Full search page →

ML 01A · Linear Algebra for Learning

Machine LearningBeginner29 minUpdated Nov 6, 2026

Needs: ML 01 · Introduction to Machine Learning

Navigate: this page and this track: Navigate: this page and this track
Explore this chapter 1 interactive experiment

Move the images of the two basis vectors and watch a real photograph follow. The determinant is the signed area scale, the singular values are the stretch along two perpendicular directions, and rank 1 flattens the picture onto a line.

What you’ll learn

  • Track array shapes and interpret matrix multiplication.
  • Use rank, null spaces and norms to reason about linear systems.
  • Read eigenvalues and singular values as geometric information.
  • Solve least-squares problems and diagnose sensitivity to noise.
  • Derive PCA and connect matrix identities to learning.

The big picture

Almost every operation inside a neural network is a linear map followed by a simple nonlinear function. A fully connected layer multiplies by a weight matrix. A convolution is a structured matrix product. Attention computes dot products between vectors and then mixes vectors with a matrix of weights. Linear algebra is the language for all of these. It tells us what a map keeps, what it throws away, what it stretches, and how to compute it without losing accuracy.

This chapter follows the “Applied Math” part of Goodfellow, Bengio and Courville’s Deep Learning [1] and the linear algebra chapters of Mathematics for Machine Learning [2]. Strang’s textbook [3] is the gentlest full course if you want more practice, and Golub and Van Loan [4] and Trefethen and Bau [5] are the standard references for how these computations are done reliably on a computer. Read this chapter before ML 02 if matrix notation is unfamiliar. The companion chapters are ML 01B · Probability and Information Theory and ML 01C · Numerical Computation.

The chapter has a single thread. We start with objects and shapes, move to products and solving equations, then measure size with norms. Eigendecomposition and the SVD then explain the “personality” of a matrix. The pseudo-inverse, trace and determinant are tools built on top of them. Finally, we use every one of these tools to derive PCA, the classic method for compressing data, exactly as it is derived in [1].

Scalars, vectors, matrices and tensors

Plain version. Every number in machine learning lives in an array with named axes. Name every axis before you multiply anything.

A scalar is a single number, written in italics: s∈Rs\in\mathbb R. A vector is an ordered list of nn numbers, written in bold lowercase or plain lowercase in this chapter: x∈Rnx\in\mathbb R^n, with entries x1,…,xnx_1,\dots,x_n. By convention a vector is a column. A matrix is a 2-D grid of numbers: A∈Rm×nA\in\mathbb R^{m\times n} has mm rows and nn columns, and AijA_{ij} is the entry in row ii and column jj. A tensor is an array with any number of axes.

These objects map directly onto data:

  • A grayscale image of height HH and width WW is a matrix in RH×W\mathbb R^{H\times W}. Flattened, it becomes a vector x∈RHWx\in\mathbb R^{HW}. (See Images as Arrays.)
  • A dataset of nn examples with dd features each, stored one example per row, is a design matrix X∈Rn×dX\in\mathbb R^{n\times d}.
  • A fully connected layer with weights W∈Rd×mW\in\mathbb R^{d\times m} and bias b∈Rmb\in\mathbb R^m maps the whole batch at once: Y=XW+1b⊤∈Rn×mY=XW+\mathbf 1 b^\top\in\mathbb R^{n\times m}, where 1∈Rn\mathbf 1\in\mathbb R^n is a vector of ones.
  • An image batch in PyTorch is usually a 4-D tensor of shape B×C×H×WB\times C\times H\times W (batch, channels, height, width). A batch of token embeddings in a Transformer is usually B×N×DB\times N\times D (batch, sequence length, embedding width).

The transpose A⊤A^\top swaps rows and columns: (A⊤)ij=Aji(A^\top)_{ij}=A_{ji}. It satisfies (A⊤)⊤=A(A^\top)^\top=A and (AB)⊤=B⊤A⊤(AB)^\top=B^\top A^\top. Note the reversed order.

Broadcasting

Writing 1b⊤\mathbf 1b^\top is mathematically honest but tedious, so libraries let you add a vector to every row of a matrix directly. This is called broadcasting: when two arrays have different shapes, axes of length 1 (or missing leading axes) are stretched to match. Broadcasting is convenient and dangerous, because a wrong shape often still runs. The most common bug is subtracting a column vector of shape (n,1)(n,1) from a flat vector of shape (n,)(n,), which silently produces an n×nn\times n matrix instead of nn residuals.

Code · Python · 22 lines
import numpy as np

rng = np.random.default_rng(0)
X = rng.normal(size=(32, 64))      # batch of 32 examples, 64 features
W = rng.normal(size=(64, 10))      # linear map 64 -> 10
b = rng.normal(size=10)            # one bias per output
Y = X @ W + b                      # b broadcasts over the 32 rows
assert Y.shape == (32, 10)

# A classic broadcasting bug: (32,) - (32, 1) silently becomes (32, 32)
y_true = rng.normal(size=32)
y_pred = rng.normal(size=(32, 1))
print("buggy residual shape:", (y_true - y_pred).shape)
print("fixed residual shape:", (y_true - y_pred[:, 0]).shape)

# Four equivalent views of the same matrix product
A, B = rng.normal(size=(3, 4)), rng.normal(size=(4, 2))
entry = np.array([[A[i] @ B[:, j] for j in range(2)] for i in range(3)])
cols = np.stack([A @ B[:, j] for j in range(2)], axis=1)
outer = sum(np.outer(A[:, k], B[k]) for k in range(4))
assert np.allclose(A @ B, entry) and np.allclose(A @ B, cols) and np.allclose(A @ B, outer)
print("all views agree")

The output shows (32, 32) for the buggy line and (32,) for the fixed one. A mean over a 32×3232\times32 array still returns a single number, so a loss computed this way trains without errors while optimizing the wrong thing. Put assert statements on shapes in any code you care about.

Multiplying matrices and vectors

Plain version. A matrix product chains two linear machines into one. Each output number is a dot product between a row of the first matrix and a column of the second.

For A∈Rm×nA\in\mathbb R^{m\times n} and B∈Rn×pB\in\mathbb R^{n\times p}, the matrix product C=AB∈Rm×pC=AB\in\mathbb R^{m\times p} is

Cij=∑k=1nAikBkj.C_{ij}=\sum_{k=1}^{n}A_{ik}B_{kj}.

Here ii indexes rows of AA (and of CC), jj indexes columns of BB (and of CC), and kk runs over the shared inner dimension nn. The inner dimensions must match; that is the first thing to check when a shape error appears.

The same product can be read in four ways, and each one is useful:

  1. Entry view. CijC_{ij} is the dot product of row ii of AA with column jj of BB. This is how attention scores QK⊤QK^\top are read: every query is compared with every key.
  2. Column view. Column jj of CC is AA times column jj of BB. Each column of CC is a combination of the columns of AA.
  3. Row view. Row ii of CC is row ii of AA times BB. In Y=XWY=XW, each output example is its input row pushed through the same weights.
  4. Outer-product view. C=∑ka:kbk:C=\sum_k a_{:k}b_{k:}, a sum of nn rank-one matrices, each formed from column kk of AA and row kk of BB. This view explains low-rank approximation and LoRA later in the chapter.

The code above checks that all four views give the same answer.

Matrix multiplication is associative, (AB)C=A(BC)(AB)C=A(BC), and distributive, A(B+C)=AB+ACA(B+C)=AB+AC, but not commutative: AB≠BAAB\ne BA in general, and often one of the two products is not even defined. The elementwise (Hadamard) product A⊙BA\odot B multiplies matching entries instead and needs equal shapes. In NumPy and PyTorch, A @ B is the matrix product and A * B is elementwise. The dot product of two vectors x,y∈Rnx,y\in\mathbb R^n is the special case x⊤y=∑ixiyix^\top y=\sum_i x_iy_i, and it is symmetric: x⊤y=y⊤xx^\top y=y^\top x.

Identity, inverse and systems of equations

A system of mm linear equations in nn unknowns can be written compactly as

Ax=b,A∈Rm×n,  x∈Rn,  b∈Rm.Ax=b,\qquad A\in\mathbb R^{m\times n},\; x\in\mathbb R^n,\; b\in\mathbb R^m.

Each row of AA holds the coefficients of one equation, xx holds the unknowns, and bb holds the right-hand sides.

