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