- Source: 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
A
{\displaystyle A}
into a product of three matrices,
A
=
U
T
V
∗
{\displaystyle A=UTV^{*}}
, where
U
{\displaystyle U}
and
V
∗
{\displaystyle V^{*}}
are unitary matrices and
T
{\displaystyle T}
is a triangular matrix. For a matrix
A
{\displaystyle A}
of rank
r
{\displaystyle r}
, the triangular matrix
T
{\displaystyle T}
can be chosen such that only its top-left
r
×
r
{\displaystyle r\times r}
block is nonzero, making the decomposition rank-revealing.
For a matrix of size
m
×
n
{\displaystyle m\times n}
, assuming
m
≥
n
{\displaystyle m\geq n}
, the complete orthogonal decomposition requires
O
(
m
n
2
)
{\displaystyle O(mn^{2})}
floating point operations and
O
(
m
2
)
{\displaystyle O(m^{2})}
auxiliary memory to compute, similar to other rank-revealing decompositions. Crucially however, if a row/column is added or removed, its decomposition can be updated in
O
(
m
n
)
{\displaystyle O(mn)}
operations.
Because of its form,
A
=
U
T
V
∗
{\displaystyle A=UTV^{*}}
, the decomposition is also known as UTV decomposition. Depending on whether a left-triangular or right-triangular matrix is used in place of
T
{\displaystyle T}
, 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
U
{\displaystyle U}
, another applied from the right, which yields
V
∗
{\displaystyle V^{*}}
, which "sandwiches" triangular matrix
T
{\displaystyle T}
in the middle.
Let
A
{\displaystyle A}
be a
m
×
n
{\displaystyle m\times n}
matrix of rank
r
{\displaystyle r}
. One first performs a QR decomposition with column pivoting:
A
Π
=
U
[
R
11
R
12
0
0
]
{\displaystyle A\Pi =U{\begin{bmatrix}R_{11}&R_{12}\\0&0\end{bmatrix}}}
,
where
Π
{\displaystyle \Pi }
is a
n
×
n
{\displaystyle n\times n}
permutation matrix,
U
{\displaystyle U}
is a
m
×
m
{\displaystyle m\times m}
unitary matrix,
R
11
{\displaystyle R_{11}}
is a
r
×
r
{\displaystyle r\times r}
upper triangular matrix and
R
12
{\displaystyle R_{12}}
is a
r
×
(
n
−
r
)
{\displaystyle r\times (n-r)}
matrix. One then performs another QR decomposition on the adjoint of
R
{\displaystyle R}
:
[
R
11
∗
R
12
∗
]
=
V
′
[
T
∗
0
]
{\displaystyle {\begin{bmatrix}R_{11}^{*}\\R_{12}^{*}\end{bmatrix}}=V'{\begin{bmatrix}T^{*}\\0\end{bmatrix}}}
,
where
V
′
{\displaystyle V'}
is a
n
×
n
{\displaystyle n\times n}
unitary matrix and
T
{\displaystyle T}
is an
r
×
r
{\displaystyle r\times r}
lower (left) triangular matrix. Setting
V
=
Π
V
′
{\displaystyle V=\Pi V'}
yields the complete orthogonal (UTV) decomposition:
A
=
U
[
T
0
0
0
]
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,
A
=
U
S
V
∗
{\displaystyle A=USV^{*}}
, where
S
11
≥
S
22
≥
…
≥
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, but has a stronger rank-revealing property.
See also
Rank-revealing QR decomposition
Schur decomposition
Online machine learning
References
Kata Kunci Pencarian:
- Complete orthogonal decomposition
- Matrix decomposition
- Singular value decomposition
- Schur decomposition
- Projection (linear algebra)
- Cholesky decomposition
- Eigendecomposition of a matrix
- Orthogonal group
- Hilbert space
- Spectral theorem
