Matrix Factorization

Matrix factorization is the representation of a matrix as a product of two or more matrices with useful structural properties. In linear algebra and numerical linear algebra, these properties may include triangular form, orthogonality, or a diagonal arrangement of singular values. Factorizations transform problems such as solving equations, estimating rank, and computing spectral information into simpler operations. The term also encompasses approximate factorizations that represent data using fewer parameters than the original matrix. (netlib.org)

Mathematical framework

An exact factorization has the form $A=BC$, or a product of more factors, with compatible dimensions. An approximate factorization instead seeks $A\approx BC$, usually under restrictions on the factors or their dimensions. Different restrictions produce different decompositions; there is no single factorization appropriate for every purpose. Common numerical families include LU, Cholesky, QR, singular value, and Schur decompositions. (netlib.org)

For a low-rank representation of an $m\times n$ matrix, one uses factors of sizes $m\times k$ and $k\times n$, where $k$ is smaller than the original dimensions. Their product has rank at most $k$. This construction underlies dimensionality reduction: the matrix is represented through a smaller collection of components rather than through all its entries independently. (cbmm.mit.edu)

Triangular and orthogonal factorizations

LU decomposition expresses a matrix through lower- and upper-triangular factors. For a nonsingular square matrix, row pivoting gives the convention

where $P$ records row permutations and $L$ usually has unit diagonal. This is closely connected to Gaussian elimination. To solve a system of linear equations $Ax=b$, one solves $Ly=Pb$ by forward substitution and then $Ux=y$ by backward substitution. The same factors can serve multiple right-hand sides. (netlib.org)

Cholesky decomposition applies to a real symmetric positive-definite matrix:

For a complex Hermitian positive-definite matrix, the corresponding expression is $A=LL^*$, where the asterisk denotes conjugate transpose. This factorization exploits symmetry and positive definiteness rather than treating the matrix as general. (netlib.org)

QR decomposition writes

where $Q$ is an orthogonal matrix in the real case and a unitary matrix in the complex case. The factor $R$ is upper triangular or upper trapezoidal, depending on dimensions. A reduced QR representation retains only the needed columns of $Q$. Orthogonal transformations preserve Euclidean lengths, making QR useful for least-squares problems, including ordinary least squares. (netlib.org)

Singular value and spectral decompositions

The singular value decomposition (SVD) exists for every real or complex rectangular matrix:

The matrices $U$ and $V$ are unitary, or orthogonal for real data, while $\Sigma$ is rectangular diagonal with nonnegative singular values conventionally arranged in descending order. For real matrices, $V^*$ is the transpose $V^T$. Singular vectors describe paired directions in the input and output spaces. (netlib.org)

Spectral factorizations concern eigenvalues and eigenvectors of square matrices. The Schur decomposition writes a complex square matrix as $A=QTQ^*$, with unitary $Q$ and upper-triangular $T$. Its diagonal contains the eigenvalues. The real version uses orthogonal $Q$ and quasi-triangular $T$, whose diagonal contains blocks of sizes one or two. Schur form therefore accommodates general square matrices without requiring a diagonal middle factor. (netlib.org)

Low-rank approximation

Truncating the SVD retains the largest $k$ singular values and their associated vectors:

The Eckart–Young–Mirsky theorem states that this construction minimizes the approximation error among matrices of rank at most $k$, in both the spectral and Frobenius norms. The squared Frobenius error equals the sum of the squares of the discarded singular values. This gives a precise relationship between representation size and reconstruction error. (ocw.mit.edu)

Low-rank approximation can support data compression and extraction of dominant patterns. Its connection with principal component analysis is especially important: applying the SVD to a centered data matrix identifies principal directions. Small reconstruction error, however, concerns the chosen mathematical norm; it does not by itself establish that every application-relevant feature has been preserved. (cbmm.mit.edu)

Constrained factorizations and data modeling

In machine learning, factorization can estimate latent components rather than compute an exact decomposition. Nonnegative matrix factorization seeks $A\approx WH$, with all entries of the data and factors nonnegative. Components combine additively, without cancellation by negative coefficients. Such representations have been demonstrated for image parts and semantic features in text, although the interpretation depends on the data and fitted factors. (nature.com)

In recommender systems, rows and columns can represent users and items, with low-dimensional vectors determining predicted interactions through dot products. The factors are learned from observed entries rather than necessarily from a complete matrix. Implementations commonly use a loss function together with regularization, and may include separate user and item bias terms. Alternating least-squares methods repeatedly update one collection of factors while holding the other fixed. (link.springer.com)

Numerical accuracy

A mathematical factorization and its computed approximation are distinct. Floating-point arithmetic introduces rounding errors, so numerical stability concerns how those errors affect the result. Backward error measures the perturbation to the input for which the computed answer would be exact. A small backward error can still accompany substantial output error when the underlying problem has a large condition number. Consequently, accuracy assessment requires both information about the algorithm and information about the sensitivity of the problem. (netlib.org)