The identity matrix InI_n has ones on the diagonal and zeros elsewhere; it leaves every vector unchanged, Inx=xI_nx=x. A square matrix AA is invertible if there is a matrix A−1A^{-1} with A−1A=AA−1=IA^{-1}A=AA^{-1}=I. Then the system has exactly one solution, x=A−1bx=A^{-1}b.

That formula is excellent for derivations and poor for computation. Explicitly forming A−1A^{-1} costs more and loses more accuracy than solving the system directly with an LU, Cholesky or QR factorization [4], [5]. In NumPy, write np.linalg.solve(A, b), not np.linalg.inv(A) @ b. In this chapter, A−1A^{-1} is a thinking tool.

Linear dependence, span and rank

Plain version. Rank counts how many genuinely different directions a matrix can produce. Repeated or redundant columns add nothing new.

A linear combination of vectors v(1),…,v(k)v^{(1)},\dots,v^{(k)} is ∑iciv(i)\sum_i c_iv^{(i)} for scalars cic_i. The span of a set of vectors is the set of all their linear combinations. Because Ax=∑jxj a:jAx=\sum_j x_j\,a_{:j}, the vector AxAx is a linear combination of the columns a:ja_{:j} of AA. So Ax=bAx=b has a solution exactly when bb lies in the span of the columns, called the column space (or range) of AA.

A set of vectors is linearly independent if no vector in it is a linear combination of the others; equivalently, ∑iciv(i)=0\sum_ic_iv^{(i)}=0 only when every ci=0c_i=0. The rank of AA is the number of linearly independent columns, which always equals the number of linearly independent rows. For A∈Rm×nA\in\mathbb R^{m\times n}, rank⁡(A)≤min⁡(m,n)\operatorname{rank}(A)\le\min(m,n); if equality holds, AA has full rank.

The null space of AA is the set of vectors zz with Az=0Az=0. Those are the input directions that AA destroys. The rank–nullity theorem says

rank⁡(A)+dim⁡null⁡(A)=n,\operatorname{rank}(A)+\dim\operatorname{null}(A)=n,

where nn is the number of columns and dim⁡\dim is the number of independent directions in the null space. This one equation explains the three regimes of Ax=bAx=b:

Shape and rankWhat happensTypical ML case
square, full rankexactly one solutiona well-posed change of coordinates
tall (m>nm\gt n), full column rankusually no exact solution; solve in the least-squares senseregression with more examples than features
wide (m<nm\lt n) or rank-deficientinfinitely many solutions (if any)more parameters than constraints, as in deep networks

For a square matrix, “invertible”, “full rank”, “columns linearly independent” and “null space contains only zero” are all the same statement. A square matrix that fails them is called singular.

Norms: measuring size

Plain version. A norm turns a vector into one non-negative number that says how big it is. Different norms disagree about what “big” means.

A norm is any function ff with f(x)=0⇒x=0f(x)=0\Rightarrow x=0, f(x+y)≤f(x)+f(y)f(x+y)\le f(x)+f(y) (the triangle inequality), and f(αx)=∣α∣f(x)f(\alpha x)=|\alpha|f(x) for every scalar α\alpha. The most common family is the LpL^p norm,

∥x∥p=(∑i∣xi∣p)1/p,p≥1.\|x\|_p=\Big(\sum_i|x_i|^p\Big)^{1/p},\qquad p\ge1.
  • ∥x∥2\|x\|_2, the Euclidean norm, is ordinary length; we often write ∥x∥\|x\|. Its square ∥x∥22=x⊤x\|x\|_2^2=x^\top x is easier to differentiate and appears in mean-squared-error losses and weight decay.
  • ∥x∥1=∑i∣xi∣\|x\|_1=\sum_i|x_i| grows at the same rate everywhere, even near zero. That makes it useful when the difference between exactly zero and slightly nonzero matters, which is why L1L^1 penalties encourage sparse solutions.
  • ∥x∥∞=max⁡i∣xi∣\|x\|_\infty=\max_i|x_i|, the max norm, is the size of the largest entry. Adversarial-robustness work often bounds perturbations in this norm.
  • The count of nonzero entries is sometimes called the ”L0L^0 norm”, but it is not a norm: scaling xx by 2 does not change it.

The dot product connects to the Euclidean norm through angles: x⊤y=∥x∥2∥y∥2cos⁡θx^\top y=\|x\|_2\|y\|_2\cos\theta, where θ\theta is the angle between xx and yy. The cosine similarity

cos⁡(x,y)=x⊤y∥x∥2∥y∥2\cos(x,y)=\frac{x^\top y}{\|x\|_2\|y\|_2}

is defined for nonzero vectors and ignores scale. That is useful for some embeddings (contrastive learning normalizes features for this reason) and wrong when magnitude carries meaning, such as image brightness.

Matrix norms

For matrices we use two norms constantly. The Frobenius norm treats the matrix as one long vector,

∥A∥F=∑i,jAij2.\|A\|_F=\sqrt{\sum_{i,j}A_{ij}^2}.

The spectral norm (operator 2-norm) measures the largest factor by which AA can stretch a unit vector,

∥A∥2=max⁡∥x∥2=1∥Ax∥2=σmax⁡(A),\|A\|_2=\max_{\|x\|_2=1}\|Ax\|_2=\sigma_{\max}(A),

where σmax⁡(A)\sigma_{\max}(A) is the largest singular value, defined in the SVD section below. In terms of all singular values σ1≥σ2≥…\sigma_1\ge\sigma_2\ge\dots, we have ∥A∥F2=∑iσi2\|A\|_F^2=\sum_i\sigma_i^2 while ∥A∥2=σ1\|A\|_2=\sigma_1. So many small singular values can make the Frobenius norm large without changing the largest amplification. The spectral norm bounds how much a layer can magnify a perturbation of its input, which is why it appears in robustness and GAN-stability work [17].

Code · Python · 13 lines
import numpy as np

x = np.array([3.0, -4.0, 0.0, 1.0])
for p in [1, 2, np.inf]:
    print(f"L{p} norm:", np.linalg.norm(x, p))
print("L0 'norm' (count of nonzeros):", np.count_nonzero(x))

A = np.array([[3.0, 0.0], [4.0, 5.0]])
s = np.linalg.svd(A, compute_uv=False)
print("singular values:", s.round(4))
print("Frobenius:", np.linalg.norm(A, "fro"), "=", np.sqrt((s**2).sum()))
print("spectral :", np.linalg.norm(A, 2), "=", s[0])
assert np.isclose(np.linalg.norm(A, "fro")**2, np.trace(A.T @ A))

For x=(3,−4,0,1)x=(3,-4,0,1) this prints L1=8L^1=8, L2=26≈5.10L^2=\sqrt{26}\approx5.10, L∞=4L^\infty=4 and three nonzeros. For the 2×22\times2 matrix the singular values are 35≈6.713\sqrt5\approx6.71 and 5≈2.24\sqrt5\approx2.24, giving ∥A∥F=50≈7.07\|A\|_F=\sqrt{50}\approx7.07 and ∥A∥2≈6.71\|A\|_2\approx6.71.

Special kinds of matrices and vectors

Plain version. Some matrices are much easier to work with than others. Learning to spot them saves computation and explains many design choices.

  • A diagonal matrix D=diag⁡(v)D=\operatorname{diag}(v) has nonzero entries only on its main diagonal. Multiplying by it scales each coordinate: diag⁡(v)x=v⊙x\operatorname{diag}(v)x=v\odot x. Its inverse, when every vi≠0v_i\ne0, is diag⁡(1/v1,…,1/vn)\operatorname{diag}(1/v_1,\dots,1/v_n). Per-channel scaling in normalization layers is a diagonal matrix in disguise. Rectangular diagonal matrices also exist; they appear in the SVD.
  • A symmetric matrix satisfies A=A⊤A=A^\top. Covariance matrices, Gram matrices X⊤XX^\top X, Hessians of smooth functions and distance matrices are symmetric.
  • A unit vector has ∥x∥2=1\|x\|_2=1. Two vectors are orthogonal if x⊤y=0x^\top y=0; if they are also unit vectors, they are orthonormal.
  • An orthogonal matrix QQ is square with orthonormal rows and columns, so Q⊤Q=QQ⊤=IQ^\top Q=QQ^\top=I and Q−1=Q⊤Q^{-1}=Q^\top. Its inverse is free to compute. It preserves lengths and angles, ∥Qx∥2=∥x∥2\|Qx\|_2=\|x\|_2, so geometrically it is a rotation, a reflection, or both.

