Matrix Phylogeny

Let's step back and organize the decompositions you have met into a phylogeny — a family tree of matrix factorizations, each specialized for different matrix classes. The most general factorizations apply to the broadest set of matrices; the most specialized exploit extra structure for speed or insight.

At the top sit LU ($A = LU$, requires $A$ invertible after permutations) and QR ($A = QR$, exists for any rectangular $A$). These are the workhorses for solving linear systems and least-squares problems. LU is cheap but numerically delicate; QR uses orthogonal matrices and is more stable, especially for tall-skinny matrices.

Moving to square matrices, eigendecomposition ($A = PDP^{-1}$) exists for diagonalizable matrices. For the subset of symmetric matrices, it specializes to $A = QDQ^\top$ with orthogonal $Q$ (spectral theorem). For the even narrower subset of symmetric positive definite matrices, we get Cholesky ($A = LL^\top$) as a fast square-root factorization.

Above everything in generality sits SVD ($A = U\Sigma V^\top$), which works for every rectangular matrix, every rank, every condition number. It is slower than specialized decompositions but universal. Inside, every other decomposition can be connected to it: QR is an intermediate step, eigendecomposition is SVD when $A$ is symmetric, and Cholesky is a specialized $LDL^\top$ for positive-definite matrices.

Worked example — decision flowchart: You need to solve $A\mathbf{x} = \mathbf{b}$ for a $5000 \times 5000$ matrix $A$. Is $A$ SPD (e.g., $X^\top X$ in regression)? → Cholesky ($\approx 5000^3/3$ flops). Otherwise is $A$ square and well-conditioned? → LU with partial pivoting ($\approx 2\cdot 5000^3/3$ flops). Otherwise for least squares or rank-deficient $A$? → QR or SVD. Matching the decomposition to the problem structure can cut compute by a factor of 2–10.

Worked example — SVD vs. eigendecomposition cost: For a $n \times n$ symmetric matrix, eigendecomposition costs $O(n^3)$; SVD on the same matrix also costs $O(n^3)$ but with a larger constant (~2-3×). Rule of thumb: use eigendecomposition when you know the matrix is symmetric (PCA covariance, graph Laplacian); use SVD for rectangular data matrices or when you don't trust the symmetry. For a $10^5 \times 10^5$ matrix, this constant factor is hours of compute.

ML connection — normalizing flows use log|det J|: Normalizing flows require efficient Jacobian determinants. Designs often constrain the Jacobian to be triangular (so $\det J$ = product of diagonal) or to be a composition of rotations + diagonal scales (Cholesky-like). Picking the right decomposition structure for your layer is a modeling choice that directly controls training speed.

When you are solving an ML problem, pick the most specific decomposition that still applies. For normal equations $X^\top X \mathbf{w} = X^\top \mathbf{y}$, use Cholesky — it's twice as fast as LU. For least squares on ill-conditioned data, use QR on $X$ directly, avoiding the conditioning squaring from $X^\top X$. For PCA, use SVD on $X$ directly for best numerics. For general spectral problems, use eigendecomposition of the relevant symmetric operator. Knowing the phylogeny is knowing when to use which tool.