View source for Complete orthogonal decomposition

In [[Linear algebra|linear algebra]], the '''complete orthogonal decomposition''' is a [[Matrix decomposition|matrix decomposition]].<ref name="golub-van-loon">{{cite book |last1=Golub |first1=Gene |last2=van Loon |first2=Charles F. |title=Matrix Computations |date=15 October 1996 |publisher=Johns Hopkins University Press |isbn=0-8018-5414-8 |edition=Third}}</ref><ref name="bjorck">{{cite book |last1=Björck |first1=Åke |title=Numerical methods for least squares problems |date=December 1996 |publisher=SIAM |isbn=0-89871-360-9}}</ref> It is similar to the [[Singular value decomposition|singular value decomposition]], but typically somewhat<ref name="Chandrasekaran" /> cheaper to compute and in particular much cheaper and easier to update when the original matrix is slightly altered.<ref name="golub-van-loon" />
Specifically, the complete orthogonal decomposition [[Factorization|factorizes]] an arbitrary [[Complex number|complex]] [[Matrix (mathematics)|matrix]] <math>A</math> into a product of three matrices, <math>A = U T V^*</math>, where <math>U</math> and <math>V^*</math> are [[Unitary matrix|unitary matrices]] and <math>T</math> is a [[Triangular matrix|triangular matrix]].  For a matrix <math>A</math> of rank <math>r</math>, the triangular matrix <math>T</math> can be chosen such that only its top-left <math>r\times r</math> block is nonzero, making the decomposition rank-revealing.

For a matrix of size <math>m\times n</math>, assuming <math>m \ge n</math>, the complete orthogonal decomposition requires <math>O(mn^2)</math> floating point operations and <math>O(m^2)</math> auxiliary memory to compute, similar to other rank-revealing decompositions.<ref name="golub-van-loon" /> 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 <math>O(mn)</math> operations.<ref name="golub-van-loon" />

Because of its form, <math>A = U T V^*</math>, the decomposition is also known as '''UTV decomposition'''.<ref>{{cite journal |last1=Fierro |first1=Ricardo D. |last2=Hansen |first2=Per Christian |last3=Hansen |first3=Peter Søren Kirk |title=UTV Tools: Matlab templates for rank-revealing UTV decompositions |journal=Numerical Algorithms |date=1999 |volume=20 |issue=2/3 |pages=165–194 |doi=10.1023/A:1019112103049|s2cid=19861950 |url=https://backend.orbit.dtu.dk/ws/files/57025531/10.1023_A_1019112103049.pdf }}</ref>  Depending on whether a left-triangular or right-triangular matrix is used in place of <math>T</math>, it is also referred to as '''ULV decomposition'''<ref name="Chandrasekaran">{{cite journal |last1=Chandrasekaran |first1=S. |last2=Gu |first2=M. |last3=Pals |first3=T. |title=A Fast ''ULV'' Decomposition Solver for Hierarchically Semiseparable Representations |journal=SIAM Journal on Matrix Analysis and Applications |date=January 2006 |volume=28 |issue=3 |pages=603–622 |doi=10.1137/S0895479803436652}}</ref> or '''URV decomposition''',<ref>{{cite book |last1=Adams |first1=G. |last2=Griffin |first2=M.F. |last3=Stewart |first3=G.W. |title=&#91;Proceedings&#93; ICASSP 91: 1991 International Conference on Acoustics, Speech, and Signal Processing |chapter=Direction-of-arrival estimation using the rank-revealing URV decomposition |publisher=Proc. Of IEEE Internat. Conf. On Acoustics, Speech, and Signal Processing |date=1991 |pages=1385-1388 vol.2 |doi=10.1109/icassp.1991.150681|hdl=1903/555 |isbn=0-7803-0003-3 |s2cid=9201732 }}</ref> respectively.

==Construction==
The UTV decomposition is usually<ref name="lapack">{{cite web |title=LAPACK – Complete Orthogonal Factorization |url=https://netlib.org/lapack/lug/node43.html |website=netlib.org}}</ref><ref>{{cite web |title=Eigen::CompleteOrthogonalDecomposition|url=https://eigen.tuxfamily.org/dox-3.3/classEigen_1_1CompleteOrthogonalDecomposition.html |website=Eigen 3.3 reference documentation |access-date=2023-08-07}}</ref> computed by means of a pair of [[QR decomposition]]s: one QR decomposition is applied to the matrix from the left, which yields <math>U</math>, another applied from the right, which yields <math>V^*</math>, which "sandwiches" triangular matrix <math>T</math> in the middle.

Let <math>A</math> be a <math>m\times n</math> matrix of rank <math>r</math>. One first performs a QR decomposition with column pivoting:

:<math>A\Pi = U \begin{bmatrix} R_{11} & R_{12} \\ 0 & 0 \end{bmatrix}</math>,

where <math>\Pi</math> is a <math>n\times n</math> [[Permutation matrix|permutation matrix]], <math>U</math> is a <math>m\times m</math> [[Unitary matrix|unitary matrix]], <math>R_{11}</math> is a <math>r\times r</math> upper triangular matrix and <math>R_{12}</math> is a <math>r\times(n-r)</math> matrix.  One then performs another QR decomposition on the adjoint of <math>R</math>:

:<math>\begin{bmatrix} R^*_{11} \\ R^*_{12}\end{bmatrix}
= V' \begin{bmatrix} T^* \\ 0\end{bmatrix}
</math>,

where <math>V'</math> is a <math>n\times n</math> unitary matrix and <math>T</math> is an <math>r\times r</math> lower (left) triangular matrix. Setting <math>V = \Pi V'</math> yields the complete orthogonal (UTV) decomposition:<ref name="golub-van-loon" />

:<math>A = U \begin{bmatrix} T & 0 \\ 0 & 0 \end{bmatrix} V^*</math>.

Since any [[Diagonal matrix|diagonal matrix]] is by construction triangular, the [[Singular value decomposition|singular value decomposition]], <math>A = USV^*</math>, where <math>S_{11} \ge S_{22} \ge \ldots \ge 0</math>, is a special case of the UTV decomposition.  Computing the SVD is slightly more expensive than the UTV decomposition,<ref name="Chandrasekaran" /> but has a stronger rank-revealing property.

==See also==
* [[RRQR factorization|Rank-revealing QR decomposition]]
* [[Schur decomposition]]
* [[Online machine learning]]

==References==
{{Reflist}}

{{Numerical linear algebra}}

[[Category:Matrix decompositions]]
[[Category:Numerical linear algebra]]

{{Sourceattribution|Complete orthogonal decomposition}}