If Q∈Rn×kQ\in\mathbb R^{n\times k} has k<nk\lt n orthonormal columns, then Q⊤Q=IkQ^\top Q=I_k but QQ⊤≠InQQ^\top\ne I_n. The matrix P=QQ⊤P=QQ^\top is the orthogonal projection onto the span of the columns of QQ. The projection PxPx is the closest point to xx in that subspace, and the residual x−Pxx-Px is perpendicular to every column of QQ. Projecting twice changes nothing: P2=PP^2=P. PCA, below, is exactly the search for the best such QQ.

Eigendecomposition

Plain version. A real eigenvector stays on the same line after transformation. Its eigenvalue sets the scale and may reverse its direction.

An eigenvector of a square matrix A∈Rn×nA\in\mathbb R^{n\times n} is a nonzero vector vv with

Av=λv,Av=\lambda v,

where the scalar λ\lambda is the corresponding eigenvalue. If vv is an eigenvector, so is cvcv for any c≠0c\ne0, so we usually normalize eigenvectors to unit length.

Suppose AA has nn linearly independent eigenvectors v(1),…,v(n)v^{(1)},\dots,v^{(n)} with eigenvalues λ1,…,λn\lambda_1,\dots,\lambda_n. Stack them as columns of VV and put the eigenvalues in Λ=diag⁡(λ1,…,λn)\Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_n). Then AV=VΛAV=V\Lambda, so

A=VΛV−1.A=V\Lambda V^{-1}.

This is the eigendecomposition. It says: change to eigenvector coordinates (V−1V^{-1}), scale each coordinate independently (Λ\Lambda), and change back (VV). Not every matrix has one. The shear [1101]\begin{bmatrix}1&1\\0&1\end{bmatrix} has only one independent eigenvector. A rotation by 90∘90^\circ has eigenvalues ±i\pm i, which are complex, because no real direction is left unturned.

The symmetric case

Symmetric matrices are the friendly case, and they are the ones ML meets most. The spectral theorem says that every real symmetric matrix can be written as

A=QΛQ⊤,A=Q\Lambda Q^\top,

where QQ is orthogonal (its columns are orthonormal eigenvectors) and Λ\Lambda is real and diagonal [3], [4]. Because Q−1=Q⊤Q^{-1}=Q^\top, no inversion is needed. Geometrically, AA stretches space by λi\lambda_i along the direction q(i)q^{(i)}, the ii-th column of QQ. The decomposition is unique up to the order of the eigenvalues and the choice of basis within any repeated eigenvalue; by convention we sort eigenvalues from largest to smallest.

For a symmetric AA, the quadratic form f(x)=x⊤Axf(x)=x^\top Ax restricted to unit vectors is bounded by the extreme eigenvalues:

λmin⁡≤x⊤Ax≤λmax⁡for ∥x∥2=1,\lambda_{\min}\le x^\top Ax\le\lambda_{\max}\qquad\text{for } \|x\|_2=1,

with the maximum reached at the top eigenvector and the minimum at the bottom one. The ratio x⊤Ax/x⊤xx^\top Ax/x^\top x is called the Rayleigh quotient. This fact is the engine of the PCA derivation later.

Positive definite matrices

The signs of the eigenvalues classify symmetric matrices:

NameEigenvaluesEquivalent condition
positive definite (PD)all λi>0\lambda_i\gt0x⊤Ax>0x^\top Ax\gt0 for every x≠0x\ne0
positive semidefinite (PSD)all λi≥0\lambda_i\ge0x⊤Ax≥0x^\top Ax\ge0 for every xx
negative (semi)definiteall λi<0\lambda_i\lt0 (or ≤0\le0)the reverse inequalities
indefiniteboth signs presentx⊤Axx^\top Ax takes both signs

Every covariance matrix and every Gram matrix X⊤XX^\top X is PSD, because v⊤X⊤Xv=∥Xv∥22≥0v^\top X^\top Xv=\|Xv\|_2^2\ge0. A Gaussian density needs a PD covariance so that it can be inverted. The Hessian of a loss is PD at a strict local minimum and indefinite at a saddle point; ML 01C uses this to explain why optimization can be slow. A PD matrix has a Cholesky factorization A=LL⊤A=LL^\top with LL lower triangular, which is the fastest stable way to solve systems with it and to sample from a Gaussian [4].

Code · Python · 17 lines
import numpy as np

rng = np.random.default_rng(1)
M = rng.normal(size=(4, 4))
S = M @ M.T + 0.1 * np.eye(4)        # symmetric positive definite
lam, Q = np.linalg.eigh(S)           # ascending eigenvalues, orthonormal Q
assert np.allclose(Q @ np.diag(lam) @ Q.T, S)
assert np.allclose(Q.T @ Q, np.eye(4))
print("eigenvalues:", lam.round(3), "all positive:", bool((lam > 0).all()))

# The quadratic form x^T S x is bounded by the extreme eigenvalues
x = rng.normal(size=4); x /= np.linalg.norm(x)
print("Rayleigh quotient in range:", lam[0] <= x @ S @ x <= lam[-1])

# A non-symmetric matrix can have complex eigenvalues
R = np.array([[0.0, -1.0], [1.0, 0.0]])  # 90-degree rotation
print("rotation eigenvalues:", np.linalg.eigvals(R))

Use np.linalg.eigh for symmetric matrices: it is faster, returns real eigenvalues in ascending order and orthonormal eigenvectors. np.linalg.eig handles the general case and may return complex numbers, as the rotation shows.

Singular value decomposition

Plain version. SVD decomposes a real matrix into orthogonal changes of coordinates and axis-wise scaling. Those coordinate changes may include reflections.

Eigendecomposition needs a square matrix and may not exist. The singular value decomposition always exists, for every real matrix A∈Rm×nA\in\mathbb R^{m\times n}:

A=UΣV⊤.A=U\Sigma V^\top.
  • U∈Rm×mU\in\mathbb R^{m\times m} is orthogonal. Its columns are the left singular vectors, directions in the output space.
  • Σ∈Rm×n\Sigma\in\mathbb R^{m\times n} is rectangular diagonal. Its diagonal entries σ1≥σ2≥⋯≥0\sigma_1\ge\sigma_2\ge\dots\ge0 are the singular values.
  • V∈Rn×nV\in\mathbb R^{n\times n} is orthogonal. Its columns are the right singular vectors, directions in the input space.

Read from right to left, Ax=UΣV⊤xAx=U\Sigma V^\top x first expresses xx in the VV coordinates (a rotation or reflection), then scales coordinate ii by σi\sigma_i, then places the result along the UU directions. Figure 1 shows this for a 2×22\times2 matrix: the unit circle becomes an ellipse whose semi-axes have lengths σ1\sigma_1 and σ2\sigma_2.

Four panels: a unit circle with two arrows; the circle after a rotation; an axis-aligned ellipse after stretching; the final tilted ellipse
Figure 1 — The SVD as rotate, stretch, rotate. The right singular vectors v1 and v2 (red, yellow) are first rotated onto the axes by V-transpose, stretched by the singular values, then rotated by U. The final ellipse is the image of the unit circle under A.

The SVD and eigendecomposition are closely related. Since A⊤A=VΣ⊤ΣV⊤A^\top A=V\Sigma^\top\Sigma V^\top and AA⊤=UΣΣ⊤U⊤AA^\top=U\Sigma\Sigma^\top U^\top, the right singular vectors are eigenvectors of A⊤AA^\top A, the left singular vectors are eigenvectors of AA⊤AA^\top, and σi=λi(A⊤A)\sigma_i=\sqrt{\lambda_i(A^\top A)}. For a symmetric PSD matrix, the SVD and the eigendecomposition coincide.

The number of nonzero singular values equals the rank rr. Keeping only those gives the compact (thin) SVD A=UrΣrVr⊤=∑i=1rσiu(i)v(i)⊤A=U_r\Sigma_rV_r^\top=\sum_{i=1}^r\sigma_iu^{(i)}v^{(i)\top}, a sum of rr rank-one matrices. That is the outer-product view of a matrix product again.

