Misplaced Pages

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

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. Crucially however, if a row/column is added or removed, its decomposition can be updated in ${\displaystyle O(mn)}$ operations.

Because of its form, ${\displaystyle A=UTV^{*}}$, the decomposition is also known as UTV decomposition. 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 or URV decomposition, respectively.

Construction

The UTV decomposition is usually 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:

${\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, but has a stronger rank-revealing property.

See also

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

References

1. ^ Golub, Gene; van Loan, 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.

• Matrix decompositions
• Numerical linear algebra