Comment on page

# Matrix Factorization

## A Summary of Matrix Factorizations  ## Gaussian Elimination

• Gaussian elimination involves three types of elementary row operations:
• Swapping two rows (also known as a row exchange),
• Multiplying a row by a nonzero number,
• Adding a multiple of one row to another row.
• Gaussian elimination reduces A to row echelon form in general, whereas #4 reduces A to the reduced row echelon form (rref), which further requires 1) the leading entry (pivot) in each nonzero row is 1, and 2) each column containing a pivot has all other entries equal to zero.

## LU Decomposition

• #1, #2 and #3 are three variants of LU decomposition.
• #1 and #2 are the simple/basic forms of LU decomposition, which use only the second and third types of row operations in Gaussian elimination. No row exchanges.
• #3 is known as the LU decomposition with partial pivoting (or PLU decomposition), where row exchanges are necessary and represented by a permutation matrix P.
• There exists the fourth variant of LU decomposition, where column permutations are also necessary and represented by a permutation matrix Q. The decomposition becomes PAQ = LU, and is known as LU factorization with full pivoting.
• It is typically required that A be a square matrix, but it is possible to generalize LU decomposition to rectangular matrices.
• LU decomposition can be viewed as the matrix form of Gaussian elimination. It is often used to solve square systems of linear equations, and serves as a key step when inverting a matrix or computing the determinant of a matrix.

## Cholesky Decomposition

• #5 is the standard form of Cholesky decomposition, which is a special case of LU decomposition where matrices are symmetric and positive-definite.
• This is also known as LLT decomposition, since we can replace the notation C with L and denote
$A = LL^{\text{T}}$
. This expression is not recommended as it can confuse the reader on the meaning of notation L.
• In practice, we often perform
$A = LDL^{\text{T}}$
(as mentioned in #2) to avoid extracting square roots as required in
$C = L\sqrt{D}$
. This is often known as LDL decomposition, LDLT decomposition, or square-root-free Cholesky decomposition.
• If matrices are not positive-definite, LDLT decomposition can still be performed, but requires pivoting (as discussed previously in LU decomposition) to ensure numerical stability. The decomposition becomes
$A = P^{\text{T}}LDL^{\text{T}}P$
.

## QR Decomposition

• #6 is the standard form of QR decomposition. The only requirement is that A has independent columns.
• There are three implementations of QR decomposition: Gram–Schmidt process, Givens rotation matrices, Householder transformation (reflection operation).
• If pivoting is necessary (for numerical stability), the decomposition becomes
$PAP'=QR$
, where P and P' are permutation matrices for row and column, respectively.
• QR decomposition is often used to solve the linear least squares problem and is the basis for a particular eigenvalue algorithm, the QR algorithm.

## Eigen Decomposition

• #7 is the standard form of Eigendecomposition. The requirement is that A is diagonalizable or non-defective, or equivalently A is a square matrix with n linearly independent eigenvectors.
• Diagonalizability of A depends on enough eigenvectors, whereas the invertibility of A depends on nonzero eigenvalues. There is no connection between the two.
• Diagonalization can fail only if there are repeated eigenvalues. In this case, some of the eigenvectors may be linearly dependent on others.
• #8 is a special case of Eigendecomposition, where A is a real symmetric matrix.
• When the matrix being factorized is a normal or real symmetric matrix, the decomposition is also known as spectral decomposition, derived from the spectral theorem.
• Every real symmetric matrix is a normal matrix.
• Useful facts:
• The product of the eigenvalues is equal to the determinant of A.
• The sum of the eigenvalues is equal to the trace of A.
• The eigenvectors of A^-1 are the same as the eigenvectors of A.
• The statement "A can be eigendecomposed" does not imply that A has an inverse. A can be inverted if and only if all eigenvalues are nonzero.
• The statement "A has an inverse" does not imply that A can be eigendecomposed. The counterexample is [1 1; 0 1], which is an invertible defective matrix.

## Singular Value Decomposition

• #10 is the standard form of Singular Value Decomposition (SVD), which generalizes the eigendecomposition of a square matrix to any m-by-n matrix.
• Intuitively, the SVD decomposition breaks down a linear transformation of R^n into a composition of three geometrical transformations: a rotation or reflection (V), followed by a coordinate-by-coordinate scaling (Sigma), followed by another rotation or reflection (U).
• Examples on the relation between SVD and eigendecomposition.
• For a real symmetric square matrix, the singular values are the absolute values of the eigenvalues.
• For matrix A = [1 0 1; 0 1 1; 0 0 0], the eigenvalues of A are 1, 1, 0, whereas the singular values of A are sqrt(3), 1, 0.
• For matrix A = [1 1; 0 0], the eigenvalues are 1 and 0; the singular values are sqrt(2) and 0.

## Polar Decomposition

• #12 is the standard form of Polar decomposition.
• In general, the polar decomposition of a square matrix A always exists. If A is invertible, the decomposition is unique, and the factor H will be positive-definite.
• Intuitively, if a real n-by-n matrix A is interpreted as a linear transformation of n-dimensional space R^n, the polar decomposition separates it into a rotation or reflection U of R^n, and a scaling of the space along a set of n orthogonal axes.
• This decomposition is useful in computing the fundamental group of (matrix) Lie groups.

## Comparison in Eigen library

Decomposition
Requirements
Speed (small-to-medium)
Speed (large)
Accuracy
LLT
Positive definite
+++
+++
+
LDLT
Positive or negative semidefinite
+++
+
++
Invertible
++
++
+
FullPivLU
None
-
- -
+++
None
++
++
+
None
+
-
+++
None
-
- -
+++
None
+
-
+++
BDCSVD
None
-
-
+++
JacobiSVD
None
-
- - -
+++
• Appendix C in the textbook "Linear algebra and its applications", Gilbert Strang