The best low-rank approximation

Truncating that sum after kk terms gives Ak=∑i=1kσiu(i)v(i)⊤A_k=\sum_{i=1}^k\sigma_iu^{(i)}v^{(i)\top}. The Eckart–Young theorem [6] says that AkA_k is the best rank-kk approximation of AA in the Frobenius norm:

min⁡rank⁡(B)≤k∥A−B∥F2=∥A−Ak∥F2=∑i>kσi2.\min_{\operatorname{rank}(B)\le k}\|A-B\|_F^2=\|A-A_k\|_F^2=\sum_{i\gt k}\sigma_i^2.

The same AkA_k is also optimal in the spectral norm, with error ∥A−Ak∥2=σk+1\|A-A_k\|_2=\sigma_{k+1} [4]. In words: throw away the smallest singular values, and the energy you lose is exactly what you threw away. Storing AkA_k needs k(m+n+1)k(m+n+1) numbers instead of mnmn.

Figure 2 applies this to a 256×256256\times256 grayscale photograph. Natural images have rapidly decaying singular values, so a rank-50 approximation already keeps the main structure. The streaky artifacts at low rank come from the fact that each rank-one term is an outer product of a column pattern and a row pattern.

Camera-man image approximated with rank 5, 20 and 50, the original, and a log-scale plot of singular values
Figure 2 — Rank-k approximations of the 256×256 'camera' image from scikit-image, with the relative Frobenius error in each title. Right: singular values on a log scale; dashed lines mark k = 5, 20, 50. The error of each approximation is set by the singular values to the right of its line.
Code · Python · 16 lines
import numpy as np

rng = np.random.default_rng(0)
A = rng.normal(size=(12, 8))
U, s, Vt = np.linalg.svd(A, full_matrices=False)
assert np.allclose(U @ np.diag(s) @ Vt, A)
k = 3
Ak = (U[:, :k] * s[:k]) @ Vt[:k]
err_F = np.linalg.norm(A - Ak, "fro")**2
err_2 = np.linalg.norm(A - Ak, 2)
assert np.isclose(err_F, (s[k:]**2).sum()) and np.isclose(err_2, s[k])
print("rank-k squared Frobenius error:", round(err_F, 3))
print("rank-k spectral error = sigma_{k+1}:", round(err_2, 3), round(s[k], 3))
# Eigenvalues of A^T A are squared singular values of A
assert np.allclose(np.sort(np.linalg.eigvalsh(A.T @ A))[::-1], s**2)
print("storage: full", A.size, "numbers; rank-3 factors", k * (12 + 8 + 1))

full_matrices=False returns the thin SVD, which is what you almost always want. (U[:, :k] * s[:k]) scales the columns of UU by broadcasting instead of building a diagonal matrix. Both Eckart–Young identities hold to machine precision.

One caveat: the directions with the largest singular values carry the most energy, not necessarily the most useful information. For classification, a small-variance direction can be the one that separates the classes. PR 05 contrasts PCA with discriminant methods for exactly this reason.

The Moore–Penrose pseudo-inverse

Plain version. When a matrix has no inverse, the pseudo-inverse gives the next best thing: the answer that fits the data as closely as possible, and among equally good answers, the smallest one.

Only square, full-rank matrices have inverses. For any A∈Rm×nA\in\mathbb R^{m\times n}, the Moore–Penrose pseudo-inverse A+∈Rn×mA^+\in\mathbb R^{n\times m} is the unique matrix satisfying the four Penrose conditions [7]:

AA+A=A,A+AA+=A+,(AA+)⊤=AA+,(A+A)⊤=A+A.AA^+A=A,\quad A^+AA^+=A^+,\quad (AA^+)^\top=AA^+,\quad (A^+A)^\top=A^+A.

It is easiest to compute from the SVD. If A=UΣV⊤A=U\Sigma V^\top, then

A+=VΣ+U⊤,A^+=V\Sigma^+U^\top,

where Σ+∈Rn×m\Sigma^+\in\mathbb R^{n\times m} is formed by transposing Σ\Sigma and replacing each nonzero singular value σi\sigma_i by 1/σi1/\sigma_i (zeros stay zero). Goodfellow et al. give the equivalent limit A+=lim⁡α↘0(A⊤A+αI)−1A⊤A^+=\lim_{\alpha\searrow0}(A^\top A+\alpha I)^{-1}A^\top [1], which already hints at ridge regression.

The pseudo-inverse gives the right answer in every regime of the rank table:

  • Tall, full column rank (m>nm\gt n). Ax=bAx=b usually has no exact solution. Then x=A+b=(A⊤A)−1A⊤bx=A^+b=(A^\top A)^{-1}A^\top b is the least-squares solution: it minimizes ∥Ax−b∥22\|Ax-b\|_2^2.
  • Wide, full row rank (m<nm\lt n). There are infinitely many solutions. Then x=A+b=A⊤(AA⊤)−1bx=A^+b=A^\top(AA^\top)^{-1}b is the solution with the smallest ∥x∥2\|x\|_2, the minimum-norm solution. Any other solution adds a null-space vector, which can only increase the norm.
  • Rank-deficient. A+bA^+b is both: among all least-squares minimizers, the one with the smallest norm.

The minimum-norm property is a small window into a modern question. Gradient descent on an under-determined least-squares problem, started from zero, converges to the minimum-norm solution, because every gradient A⊤(Ax−b)A^\top(Ax-b) lies in the row space of AA. Over-parameterized networks are not linear, but this simple case is the usual starting point for thinking about which of many perfect fits a training algorithm picks.

Least squares, the normal equations and conditioning

For a regression design matrix X∈Rn×dX\in\mathbb R^{n\times d} and targets y∈Rny\in\mathbb R^n, least squares minimizes ∥Xw−y∥22\|Xw-y\|_2^2. Setting the gradient to zero gives the normal equations

X⊤Xw=X⊤y.X^\top Xw=X^\top y.

These are correct but numerically risky. The sensitivity of a linear problem is measured by the condition number κ2(A)=σmax⁡/σmin⁡\kappa_2(A)=\sigma_{\max}/\sigma_{\min}. Roughly, relative errors in the data can be amplified by up to a factor κ\kappa in the solution [5]. Forming X⊤XX^\top X squares the condition number, κ(X⊤X)=κ(X)2\kappa(X^\top X)=\kappa(X)^2, so a mildly ill-conditioned problem becomes a severely ill-conditioned one. Library least-squares solvers (np.linalg.lstsq, torch.linalg.lstsq) work with QR or SVD factorizations of XX directly and avoid that squaring [4].

When two features are almost identical, σmin⁡\sigma_{\min} is tiny, and the individual coefficients become extremely sensitive even when predictions are fine. Ridge regression [8] adds a penalty λ∥w∥22\lambda\|w\|_2^2 with λ>0\lambda\gt0:

wridge=(X⊤X+λI)−1X⊤y=∑iσiσi2+λ (u(i)⊤y) v(i).w_{\text{ridge}}=(X^\top X+\lambda I)^{-1}X^\top y=\sum_i\frac{\sigma_i}{\sigma_i^2+\lambda}\,(u^{(i)\top}y)\,v^{(i)}.

The SVD form on the right shows what ridge does. Plain least squares uses the factor 1/σi1/\sigma_i, which explodes for small σi\sigma_i. Ridge uses σi/(σi2+λ)\sigma_i/(\sigma_i^2+\lambda), which stays bounded by 1/(2λ)1/(2\sqrt\lambda). Large-σ\sigma directions are nearly untouched; small-σ\sigma directions are suppressed. The price is bias. In neural networks the same penalty is called weight decay.

Code · Python · 28 lines
import numpy as np

rng = np.random.default_rng(0)
# Over-determined: more equations than unknowns -> least squares
x = np.linspace(-1, 1, 40)
X = np.c_[np.ones_like(x), x]
y = 2 + 3*x + rng.normal(0, .05, len(x))
w, residuals, rank, sv = np.linalg.lstsq(X, y, rcond=None)
print("intercept and slope:", w.round(3), "rank:", rank)
assert np.allclose(w, np.linalg.pinv(X) @ y)

