Linear Algebra for Machine Learning

Everything later in this laboratory is written in the language of this page. A concentration inequality for random matrices is a statement about $\|A\|$; a convergence rate for gradient descent is a statement about $\lambda_{\max}(\nabla^2 f)$ and $\lambda_{\min}(\nabla^2 f)$; the kernel trick is a statement about Gram matrices; attention is a statement about the geometry of inner products. This page fixes notation and proves the five or six facts that get used without comment from here on.

Inner products, norms and orthogonality

We work in $\R^d$ with the standard inner product $\ip{x}{y} = \sum_{i=1}^d x_i y_i = x^\top y$ and the Euclidean norm $\norm{x}_2 = \sqrt{\ip{x}{x}}$.

DefinitionNorms on vectors

For $p \in [1,\infty)$ the $\ell^p$ norm is $\norm{x}_p = \left(\sum_i |x_i|^p\right)^{1/p}$, and $\norm{x}_\infty = \max_i |x_i|$. Each satisfies

• $\norm{x} \ge 0$, with $\norm{x} = 0$ only for $x = 0$ (positivity),
• $\norm{cx} = |c|\,\norm{x}$ (homogeneity),
• $\norm{x+y} \le \norm{x} + \norm{y}$ (triangle inequality).

Only $p=2$ comes from an inner product, which is why the Euclidean norm is the one with a geometry — angles, projections, orthogonality — attached to it.

TheoremCauchy–Schwarz inequality

For all $x, y \in \R^d$,

$$|\ip{x}{y}| \le \norm{x}_2 \norm{y}_2 ,$$

with equality if and only if $x$ and $y$ are linearly dependent.

ProofReveal

The Cauchy–Schwarz inequality is what lets us define the angle $\theta$ between non-zero vectors through $\cos\theta = \ip{x}{y}/(\norm{x}_2\norm{y}_2) \in [-1,1]$. Two vectors are orthogonal when $\ip{x}{y}=0$. A set $\{u_1,\dots,u_k\}$ is orthonormal when $\ip{u_i}{u_j} = \delta_{ij}$.

Orthogonal projection

TheoremOrthogonal projection onto a subspace

Let $V \subseteq \R^d$ be a subspace with orthonormal basis $u_1,\dots,u_k$, and let $P = \sum_{i=1}^k u_i u_i^\top$. Then for every $x \in \R^d$:

1. $Px \in V$ and $x - Px \perp V$;
2. the decomposition $x = Px + (x - Px)$ into a $V$-component and a $V^\perp$-component is unique;
3. $Px = \argmin_{v \in V} \norm{x - v}_2$, and $\norm{x}_2^2 = \norm{Px}_2^2 + \norm{x-Px}_2^2$;
4. $P = P^\top = P^2$, and $\norm{P} = 1$ unless $V = \{0\}$.

ProofReveal

The spectral theorem

Write $\mathbb{S}^d$ for the set of real symmetric $d \times d$ matrices.

TheoremSpectral theorem for real symmetric matrices

Let $A \in \mathbb{S}^d$. Then there exist real numbers $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_d$ and an orthonormal basis $u_1,\dots,u_d$ of $\R^d$ with $Au_i = \lambda_i u_i$. Equivalently $A = U\Lambda U^\top$ with $U$ orthogonal and $\Lambda = \diag(\lambda_1,\dots,\lambda_d)$, equivalently $A = \sum_{i=1}^d \lambda_i u_i u_i^\top$.

ProofReveal

PropositionRayleigh quotient characterisation of eigenvalues

For $A \in \mathbb{S}^d$ and $x \ne 0$ define the Rayleigh quotient $R_A(x) = \dfrac{x^\top A x}{x^\top x}$. Then

$$\lambda_{\max}(A) = \max_{x \ne 0} R_A(x), \qquad \lambda_{\min}(A) = \min_{x \ne 0} R_A(x),$$

and more generally $\lambda_k(A) = \max_{\dim V = k}\ \min_{0 \ne x \in V} R_A(x)$ (the Courant–Fischer min–max characterisation).

ProofReveal

Positive semidefinite matrices and quadratic forms

DefinitionPositive semidefinite and positive definite

$A \in \mathbb{S}^d$ is positive semidefinite (PSD), written $A \succeq 0$, if $x^\top A x \ge 0$ for all $x$, and positive definite (PD), written $A \succ 0$, if $x^\top A x > 0$ for all $x \ne 0$. We write $A \succeq B$ for $A - B \succeq 0$; this is the Loewner order, a partial order — not every pair of symmetric matrices is comparable.

