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

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

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

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

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

Решение

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

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

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

.

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

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

писать

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

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

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

{\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}}

Это количество

S

является ортогональной матрицей (поскольку она является произведением ортогональных матриц), и, следовательно, выражение максимизируется, когда

S

равно единичной матрице

I

. Таким образом

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

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

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

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

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

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

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

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

См. также

Ссылки

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

[1] Гауэр, Дж.К.; Дейкстерхейс, Великобритания (2004), Проблемы Прокруста , Oxford University Press

[2] Херли-младший; Кеттелл, Р.Б. (1962), «Проведение прямого вращения для проверки гипотетической факторной структуры», Behavioral Science , 7 (2): 258–262, doi : 10.1002/bs.3830070216

[3] Голуб, Г.Х.; Ван Лоан, К. (2013). Матричные вычисления (4-е изд.). Джу Пресс. п. 327. ИСБН 978-1421407944 .

[4] Шенеманн, PH (1966), «Обобщенное решение ортогональной проблемы Прокруста» (PDF) , Psychometrika , 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

[1]

[2]

[3]

[4]

[5]

[6]