# Under-determined: fewer equations than unknowns -> minimum-norm solution
A = rng.normal(size=(2, 5)); b = rng.normal(size=2)
w_min = np.linalg.pinv(A) @ b
null = np.linalg.svd(A)[2][-1]             # a direction with A @ null = 0
w_other = w_min + 0.7 * null
print("both solve Aw=b:", np.allclose(A @ w_min, b), np.allclose(A @ w_other, b))
print("norms:", np.linalg.norm(w_min).round(3), "<", np.linalg.norm(w_other).round(3))

# Near-collinear features: condition number and ridge
z = rng.normal(size=200)
F = np.c_[z, z + 1e-4 * rng.normal(size=200)]
t = z + 0.01 * rng.normal(size=200)
print("cond(F) = %.1e, cond(F^T F) = %.1e" % (np.linalg.cond(F), np.linalg.cond(F.T @ F)))
w_ls = np.linalg.lstsq(F, t, rcond=None)[0]
lam = 1e-2
w_ridge = np.linalg.solve(F.T @ F + lam * np.eye(2), F.T @ t)
print("least squares:", w_ls.round(2), " ridge:", w_ridge.round(3))

The line fit recovers intercept ≈2.00\approx2.00 and slope ≈3.01\approx3.01, and pinv agrees with lstsq. The under-determined system has two exact solutions; the pseudo-inverse one has the smaller norm (0.885 versus 1.128). In the collinear case, κ(F)≈2×104\kappa(F)\approx2\times10^4 while κ(F⊤F)≈4×108\kappa(F^\top F)\approx4\times10^8, its square. Least squares returns wild coefficients (−2.63, 3.63)(-2.63,\,3.63) whose sum is still about 1, so its predictions are fine. Ridge returns the stable split (0.5, 0.5)(0.5,\,0.5). The intercept column in the first example lets the line have a nonzero offset. In a real pipeline, fit any centering and scaling on the training set only, then apply it unchanged to validation and test data.

The trace operator

Plain version. The trace adds up the diagonal. It looks too simple to matter, but it lets you rewrite awkward sums as matrix expressions and move matrices around inside them.

The trace of a square matrix is

Tr⁡(A)=∑iAii.\operatorname{Tr}(A)=\sum_iA_{ii}.

Its useful properties are:

  • Frobenius norm. ∥A∥F=Tr⁡(AA⊤)=Tr⁡(A⊤A)\|A\|_F=\sqrt{\operatorname{Tr}(AA^\top)}=\sqrt{\operatorname{Tr}(A^\top A)}.
  • Transpose. Tr⁡(A)=Tr⁡(A⊤)\operatorname{Tr}(A)=\operatorname{Tr}(A^\top).
  • Cyclic property. Tr⁡(ABC)=Tr⁡(CAB)=Tr⁡(BCA)\operatorname{Tr}(ABC)=\operatorname{Tr}(CAB)=\operatorname{Tr}(BCA) whenever the products are defined, even when the matrices are not square and the intermediate products have different shapes. In particular Tr⁡(AB)=Tr⁡(BA)\operatorname{Tr}(AB)=\operatorname{Tr}(BA) for A∈Rm×nA\in\mathbb R^{m\times n}, B∈Rn×mB\in\mathbb R^{n\times m}. You may cycle, but not arbitrarily reorder: Tr⁡(ABC)≠Tr⁡(ACB)\operatorname{Tr}(ABC)\ne\operatorname{Tr}(ACB) in general.
  • Scalars. A scalar is its own trace, a=Tr⁡(a)a=\operatorname{Tr}(a). This turns a quadratic form into a trace: x⊤Ax=Tr⁡(x⊤Ax)=Tr⁡(Axx⊤)x^\top Ax=\operatorname{Tr}(x^\top Ax)=\operatorname{Tr}(Axx^\top).
  • Eigenvalues. Tr⁡(A)=∑iλi\operatorname{Tr}(A)=\sum_i\lambda_i. For a covariance matrix, that is the total variance, the sum of the variances along every principal direction.

The scalar trick is how many expectations are evaluated. For a random vector xx with mean zero and covariance Σ\Sigma, E[x⊤Ax]=E[Tr⁡(Axx⊤)]=Tr⁡(AΣ)\mathbb E[x^\top Ax]=\mathbb E[\operatorname{Tr}(Axx^\top)]=\operatorname{Tr}(A\Sigma), because trace and expectation are both linear.

The determinant

Plain version. The absolute determinant gives volume scaling; its sign records orientation. A zero determinant means a square matrix collapses a dimension and is not invertible.

The determinant det⁡(A)\det(A) of a square matrix is a single number with these properties:

  • det⁡(A)=∏iλi\det(A)=\prod_i\lambda_i, the product of the eigenvalues.
  • ∣det⁡(A)∣|\det(A)| is the factor by which AA scales volume. The unit cube maps to a parallelepiped of volume ∣det⁡(A)∣|\det(A)|.
  • The sign records orientation. A negative determinant means AA includes a reflection.
  • det⁡(A)=0\det(A)=0 exactly when AA is singular: some direction is collapsed to zero, so information is lost.
  • det⁡(AB)=det⁡(A)det⁡(B)\det(AB)=\det(A)\det(B), det⁡(A⊤)=det⁡(A)\det(A^\top)=\det(A), and det⁡(A−1)=1/det⁡(A)\det(A^{-1})=1/\det(A).
Four panels showing the unit square mapped by the identity, a stretch-and-shear, a reflection and a singular matrix, with determinants 1, 2, -1 and 0
Figure 3 — The determinant as signed area. Dashed: the unit square. Shaded: its image, spanned by Ae1 (red) and Ae2 (yellow). A shear does not change area; a reflection flips the sign; a singular matrix collapses the square onto a line (det = 0).

Determinants appear in machine learning in two main places. The multivariate Gaussian density contains det⁡(Σ)−1/2\det(\Sigma)^{-1/2}, the volume normalization of the covariance; ML 01B uses it. Normalizing flows (ML 07) need log⁡∣det⁡J∣\log|\det J| of a Jacobian matrix JJ to account for how an invertible network stretches probability mass. In both cases you need the logarithm, never the raw value: the determinant of a 500×500500\times500 diagonal matrix with entries 10−310^{-3} is 10−150010^{-1500}, which underflows to zero in float64.

Code · Python · 19 lines
import numpy as np

rng = np.random.default_rng(2)
A, B, C = rng.normal(size=(3, 4)), rng.normal(size=(4, 5)), rng.normal(size=(5, 3))
print("cyclic trace:", np.isclose(np.trace(A @ B @ C), np.trace(C @ A @ B)),
      np.isclose(np.trace(A @ B @ C), np.trace(B @ C @ A)))

S = rng.normal(size=(4, 4))
lam = np.linalg.eigvals(S)
print("trace = sum of eigenvalues:", np.isclose(np.trace(S), lam.sum().real))
print("det = product of eigenvalues:", np.isclose(np.linalg.det(S), np.prod(lam).real))

# log-determinant of a covariance without overflow/underflow
Sigma = np.diag(np.full(500, 1e-3))
print("det underflows:", np.linalg.det(Sigma))
sign, logdet = np.linalg.slogdet(Sigma)
print("slogdet:", sign, round(logdet, 2))
L = np.linalg.cholesky(Sigma)
print("via Cholesky:", round(2 * np.log(np.diag(L)).sum(), 2))

The direct determinant prints 0.0, while slogdet and the Cholesky route both give log⁡det⁡=500log⁡10−3≈−3453.88\log\det=500\log10^{-3}\approx-3453.88. For a PD matrix, det⁡(A)=∏iLii2\det(A)=\prod_iL_{ii}^2 when A=LL⊤A=LL^\top, so log⁡det⁡A=2∑ilog⁡Lii\log\det A=2\sum_i\log L_{ii}.

Worked example: deriving principal component analysis

Plain version. PCA looks for the flat subspace that the data cloud lies closest to. Projecting onto it compresses each point to a few numbers while losing as little as possible.

PCA goes back to Pearson’s “lines and planes of closest fit” [9] and Hotelling’s analysis of “principal components” [10]; Jolliffe and Cadima give a modern review [11]. We derive it in the style of [1], using only the tools above.

Setup. We have nn points x(1),…,x(n)∈Rdx^{(1)},\dots,x^{(n)}\in\mathbb R^d and want to store each one with only l<dl\lt d numbers. First subtract the mean μ=1n∑ix(i)\mu=\frac1n\sum_ix^{(i)} from every point, so we can assume the data are centered. Stack the centered points as rows of X∈Rn×dX\in\mathbb R^{n\times d}.

