Complete orthogonal decomposition explained

In linear algebra, the complete orthogonal decomposition is a matrix decomposition.^{[1] [2]} 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.

A into a product of three matrices, A = U T V ^{*} , where U and V ^{*} are unitary matrices and T is a triangular matrix. For a matrix A of rank r , the triangular matrix T can be chosen such that only its top-left r x r block is nonzero, making the decomposition rank-revealing.

For a matrix of size

m x n , assuming m \ge n , the complete orthogonal decomposition requires O(mn ^{2)} floating point operations and O(m ^{2)} auxiliary memory to compute, similar to other rank-revealing decompositions. Crucially however, if a row/column is added or removed or the matrix is perturbed by a rank-one matrix, its decomposition can be updated in O(mn) operations.

Because of its form,

A = U T V ^{*} , the decomposition is also known as UTV decomposition.^[3] Depending on whether a left-triangular or right-triangular matrix is used in place of T , it is also referred to as ULV decomposition^[4] 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

U , another applied from the right, which yields V ^{*} , which "sandwiches" triangular matrix T in the middle.

Let

A be a m x n matrix of rank r . One first performs a QR decomposition with column pivoting:A\Pi = U \begin{bmatrix} R _{11} & R _{12} \ 0 & 0 \end{bmatrix} ,

where

\Pi is a n x n permutation matrix, U is a m x m unitary matrix, R _{11} is a r x r upper triangular matrix and R _{12} is a r x (n - r) matrix. One then performs another QR decomposition on the adjoint of R :\begin{bmatrix} R ^{*} _{11} \ R ^{*} _{12} \end{bmatrix} = V' \begin{bmatrix} T ^{*} \ 0 \end{bmatrix} ,

where

V' is a n x n unitary matrix and T is an r x r lower (left) triangular matrix. Setting V = \Pi V' yields the complete orthogonal (UTV) decomposition:A = U \begin{bmatrix} T & 0 \ 0 & 0 \end{bmatrix} V ^{*} .

Since any diagonal matrix is by construction triangular, the singular value decomposition,

A = USV ^{*} , where S _{11} \ge S _{22} \ge \ldots \ge 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

Notes and References

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