Ортогональная задача Прокруста

Задача аппроксимации матриц в линейной алгебре

Ортогональная задача Прокруста ^[1] — это задача аппроксимации матриц в линейной алгебре . В своей классической форме, даны две матрицы и и предлагается найти ортогональную матрицу, которая наиболее точно соответствует . [ ^{2] [3]} В частности, ортогональная задача Прокруста — это задача оптимизации, заданная как ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \Omega }$ ${\displaystyle A}$ ${\displaystyle B}$

$${\displaystyle {\begin{aligned}{\underset {\Omega }{\text{minimize}}}\quad &\|\Omega A-B\|_{F}\\{\text{subject to}}\quad &\Omega ^{T}\Omega =I,\end{aligned}}}$$

где обозначает норму Фробениуса . Это частный случай задачи Вахбы (с одинаковыми весами; вместо рассмотрения двух матриц, в задаче Вахбы столбцы матриц рассматриваются как отдельные векторы). Другое отличие состоит в том, что задача Вахбы пытается найти правильную матрицу поворота вместо просто ортогональной. ${\displaystyle \|\cdot \|_{F}}$

Имя Прокруст отсылает к разбойнику из греческой мифологии, который заставлял своих жертв помещаться в его постель, растягивая их конечности или отрезая их.

Решение

Первоначально эта проблема была решена Петером Шенеманом в диссертации 1964 года и вскоре после этого опубликована в журнале Psychometrika. ^[4]

Эта задача эквивалентна нахождению ближайшей ортогональной матрицы к заданной матрице , т.е. решению задачи ближайшей ортогональной аппроксимации. ${\displaystyle M=BA^{T}}$

${\displaystyle \min _{R}\|R-M\|_{F}\quad \mathrm {subject\ to} \quad R^{T}R=I}$.

Чтобы найти матрицу , используется разложение по сингулярным числам (для которого элементы неотрицательны) ${\displaystyle R}$ ${\displaystyle \Sigma }$

${\displaystyle M=U\Sigma V^{T}\,\!}$

писать

${\displaystyle R=UV^{T}.\,\!}$

Доказательство решения

Одно доказательство зависит от основных свойств скалярного произведения Фробениуса , которое индуцирует норму Фробениуса :

${\displaystyle {\begin{aligned}R&=\arg \min _{\Omega }||\Omega A-B\|_{F}^{2}\\&=\arg \min _{\Omega }\langle \Omega A-B,\Omega A-B\rangle _{F}\\&=\arg \min _{\Omega }\|\Omega A\|_{F}^{2}+\|B\|_{F}^{2}-2\langle \Omega A,B\rangle _{F}\\&=\arg \min _{\Omega }\|A\|_{F}^{2}+\|B\|_{F}^{2}-2\langle \Omega A,B\rangle _{F}\\&=\arg \max _{\Omega }\langle \Omega A,B\rangle _{F}\\&=\arg \max _{\Omega }\langle \Omega ,BA^{T}\rangle _{F}\\&=\arg \max _{\Omega }\langle \Omega ,U\Sigma V^{T}\rangle _{F}\\&=\arg \max _{\Omega }\langle U^{T}\Omega V,\Sigma \rangle _{F}\\&=\arg \max _{\Omega }\langle S,\Sigma \rangle _{F}\quad {\text{where }}S=U^{T}\Omega V\\\end{aligned}}}$

Эта величина является ортогональной матрицей (так как она является произведением ортогональных матриц) и, таким образом, выражение максимизируется, когда равно единичной матрице . Таким образом ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle I}$

${\displaystyle {\begin{aligned}I&=U^{T}RV\\R&=UV^{T}\\\end{aligned}}}$

где — решение для оптимального значения, минимизирующее квадрат нормы . ${\displaystyle R}$ ${\displaystyle \Omega }$ ${\displaystyle ||\Omega A-B\|_{F}^{2}}$

Обобщенные/ограниченные задачи Прокруста

Существует ряд проблем, связанных с классической ортогональной проблемой Прокруста. Можно обобщить ее, найдя ближайшую матрицу, в которой столбцы ортогональны , но не обязательно ортонормальны . ^[5]

В качестве альтернативы, можно ограничить его, разрешив только матрицы вращения (т.е. ортогональные матрицы с определителем 1, также известные как специальные ортогональные матрицы ). В этом случае можно записать (используя приведенное выше разложение ) ${\displaystyle M=U\Sigma V^{T}}$

${\displaystyle R=U\Sigma 'V^{T},\,\!}$

где — модифицированный , в котором наименьшее сингулярное значение заменено на (+1 или -1), а остальные сингулярные значения заменены на 1, так что определитель R гарантированно будет положительным. ^[6] Для получения дополнительной информации см. алгоритм Кабша . ${\displaystyle \Sigma '\,\!}$ ${\displaystyle \Sigma \,\!}$ ${\displaystyle \det(UV^{T})}$

Несбалансированная задача Прокруста касается минимизации нормы , где , и , с , или поочередно с комплекснозначными матрицами. Это задача над многообразием Штифеля , и в настоящее время не имеет известной замкнутой формы. Чтобы различать, стандартная задача Прокруста ( ) в этих контекстах называется сбалансированной задачей. ${\displaystyle AU-B}$ ${\displaystyle A\in \mathbb {R} ^{m\times \ell },U\in \mathbb {R} ^{\ell \times n}}$ ${\displaystyle B\in \mathbb {R} ^{m\times n}}$ ${\displaystyle m>\ell \geq n}$ ${\displaystyle U\in U(m,\ell )}$ ${\displaystyle A\in \mathbb {R} ^{m\times m}}$

Смотрите также

• Прокрустов анализ
• Преобразование Прокруста
• Проблема Вахбы
• Алгоритм Кабша
• Регистрация набора точек

Ссылки

1. Гауэр, JC; Дейкстерхейс, Великобритания (2004), Проблемы Прокруста , Oxford University Press
2. Херли, Дж. Р.; Кеттелл, Р. Б. (1962), «Производство прямого вращения для проверки предполагаемой факторной структуры», Поведенческая наука , 7 (2): 258–262, doi :10.1002/bs.3830070216
3. Голуб, Г.Х.; Ван Лоан, К. (2013). Матричные вычисления (4-е изд.). Джу Пресс. п. 327. ИСБН 978-1421407944.
4. Шёнеманн, PH (1966), «Обобщенное решение ортогональной задачи Прокруста» (PDF) , Психометрика , 31 : 1–10, doi :10.1007/BF02289451, S2CID  121676935.
5. Эверсон, Р. (1997), Ортогональные, но не ортонормальные, задачи Прокруста (PDF)
6. Эггерт, Д. В.; Лоруссо, А.; Фишер, Р. Б. (1997), «Оценка трехмерных преобразований твердого тела: сравнение четырех основных алгоритмов», Machine Vision and Applications , 9 (5): 272–290, doi :10.1007/s001380050048, S2CID  1611749