Step 1: choose the form of the code. We use a linear decoder g(c)=Dcg(c)=Dc with D∈Rd×lD\in\mathbb R^{d\times l}. To make the problem well-posed we require the columns of DD to be orthonormal, D⊤D=IlD^\top D=I_l. (Without this, we could shrink cc and enlarge DD forever.)

Step 2: find the best code for a fixed decoder. For a given xx, choose cc to minimize the reconstruction error:

c∗=arg⁡min⁡c∥x−Dc∥22=arg⁡min⁡c(−2x⊤Dc+c⊤D⊤Dc)=arg⁡min⁡c(−2x⊤Dc+c⊤c).c^*=\arg\min_c\|x-Dc\|_2^2=\arg\min_c\big(-2x^\top Dc+c^\top D^\top Dc\big)=\arg\min_c\big(-2x^\top Dc+c^\top c\big).

We expanded the square, dropped x⊤xx^\top x (it does not depend on cc) and used D⊤D=ID^\top D=I. The gradient with respect to cc is −2D⊤x+2c-2D^\top x+2c. Setting it to zero gives the encoder

f(x)=D⊤x.f(x)=D^\top x.

So encoding is a matrix–vector product, and the reconstruction is r(x)=g(f(x))=DD⊤xr(x)=g(f(x))=DD^\top x, the orthogonal projection of xx onto the span of DD.

Step 3: find the best decoder. Now choose DD to minimize the total reconstruction error over all points:

D∗=arg⁡min⁡D∥X−XDD⊤∥F2subject to D⊤D=Il.D^*=\arg\min_D\|X-XDD^\top\|_F^2\quad\text{subject to } D^\top D=I_l.

Start with l=1l=1, so DD is a single unit vector dd. Write the Frobenius norm as a trace and expand:

∥X−Xdd⊤∥F2=Tr⁡((X−Xdd⊤)⊤(X−Xdd⊤))=Tr⁡(X⊤X)−2Tr⁡(X⊤Xdd⊤)+Tr⁡(dd⊤X⊤Xdd⊤)=Tr⁡(X⊤X)−2 d⊤X⊤Xd+d⊤X⊤Xd (d⊤d)=Tr⁡(X⊤X)−d⊤X⊤Xd.\begin{aligned} \|X-Xdd^\top\|_F^2 &=\operatorname{Tr}\big((X-Xdd^\top)^\top(X-Xdd^\top)\big)\\ &=\operatorname{Tr}(X^\top X)-2\operatorname{Tr}(X^\top Xdd^\top)+\operatorname{Tr}(dd^\top X^\top Xdd^\top)\\ &=\operatorname{Tr}(X^\top X)-2\,d^\top X^\top Xd+d^\top X^\top Xd\,(d^\top d)\\ &=\operatorname{Tr}(X^\top X)-d^\top X^\top Xd. \end{aligned}

The cyclic property moved d⊤d^\top to the front in the second and third terms, and d⊤d=1d^\top d=1 simplified the last line. The first term does not depend on dd. So minimizing the error is the same as

d∗=arg⁡max⁡d  d⊤X⊤Xdsubject to d⊤d=1.d^*=\arg\max_d\; d^\top X^\top Xd\quad\text{subject to } d^\top d=1.

That is a Rayleigh quotient of the symmetric PSD matrix X⊤XX^\top X. By the eigendecomposition section, it is maximized by the eigenvector of X⊤XX^\top X with the largest eigenvalue.

Step 4: more than one component. Repeating the argument for general ll (for example, by induction, requiring each new direction to be orthogonal to the previous ones) gives the answer: the columns of DD are the eigenvectors of X⊤XX^\top X for the ll largest eigenvalues [1]. The minimum error equals the sum of the discarded eigenvalues.

Step 5: the variance view and the SVD link. Dividing by nn turns X⊤XX^\top X into the sample covariance S=1nX⊤XS=\frac1nX^\top X (some texts use n−1n-1). The quantity d⊤Sdd^\top Sd is the variance of the projected data XdXd. So “minimize reconstruction error” and “maximize retained variance” select the same directions: Pearson’s and Hotelling’s views agree. Finally, if the centered data matrix has thin SVD X=UΣV⊤X=U\Sigma V^\top, then X⊤X=VΣ2V⊤X^\top X=V\Sigma^2V^\top. The principal directions are the right singular vectors VV, the eigenvalues are σi2\sigma_i^2, and the codes are XVl=UlΣlXV_l=U_l\Sigma_l. In practice PCA is computed with the SVD of XX rather than by forming the covariance, for the conditioning reason we met in least squares.

Left: correlated 2-D points with two principal axes drawn from the mean. Right: points projected onto the first principal axis, with gray residual segments
Figure 4 — PCA on 300 correlated 2-D points. Left: principal axes from the eigendecomposition of the sample covariance, drawn with length 2√λ. Right: a 1-D PCA reconstruction decode(encode(x)); each gray residual meets the red line at a right angle, because the reconstruction is an orthogonal projection.
Code · Python · 26 lines
import numpy as np

rng = np.random.default_rng(0)
n, d, l = 500, 5, 2
Z = rng.normal(size=(n, l))
X = Z @ rng.normal(size=(l, d)) + 0.1 * rng.normal(size=(n, d)) + 3.0

mu = X.mean(axis=0)
Xc = X - mu                                  # centre first
S = Xc.T @ Xc / n                            # sample covariance (d x d)
lam, Q = np.linalg.eigh(S)
lam, Q = lam[::-1], Q[:, ::-1]               # descending
D = Q[:, :l]                                 # decoder matrix, orthonormal columns

codes = Xc @ D                               # encode: f(x) = D^T (x - mu)
X_hat = codes @ D.T + mu                     # decode: g(c) = D c + mu
mse = np.mean(np.sum((X - X_hat)**2, axis=1))
print("explained variance ratio:", (lam[:l].sum() / lam.sum()).round(4))
print("reconstruction MSE:", mse.round(5), " sum of discarded eigenvalues:", lam[l:].sum().round(5))
assert np.isclose(mse, lam[l:].sum())

# Same subspace from the SVD of the centred data matrix
U, s, Vt = np.linalg.svd(Xc, full_matrices=False)
assert np.allclose(s[:l]**2 / n, lam[:l])
assert np.allclose(np.abs(Vt[:l] @ D), np.eye(l), atol=1e-8)
print("SVD and eigendecomposition agree")

The synthetic data are 5-D points that really live near a 2-D plane, plus small noise. Two components explain 99.36% of the variance, and the average squared reconstruction error equals the sum of the three discarded eigenvalues, exactly as Step 4 predicts. The SVD route finds the same directions (up to sign, which is arbitrary for eigenvectors).

Three practical notes. Always center the data, or the first “component” just points at the mean. Standardize features if they have incomparable units, because PCA is not scale-invariant. And fit the mean and directions on training data only. PCA is the linear ancestor of autoencoders; ML 06A develops the probabilistic version and its nonlinear successors.

Optional: PCA (in the Paper guides). Read the original figure, evidence, design choices and limitations.

Matrix calculus you will meet

Plain version. Training means following gradients, and most gradients in ML are a handful of matrix formulas used over and over.

For a scalar function f(x)f(x) of a vector x∈Rnx\in\mathbb R^n, the gradient ∇xf∈Rn\nabla_xf\in\mathbb R^n collects the partial derivatives ∂f/∂xi\partial f/\partial x_i. For a vector function f:Rn→Rmf:\mathbb R^n\to\mathbb R^m, the Jacobian J∈Rm×nJ\in\mathbb R^{m\times n} has entries Jij=∂fi/∂xjJ_{ij}=\partial f_i/\partial x_j. The rules you will use most are:

FunctionGradientNote
a⊤xa^\top xaalinear function
x⊤Axx^\top Ax(A+A⊤)x(A+A^\top)xbecomes 2Ax2Ax when AA is symmetric
12∥Xw−y∥22\tfrac12\|Xw-y\|_2^2X⊤(Xw−y)X^\top(Xw-y)least-squares loss
∥x∥22\|x\|_2^22x2xweight decay
Tr⁡(AB)\operatorname{Tr}(AB) w.r.t. AAB⊤B^\topused with the trace tricks above

