Complete orthogonal decomposition

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 [math]\displaystyle{ A }[/math] into a product of three matrices, [math]\displaystyle{ A = U T V^* }[/math], where [math]\displaystyle{ U }[/math] and [math]\displaystyle{ V^* }[/math] are unitary matrices and [math]\displaystyle{ T }[/math] is a triangular matrix. For a matrix [math]\displaystyle{ A }[/math] of rank [math]\displaystyle{ r }[/math], the triangular matrix [math]\displaystyle{ T }[/math] can be chosen such that only its top-left [math]\displaystyle{ r\times r }[/math] block is nonzero, making the decomposition rank-revealing.

For a matrix of size [math]\displaystyle{ m\times n }[/math], assuming [math]\displaystyle{ m \ge n }[/math], the complete orthogonal decomposition requires [math]\displaystyle{ O(mn^2) }[/math] floating point operations and [math]\displaystyle{ O(m^2) }[/math] 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 [math]\displaystyle{ O(mn) }[/math] operations.

Because of its form, [math]\displaystyle{ A = U T V^* }[/math], the decomposition is also known as UTV decomposition. Depending on whether a left-triangular or right-triangular matrix is used in place of [math]\displaystyle{ T }[/math], 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 [math]\displaystyle{ U }[/math], another applied from the right, which yields [math]\displaystyle{ V^* }[/math], which "sandwiches" triangular matrix [math]\displaystyle{ T }[/math] in the middle.

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

[math]\displaystyle{ A\Pi = U \begin{bmatrix} R_{11} & R_{12} \\ 0 & 0 \end{bmatrix} }[/math],

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

[math]\displaystyle{ \begin{bmatrix} R^*_{11} \\ R^*_{12}\end{bmatrix} = V' \begin{bmatrix} T^* \\ 0\end{bmatrix} }[/math],

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

[math]\displaystyle{ A = U \begin{bmatrix} T & 0 \\ 0 & 0 \end{bmatrix} V^* }[/math].

Since any diagonal matrix is by construction triangular, the singular value decomposition, [math]\displaystyle{ A = USV^* }[/math], where [math]\displaystyle{ 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, but has a stronger rank-revealing property.

See also

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