Complete orthogonal decomposition

In linear algebra, the complete orthogonal decomposition is a matrix decomposition. ^{[1] [2]} It is similar to the singular value decomposition, but typically somewhat ^[3] cheaper to compute and in particular much cheaper and easier to update when the original matrix is slightly altered. ^[1]

Specifically, the complete orthogonal decomposition factorizes an arbitrary complex matrix ${\displaystyle A}$ into a product of three matrices, ${\displaystyle A=UTV^{*}}$, where ${\displaystyle U}$ and ${\displaystyle V^{*}}$ are unitary matrices and ${\displaystyle T}$ is a triangular matrix. For a matrix ${\displaystyle A}$ of rank ${\displaystyle r}$, the triangular matrix ${\displaystyle T}$ can be chosen such that only its top-left ${\displaystyle r\times r}$ block is nonzero, making the decomposition rank-revealing.

For a matrix of size ${\displaystyle m\times n}$, assuming ${\displaystyle m\geq n}$, the complete orthogonal decomposition requires ${\displaystyle O(mn^{2})}$ floating point operations and ${\displaystyle O(m^{2})}$ auxiliary memory to compute, similar to other rank-revealing decompositions. ^[1] Crucially however, if a row/column is added or removed, its decomposition can be updated in ${\displaystyle O(mn)}$ operations. ^[1]

Because of its form, ${\displaystyle A=UTV^{*}}$, the decomposition is also known as UTV decomposition. ^[4] Depending on whether a left-triangular or right-triangular matrix is used in place of ${\displaystyle T}$, it is also referred to as ULV decomposition ^[3] or URV decomposition, ^[5] respectively.

Construction

The UTV decomposition is usually ^{[6] [7]} computed by means of a pair of QR decompositions: one QR decomposition is applied to the matrix from the left, which yields ${\displaystyle U}$, another applied from the right, which yields ${\displaystyle V^{*}}$, which "sandwiches" triangular matrix ${\displaystyle T}$ in the middle.

Let ${\displaystyle A}$ be a ${\displaystyle m\times n}$ matrix of rank ${\displaystyle r}$. One first performs a QR decomposition with column pivoting:

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

where ${\displaystyle \Pi }$ is a ${\displaystyle n\times n}$ permutation matrix, ${\displaystyle U}$ is a ${\displaystyle m\times m}$ unitary matrix, ${\displaystyle R_{11}}$ is a ${\displaystyle r\times r}$ upper triangular matrix and ${\displaystyle R_{12}}$ is a ${\displaystyle r\times (n-r)}$ matrix. One then performs another QR decomposition on the adjoint of ${\displaystyle R}$:

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

where ${\displaystyle V'}$ is a ${\displaystyle n\times n}$ unitary matrix and ${\displaystyle T}$ is an ${\displaystyle r\times r}$ lower (left) triangular matrix. Setting ${\displaystyle V=\Pi V'}$ yields the complete orthogonal (UTV) decomposition: ^[1]

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

Since any diagonal matrix is by construction triangular, the singular value decomposition, ${\displaystyle A=USV^{*}}$, where ${\displaystyle S_{11}\geq S_{22}\geq \ldots \geq 0}$, is a special case of the UTV decomposition. Computing the SVD is slightly more expensive than the UTV decomposition, ^[3] but has a stronger rank-revealing property.

See also

• Rank-revealing QR decomposition
• Schur decomposition
• Online machine learning

References

1. Golub, Gene; van Loon, Charles F. (15 October 1996). Matrix Computations (Third ed.). Johns Hopkins University Press. ISBN   0-8018-5414-8.
2. Björck, Åke (December 1996). Numerical methods for least squares problems. SIAM. ISBN   0-89871-360-9.
3. Chandrasekaran, S.; Gu, M.; Pals, T. (January 2006). "A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations". SIAM Journal on Matrix Analysis and Applications. 28 (3): 603–622. doi:10.1137/S0895479803436652.
4. Fierro, Ricardo D.; Hansen, Per Christian; Hansen, Peter Søren Kirk (1999). "UTV Tools: Matlab templates for rank-revealing UTV decompositions" (PDF). Numerical Algorithms. 20 (2/3): 165–194. doi:10.1023/A:1019112103049. S2CID   19861950.
5. Adams, G.; Griffin, M.F.; Stewart, G.W. (1991). "Direction-of-arrival estimation using the rank-revealing URV decomposition". [Proceedings] ICASSP 91: 1991 International Conference on Acoustics, Speech, and Signal Processing. Proc. Of IEEE Internat. Conf. On Acoustics, Speech, and Signal Processing. pp. 1385-1388 vol.2. doi:10.1109/icassp.1991.150681. hdl:1903/555. ISBN   0-7803-0003-3. S2CID   9201732.
6. "LAPACK – Complete Orthogonal Factorization". netlib.org.
7. "Eigen::CompleteOrthogonalDecomposition". Eigen 3.3 reference documentation. Retrieved 2023-08-07.