Each can be verified by writing the expression as a sum over indices and differentiating term by term [2]. The chain rule for vector functions multiplies Jacobians: if y=g(x)y=g(x) and L=f(y)L=f(y) is a scalar, then ∇xL=Jg⊤∇yL\nabla_xL=J_g^\top\nabla_yL. Backpropagation applies this rule layer by layer, multiplying transposed local Jacobians by the incoming gradient without ever building the full Jacobians, which would be enormous. ML 02 builds this up in detail, and ML 01C adds the Hessian, the matrix of second derivatives.

Setting the least-squares gradient to zero recovers the normal equations from the previous section. The Hessian of that loss is X⊤XX^\top X, which is PSD, so the loss is convex and every stationary point is a global minimum. A quick finite-difference check confirms the formula:

Code · Python · 13 lines
import numpy as np

rng = np.random.default_rng(3)
X, y = rng.normal(size=(30, 4)), rng.normal(size=30)
w = rng.normal(size=4)
L = lambda w: 0.5 * np.sum((X @ w - y)**2)
grad = X.T @ (X @ w - y)                    # analytic gradient
eps = 1e-6
num = np.array([(L(w + eps*e) - L(w - eps*e)) / (2*eps) for e in np.eye(4)])
print("max gradient mismatch:", np.abs(grad - num).max())
# Setting the gradient to zero gives the normal equations
w_star = np.linalg.lstsq(X, y, rcond=None)[0]
print("gradient at solution ~ 0:", np.abs(X.T @ (X @ w_star - y)).max() < 1e-10)

The analytic and numerical gradients agree to about 10−810^{-8}, the size expected from finite-difference rounding.

Modern view

The definitions in this chapter are a century old, but the way they are used in machine learning keeps changing. Four lines of work are worth knowing about.

Randomized numerical linear algebra. Exact SVDs of large matrices are expensive, roughly O(mnmin⁡(m,n))O(mn\min(m,n)) operations. Halko, Martinsson and Tropp’s SIAM Review survey [12] made a simple idea standard: multiply AA by a thin random matrix Ω\Omega to “sketch” its range, orthonormalize the result to get a basis QQ, and compute an exact SVD of the small matrix Q⊤AQ^\top A. With a little oversampling and a few power iterations, the result is accurate for matrices whose spectrum decays. Martinsson and Tropp’s Acta Numerica survey [13] covers the theory and a wide range of algorithms: norm estimation, random embeddings, regression, low-rank approximation, Nyström approximation of PSD matrices, streaming algorithms and kernel matrices from machine learning. Murray et al. [14] (LAPACK Working Note 299, 2023) take the software view. They note that RandNLA methods have entered MATLAB, the NAG Library, NVIDIA’s cuSOLVER and scikit-learn, and they argue for standard “RandBLAS” and “RandLAPACK” libraries. scikit-learn’s randomized PCA solver is a direct descendant. The core algorithm fits in a few lines:

Code · Python · 21 lines
import numpy as np

def randomized_svd(A, k, oversample=10, power_iters=2, seed=0):
    rng = np.random.default_rng(seed)
    Omega = rng.normal(size=(A.shape[1], k + oversample))  # random test matrix
    Y = A @ Omega                                          # sample the range of A
    for _ in range(power_iters):                           # sharpen a slow spectrum
        Y = A @ (A.T @ Y)
    Q, _ = np.linalg.qr(Y)                                 # orthonormal basis
    B = Q.T @ A                                            # small (k+p) x n matrix
    Ub, s, Vt = np.linalg.svd(B, full_matrices=False)
    return (Q @ Ub)[:, :k], s[:k], Vt[:k]

rng = np.random.default_rng(1)
m, n, r = 2000, 500, 20
A = rng.normal(size=(m, r)) @ rng.normal(size=(r, n)) + 0.01 * rng.normal(size=(m, n))
U, s, Vt = randomized_svd(A, k=r)
s_exact = np.linalg.svd(A, compute_uv=False)[:r]
print("max relative error in top singular values:", np.max(np.abs(s - s_exact) / s_exact))
rel = np.linalg.norm(A - (U * s) @ Vt) / np.linalg.norm(A)
print("relative reconstruction error:", round(rel, 5))

On this nearly rank-20 matrix the top 20 singular values match the exact ones to about 10−1510^{-15} relative error, and the rank-20 reconstruction error (about 0.2%) is set by the added noise. The power iterations are what make it work when the spectrum decays slowly. For a matrix with a flat spectrum, no rank-kk method can do well, randomized or not.

Low-rank structure in large models. The outer-product view of matrix products has become a practical tool for adapting large networks. LoRA [15] freezes a pretrained weight W0∈Rd×kW_0\in\mathbb R^{d\times k} and learns an update ΔW=BA\Delta W=BA with B∈Rd×rB\in\mathbb R^{d\times r}, A∈Rr×kA\in\mathbb R^{r\times k} and r≪min⁡(d,k)r\ll\min(d,k). Only r(d+k)r(d+k) numbers are trained instead of dkdk; for d=k=4096d=k=4096 and r=8r=8, that is 65,536 instead of about 16.8 million per matrix. BB starts at zero, so training begins exactly at the pretrained model. GaLore [16] (ICML 2024) keeps all weights trainable but projects the gradients onto a low-rank subspace, which shrinks the optimizer’s memory. Its authors argue that restricting the weight update itself to a low-rank subspace, as LoRA does, can underperform full-rank training. Both rely on the Eckart–Young intuition that much of a matrix’s useful content lives in a few singular directions. Whether that holds for a given task is an empirical question, not a theorem.

Controlling the spectral norm. A network’s sensitivity to input perturbations is bounded by the product of its layers’ spectral norms (for 1-Lipschitz activations such as ReLU). Spectral normalization [17] divides each weight matrix by an estimate of its largest singular value, obtained cheaply with one step of power iteration per training step. It was introduced to stabilize the discriminator in GANs (ML 07), and the same idea appears wherever a Lipschitz bound is wanted.

Beyond matrices. Convolution kernels and video features are naturally tensors with three or more axes. Kolda and Bader’s SIAM Review survey [18] is the standard introduction to tensor decompositions. It covers the CP decomposition (a sum of rank-one tensors, generalizing the outer-product view) and the Tucker decomposition (a small core tensor multiplied by a matrix along each mode, generalizing the SVD). Unlike matrices, computing the rank of a tensor is hard in general, and best low-rank approximations need not exist. The clean Eckart–Young picture does not carry over. These decompositions are used to compress layers and to analyze multi-way data.

Open questions. Why do trained weight matrices often have rapidly decaying spectra, and how does that relate to generalization? How low can the rank of an adaptation be before quality drops, and does that depend on the task or the model? How should randomized algorithms be combined with low-precision hardware, where rounding errors are much larger than in float64? None of these have settled answers. The tools in this chapter are what you need to read the papers that study them. For broader textbook treatments that connect linear algebra to deep learning, see [1], [2] and [19].

Key takeaways

  • Name each axis and check shapes before multiplying or broadcasting arrays.
  • Rank and null space constrain possible solutions; use a linear solver instead of explicitly inverting a matrix to solve a system.
  • Real symmetric matrices admit an orthonormal eigenbasis; eigenvalue signs describe their quadratic forms.
  • Truncated SVD gives a best low-rank approximation under spectral or Frobenius error.
  • The pseudo-inverse selects the minimum-norm least-squares solution; small singular values can amplify noise.
  • PCA on centered data maximizes retained variance and minimizes squared reconstruction error for a fixed subspace dimension.

Exercises

  1. Shapes and bias. A batch has shape 32×6432\times64 and a weight matrix has shape 64×1064\times10. What shape should the bias have, and what goes wrong if you use a bias of shape (32,1)(32,1) instead?
Hint

A bias of shape (10,)(10,) broadcasts over the 32 rows: one offset per output unit, shared by every example. A (32,1)(32,1) bias broadcasts across the 10 columns, giving one offset per example. The code runs, but the “bias” now depends on the position of an example in the batch, which is meaningless and changes with batch size.

  1. Projection. Let Q∈Rn×kQ\in\mathbb R^{n\times k} have orthonormal columns and P=QQ⊤P=QQ^\top. Show that P2=PP^2=P, P⊤=PP^\top=P, and that x−Pxx-Px is orthogonal to every column of QQ. What are the eigenvalues of PP?