PropositionCharacterisations of positive semidefiniteness

For $A \in \mathbb{S}^d$ the following are equivalent:

1. $x^\top A x \ge 0$ for all $x \in \R^d$;
2. every eigenvalue of $A$ is non-negative;
3. $A = B^\top B$ for some matrix $B$;
4. $A = \sum_{i=1}^r \sigma_i v_i v_i^\top$ for some $r \le d$, $\sigma_i > 0$ and orthonormal $v_i$.

ProofReveal

Statement (3) is why PSD matrices are unavoidable in learning theory: every Gram matrix $K_{ij} = \ip{\phi(x_i)}{\phi(x_j)}$ is of the form $B^\top B$ and therefore PSD, and conversely every PSD matrix is a Gram matrix of some feature map. That equivalence is Mercer's condition in miniature.

DefinitionSquare root and Cholesky factor

For $A \succeq 0$ with spectral decomposition $U\Lambda U^\top$, the matrix $A^{1/2} := U \Lambda^{1/2} U^\top$ is the unique PSD matrix with $(A^{1/2})^2 = A$. If $A \succ 0$ it also has a unique factorisation $A = LL^\top$ with $L$ lower triangular and positive diagonal (the Cholesky factor), computable in $\tfrac13 d^3$ flops — which is how every "solve $(X^\top X + \lambda I)\beta = X^\top y$" in this laboratory is actually executed.

The singular value decomposition

TheoremSingular value decomposition

Every $A \in \R^{n \times p}$ can be written

$$A = U \Sigma V^\top = \sum_{i=1}^{r} \sigma_i u_i v_i^\top ,$$

where $r = \rank A$, $U \in \R^{n\times n}$ and $V \in \R^{p \times p}$ are orthogonal, and $\Sigma \in \R^{n \times p}$ is zero off the diagonal with $\sigma_1 \ge \dots \ge \sigma_{\min(n,p)} \ge 0$.

ProofReveal

Matrix norms

DefinitionOperator, Frobenius and nuclear norms

$$\norm{A} = \norm{A}_{2\to2} = \max_{\norm{x}_2 = 1}\norm{Ax}_2 = \sigma_1, \qquad \norm{A}_F = \sqrt{\sum_{i,j} A_{ij}^2} = \sqrt{\sum_i \sigma_i^2}, \qquad \norm{A}_* = \sum_i \sigma_i .$$

The first is the spectral (operator) norm, the second the Frobenius norm, the third the nuclear norm. All three are functions of the singular values alone, hence invariant under $A \mapsto QAR$ for orthogonal $Q,R$.

The inequalities

$$\norm{A} \le \norm{A}_F \le \sqrt{r}\,\norm{A}, \qquad \norm{A}_F \le \norm{A}_* \le \sqrt{r}\,\norm{A}_F$$

follow at once from $\sigma_1^2 \le \sum_i \sigma_i^2 \le r\sigma_1^2$ and Cauchy–Schwarz on the vector of singular values. They matter because the statistically natural norm is often $\norm{\cdot}_F$ while the analytically tractable one is $\norm{\cdot}$, and the conversion costs a $\sqrt{r}$ — a factor that is harmless for low-rank objects and fatal for full-rank ones in high dimension.

TheoremEckart–Young–Mirsky theorem

Let $A_k = \sum_{i=1}^k \sigma_i u_i v_i^\top$ be the rank-$k$ truncation of the SVD. Then for every matrix $B$ of rank at most $k$,

$$\norm{A - A_k} = \sigma_{k+1} \le \norm{A-B}, \qquad \norm{A-A_k}_F = \Big(\sum_{i>k}\sigma_i^2\Big)^{1/2} \le \norm{A-B}_F .$$

Proof (sketch)Reveal

This theorem is the reason principal component analysis is what it is: PCA is the Frobenius-optimal low-rank approximation of the centred data matrix, and nothing more.

Matrix calculus in one line each

The derivative conventions used throughout the optimisation pages are collected on the matrix calculus page. The three identities used most often are

$$\nabla_x (a^\top x) = a, \qquad \nabla_x (x^\top A x) = (A + A^\top)x, \qquad \nabla_x \tfrac12\norm{Ax-b}_2^2 = A^\top(Ax-b).$$

Problems

Equality in Cauchy–SchwarzProof · Beginner · 15 min Characterising orthogonal projectorsProof · Intermediate · 30 min Schur complement and block positive semidefinitenessProof · Advanced · 30 min Bounding the spectral norm by row and column sumsProof · Intermediate · 30 min Implement power iteration and verify the convergence rateCoding · Intermediate · 1 hour