# 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
DecompositionRequirementsSpeed (small-to-medium)Speed (large)Accuracy
LLTPositive definite+++++++
LDLTPositive or negative
semidefinite		++++++
PartialPivLUInvertible+++++
FullPivLUNone-- -+++
HouseholderQRNone+++++
ColPivHouseholderQRNone+-+++
FullPivHouseholderQRNone-- -+++
CompleteOrthogonalDecompositionNone+-+++
BDCSVDNone--+++
JacobiSVDNone-- - -+++
## References * Appendix C in the textbook "Linear algebra and its applications", Gilbert Strang * [Dense Linear Solvers in Eigen library](https://eigen.tuxfamily.org/dox/group__DenseLinearSolvers__Reference.html) *