LU, QR & Cholesky

Why Factorize Matrices?

Directly solving $A x = b$ or computing matrix inverse $A^{-1}$ is slow ($O(n^3)$) and numerically unstable on computers due to floating-point rounding errors.

Matrix Decompositions break $A$ into structured pieces (Triangular, Orthogonal, Diagonal) where solving systems takes simple $O(n^2)$ substitution!

┌──────────────────────────┬──────────────────────────┬──────────────────────────┐
│  1. LU DECOMPOSITION     │  2. QR DECOMPOSITION     │ 3. CHOLESKY DECOMPOSITION│
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ A = L U                  │ A = Q R                  │ A = L L^T                │
│ L: Lower Triangular      │ Q: Orthogonal (Q^T Q = I)│ L: Lower Triangular      │
│ U: Upper Triangular      │ R: Upper Triangular      │ Requires: Symmetric      │
│ General square matrices  │ Numerically stable OLS   │ Positive Definite (Cov)  │
└──────────────────────────┴──────────────────────────┴──────────────────────────┘

1. LU Decomposition (A = L U)

Factorizes a general square matrix $A$ into Lower Triangular $L$ and Upper Triangular $U$:

  Matrix A               Lower L                Upper U
  ┌───┬───┐              ┌───┬───┐              ┌───┬───┐
  │ 2 │ 4 │        =     │ 1 │ 0 │        ×     │ 2 │ 4 │
  ├───┼───┤              ├───┼───┤              ├───┼───┤
  │ 3 │ 8 │              │1.5│ 1 │              │ 0 │ 2 │
  └───┴───┘              └───┴───┘              └───┴───┘

Solving $A x = b$ in Two Fast Steps

1. Forward substitution: Solve $L y = b$ for $y$ ($O(n^2)$).
2. Back substitution: Solve $U x = y$ for $x$ ($O(n^2)$).

Total solve time drops from $O(n^3)$ to $O(n^2)$ for multiple right-hand sides $b$!

2. QR Decomposition (A = Q R)

Factorizes any $m \times n$ matrix $A$ into Orthogonal $Q$ ($Q^T Q = I$) and Upper Triangular $R$:

Numerically Stable Least Squares

To solve $X w = y$:

1. Factorize $X = Q R$.
2. Substitute into normal equation:

R w = Q^T y

Because $R$ is upper triangular, solve for weights $w$ via back-substitution without ever computing $X^T X$ directly! This prevents squaring the matrix condition number.

3. Cholesky Decomposition (A = L L^T)

Applies strictly to Symmetric Positive-Definite matrices (e.g. Covariance matrices $\Sigma$, Kernel matrices $K$):

A = L L^T

• 2x Faster: Requires $n^3 / 3$ FLOPs compared to LU ($2n^3 / 3$ FLOPs).
• Guaranteed Stability: No pivoting required.
• Key Use Case: Sampling from Multivariate Gaussians $x = \mu + L z$ where $z \sim \mathcal{N}(0, I)$, Gaussian Process regression, and Kalman filters.

Say this out loud

Matrix decompositions turn hard matrix problems into fast triangular solves. LU factors general square matrices into Lower and Upper triangular pieces. QR factors matrices into Orthogonal Q and Triangular R, offering numerically stable least-squares solving without computing X^T X. Cholesky factors symmetric positive-definite matrices like covariance matrices into L L^T twice as fast as LU.

Follow-ups to expect

• What is Partial Pivoting in LU Decomposition (P A = L U)? Rearranging matrix rows using permutation matrix P to place the largest available number on the diagonal, preventing division by near-zero numbers during Gaussian elimination.
• How do you sample from a Multivariate Normal distribution N(mu, Sigma) using Cholesky? Compute Cholesky factorization Sigma = L L^T. Draw standard normal vector z ~ N(0, I). The sampled vector is x = mu + L z.