Matrix factorisation and low-rank approximation

Rank = the number of independent directions a matrix «really» contains. A 1000 × 1000 matrix of rank 5 is only five patterns in different mixtures — it can be written as the product of a 1000 × 5 and a 5 × 1000 matrix: 10 000 numbers instead of a million.

The SVD (singular value decomposition) finds those patterns, sorted by importance: $A = U\Sigma V^\top$. Keep the k largest singular values → the best rank-k approximation (Eckart–Young).

Why care? Rating matrices (users × films), word co-occurrences and weight updates during fine-tuning are often nearly low-rank. LoRA exploits exactly that: ΔW ≈ BA with a small k.

import numpy as np
rng = np.random.default_rng(0)

# a «secretly» low-rank matrix plus noise
B, A = rng.normal(size=(200, 4)), rng.normal(size=(4, 300))
M = B @ A + rng.normal(0, 0.5, (200, 300))

U, s, Vt = np.linalg.svd(M, full_matrices=False)
print(np.round(s[:8], 1))     # four large ones, then small: [.. .. .. ..  ~10 ~10 ...]

def approx(k):
    return (U[:, :k] * s[:k]) @ Vt[:k]

for k in (1, 2, 4, 8, 50):
    err = np.linalg.norm(M - approx(k)) / np.linalg.norm(M)
    print(k, round(err, 3))    # falls steeply up to k=4, after which only noise is left

print(200 * 300, 200 * 4 + 4 * 300)   # 60000 vs 2000 numbers

For $A\in\mathbb R^{m\times n}$: $A = U\Sigma V^\top$ with orthogonal $U, V$ and $\Sigma = \text{diag}(\sigma_1\ge\sigma_2\ge\dots\ge 0)$. The rank = the number of $\sigma_i > 0$. Eckart–Young–Mirsky: $A_k = \sum_{i\le k}\sigma_i u_i v_i^\top$ minimises $\|A - X\|_F$ over all $X$ of rank $\le k$, with error $\sqrt{\sum_{i>k}\sigma_i^2}$. Parameters: $k(m+n)$ against $mn$. The share of the «energy» $\sum_{i\le k}\sigma_i^2/\sum_i\sigma_i^2$ gives you a choice of $k$. A randomised SVD gives $A_k$ in $O(mnk)$.