Полное ортогональное разложение

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

В частности, полное ортогональное разложение факторизует произвольную комплексную матрицу. $A$ в произведение трех матриц, $A=UTV^{*}$, где $U$ и $V^{*}$ являются унитарными матрицами и $T$ представляет собой треугольную матрицу . Для матрицы $A$ ранга ​ $r$, треугольная матрица $T$ можно выбрать так, чтобы только верхний левый $r\times r$ блок не равен нулю, что делает ранг разложения очевидным.

Для матрицы размера $m\times n$, предполагая $m\geq n$, полное ортогональное разложение требует $O(mn^{2})$ операции с плавающей запятой и $O(m^{2})$ вспомогательная память для вычислений, аналогично другим разложениям, раскрывающим ранги. Однако важно отметить, что если строка/столбец добавляется или удаляется или матрица возмущается матрицей первого ранга, ее разложение можно обновить в $O(mn)$ операции.

Из-за своей формы, $A=UTV^{*}$, это разложение также известно как разложение UTV . В зависимости от того, используется ли левотреугольная или правотреугольная матрица вместо $T$, это также называется разложением УМО. или URV-разложение , соответственно.

Строительство

Разложение UTV обычно вычисляется с помощью пары QR-разложений : одно QR-разложение применяется к матрице слева, что дает $U$, еще один применяется справа, что дает $V^{*}$, который "сэндвичирует" треугольную матрицу $T$ в середине.

Позволять $A$ быть $m\times n$ матрица рангов $r$. Сначала выполняется QR-разложение с поворотом столбцов:

$A\Pi =U{\begin{bmatrix}R_{11}&R_{12}\\0&0\end{bmatrix}}$,

где $\Pi$ это $n\times n$ матрица перестановок , $U$ это $m\times m$ унитарная матрица , $R_{11}$ это $r\times r$ верхняя треугольная матрица и $R_{12}$ это $r\times (n-r)$ матрица. Затем выполняется еще одно QR-разложение на сопряженном $R$:

${\begin{bmatrix}R_{11}^{*}\\R_{12}^{*}\end{bmatrix}}=V'{\begin{bmatrix}T^{*}\\0\end{bmatrix}}$,

где $V'$ это $n\times n$ унитарная матрица и $T$ это $r\times r$ нижняя (левая) треугольная матрица. Параметр $V=\Pi V'$ дает полное ортогональное (UTV) разложение:

$A=U{\begin{bmatrix}T&0\\0&0\end{bmatrix}}V^{*}$.

Поскольку любая диагональная матрица по построению треугольна, разложение по сингулярным значениям , $A=USV^{*}$, где $S_{11}\geq S_{22}\geq \ldots \geq 0$, является частным случаем разложения UTV. Вычисление СВД немного дороже, чем разложение UTV, но имеет более сильное свойство выявления ранга.

См. также

• Ранговое QR-разложение
• Разложение Шура
• Машинное обучение онлайн