Hint

P2=Q(Q⊤Q)Q⊤=QIQ⊤=PP^2=Q(Q^\top Q)Q^\top=QIQ^\top=P. For orthogonality compute Q⊤(x−Px)=Q⊤x−Q⊤QQ⊤x=0Q^\top(x-Px)=Q^\top x-Q^\top QQ^\top x=0. From P2=PP^2=P, any eigenvalue satisfies λ2=λ\lambda^2=\lambda, so λ∈{0,1}\lambda\in\{0,1\}: eigenvalue 1 with multiplicity kk (the subspace) and 0 with multiplicity n−kn-k (its orthogonal complement). Hence Tr⁡(P)=k\operatorname{Tr}(P)=k.

  1. SVD by hand. Find the singular values of A=[3045]A=\begin{bmatrix}3&0\\4&5\end{bmatrix} by computing the eigenvalues of A⊤AA^\top A. Check that ∥A∥F2=σ12+σ22\|A\|_F^2=\sigma_1^2+\sigma_2^2 and ∣det⁡A∣=σ1σ2|\det A|=\sigma_1\sigma_2.
Hint

A⊤A=[25202025]A^\top A=\begin{bmatrix}25&20\\20&25\end{bmatrix} has eigenvalues 4545 and 55, so σ1=35\sigma_1=3\sqrt5, σ2=5\sigma_2=\sqrt5. Then σ12+σ22=50=9+16+25\sigma_1^2+\sigma_2^2=50=9+16+25, and σ1σ2=15=∣det⁡A∣=∣3⋅5−0⋅4∣\sigma_1\sigma_2=15=|\det A|=|3\cdot5-0\cdot4|. In general ∣det⁡A∣=∏iσi|\det A|=\prod_i\sigma_i for a square matrix, because ∣det⁡U∣=∣det⁡V∣=1|\det U|=|\det V|=1.

  1. Conditioning and ridge. Starting from the least-squares code, replace the second feature by an exact copy of the first. What does np.linalg.lstsq return, and why is it the minimum-norm solution? Then derive the SVD form of the ridge solution and show that each factor σ/(σ2+λ)\sigma/(\sigma^2+\lambda) is at most 1/(2λ)1/(2\sqrt\lambda).
Hint

With identical columns, the rank is 1 and the solution set is a line w1+w2=cw_1+w_2=c. lstsq uses the SVD and returns the pseudo-inverse solution, which splits the weight equally, w1=w2=c/2w_1=w_2=c/2, because that point on the line is closest to the origin. For the bound, maximize g(σ)=σ/(σ2+λ)g(\sigma)=\sigma/(\sigma^2+\lambda): g′(σ)=0g'(\sigma)=0 at σ=λ\sigma=\sqrt\lambda, giving g=1/(2λ)g=1/(2\sqrt\lambda).

  1. PCA error. Using the derivation in this chapter, show that the total reconstruction error of ll-component PCA equals ∑i>lλi(X⊤X)\sum_{i\gt l}\lambda_i(X^\top X), and that the fraction of variance retained is ∑i≤lλi/∑iλi\sum_{i\le l}\lambda_i/\sum_i\lambda_i. Then run PCA on sklearn.datasets.load_digits() and find the smallest ll that keeps 90% of the variance.
Hint

Write ∥X−XDD⊤∥F2=Tr⁡(X⊤X)−Tr⁡(D⊤X⊤XD)\|X-XDD^\top\|_F^2=\operatorname{Tr}(X^\top X)-\operatorname{Tr}(D^\top X^\top XD) (use D⊤D=ID^\top D=I and the cyclic property). With DD the top-ll eigenvectors, the second trace is ∑i≤lλi\sum_{i\le l}\lambda_i, and Tr⁡(X⊤X)=∑iλi\operatorname{Tr}(X^\top X)=\sum_i\lambda_i. For the digits, center the 1797×641797\times64 matrix, compute its singular values, and take the cumulative sum of σi2\sigma_i^2. Report your own number rather than trusting a quoted one.

  1. Determinants and volume. A 2×22\times2 matrix maps the unit square to a parallelogram with vertices 00, (2,1)(2,1), (1,3)(1,3) and (3,4)(3,4). Write down a matrix that does this, compute its determinant, and explain why a normalizing flow must track log⁡∣det⁡J∣\log|\det J| for every layer.
Hint

Put the edge vectors in the columns: A=[2113]A=\begin{bmatrix}2&1\\1&3\end{bmatrix}, with det⁡A=5\det A=5, so areas grow by a factor of 5. If a map stretches volume by 5, probability density must shrink by the same factor to keep total probability equal to 1. Stacking layers multiplies these factors, so their logarithms add, which is why flows sum log-determinants layer by layer.

Paper guides

1 paper guide, each on a page of its own.

Open the paper guides →

References

  1. I. Goodfellow, Y. Bengio and A. Courville, Deep Learning, MIT Press, 2016, ch. 2 “Linear Algebra”. Book
  2. M. P. Deisenroth, A. A. Faisal and C. S. Ong, Mathematics for Machine Learning, Cambridge University Press, 2020. Book
  3. G. Strang, Introduction to Linear Algebra, 6th ed., Wellesley-Cambridge Press, 2023. Book site
  4. G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013. DOI
  5. L. N. Trefethen and D. Bau III, Numerical Linear Algebra, SIAM, 1997. DOI
  6. C. Eckart and G. Young, “The Approximation of One Matrix by Another of Lower Rank,” Psychometrika, vol. 1, pp. 211–218, 1936. DOI
  7. R. Penrose, “A Generalized Inverse for Matrices,” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 51, pp. 406–413, 1955. DOI
  8. A. E. Hoerl and R. W. Kennard, “Ridge Regression: Biased Estimation for Nonorthogonal Problems,” Technometrics, vol. 12, pp. 55–67, 1970. DOI
  9. K. Pearson, “On Lines and Planes of Closest Fit to Systems of Points in Space,” The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, vol. 2, pp. 559–572, 1901. DOI
  10. H. Hotelling, “Analysis of a Complex of Statistical Variables into Principal Components,” Journal of Educational Psychology, vol. 24, pp. 417–441, 1933. DOI
  11. I. T. Jolliffe and J. Cadima, “Principal Component Analysis: A Review and Recent Developments,” Philosophical Transactions of the Royal Society A, vol. 374, 20150202, 2016. DOI
  12. N. Halko, P.-G. Martinsson and J. A. Tropp, “Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions,” SIAM Review, vol. 53, no. 2, pp. 217–288, 2011. DOI · arXiv
  13. P.-G. Martinsson and J. A. Tropp, “Randomized Numerical Linear Algebra: Foundations and Algorithms,” Acta Numerica, vol. 29, pp. 403–572, 2020. DOI · arXiv
  14. R. Murray, J. Demmel, M. W. Mahoney, N. B. Erichson, M. Melnichenko, O. A. Malik, L. Grigori, P. Luszczek, M. Dereziński, M. E. Lopes, T. Liang, H. Luo and J. Dongarra, “Randomized Numerical Linear Algebra: A Perspective on the Field With an Eye to Software,” LAPACK Working Note 299, 2023. arXiv
  15. E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang and W. Chen, “LoRA: Low-Rank Adaptation of Large Language Models,” in Proc. International Conference on Learning Representations (ICLR), 2022. arXiv
  16. J. Zhao, Z. Zhang, B. Chen, Z. Wang, A. Anandkumar and Y. Tian, “GaLore: Memory-Efficient LLM Training by Gradient Low-Rank Projection,” ICML, 2024. arXiv
  17. T. Miyato, T. Kataoka, M. Koyama and Y. Yoshida, “Spectral Normalization for Generative Adversarial Networks,” ICLR, 2018. arXiv
  18. T. G. Kolda and B. W. Bader, “Tensor Decompositions and Applications,” SIAM Review, vol. 51, no. 3, pp. 455–500, 2009. DOI
  19. C. M. Bishop and H. Bishop, Deep Learning: Foundations and Concepts, Springer, 2024. Book

Check your understanding

This tutorial has 6 exercises. Can you solve them without opening the hints?

Go to the exercises ↑

Next ML 01B · Probability and Information Theory · 27 min