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

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

Because of its form, ${\displaystyle A=UTV^{*}}${\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}${\displaystyle T}, it is also referred to as ULV decomposition^[3] or URV decomposition,^[5] respectively.

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}${\displaystyle U}, another applied from the right, which yields ${\displaystyle V^{*}}${\displaystyle V^{*}}, which "sandwiches" triangular matrix ${\displaystyle T}${\displaystyle T} in the middle.

Let ${\displaystyle A}${\displaystyle A} be a ${\displaystyle m\times n}${\displaystyle m\times n} matrix of rank ${\displaystyle r}${\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}}}${\displaystyle A\Pi =U{\begin{bmatrix}R_{11}&R_{12}\0円&0\end{bmatrix}}},

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

${\displaystyle {\begin{bmatrix}R_{11}^{*}\\R_{12}^{*}\end{bmatrix}}=V'{\begin{bmatrix}T^{*}\0円\end{bmatrix}}}${\displaystyle {\begin{bmatrix}R_{11}^{*}\\R_{12}^{*}\end{bmatrix}}=V'{\begin{bmatrix}T^{*}\0円\end{bmatrix}}},

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

${\displaystyle A=U{\begin{bmatrix}T&0\0円&0\end{bmatrix}}V^{*}}${\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^{*}}${\displaystyle A=USV^{*}}, where ${\displaystyle S_{11}\geq S_{22}\geq \ldots \geq 0}${\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.

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

• Matrix decompositions
• Numerical linear algebra