Linear Algebra

TL;DR

1. Scalar product $⟨v,w⟩={\sum }_i{v}_i{w}_i$; norm $\Vert v\Vert =\sqrt{⟨v,v⟩}$; $⟨v,w⟩=0$ ⟺ orthogonal. Distance of $x$ to the hyperplane $\{⟨w,x⟩=0\}$: $|⟨w,x⟩|/\Vert w\Vert$.
2. Data matrix $X\in {\mathbb{R}}^{n\times d}$: one data point per row. $Xw$ = all predictions $⟨w,x_i⟩$; $X^{\top }v={\sum }_i{v}_i{x}_i$ is a combination of data points.
3. Rank = number of independent rows/columns. A square matrix is invertible iff it has full rank. $2\times 2$: ${\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)}^{-1}=\frac{1}{ad-bc}\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$.
4. Eigenvalues: $Av=\lambda v$. Symmetric matrices have real eigenvalues and orthogonal eigenvectors: $A={\sum }_i{\lambda }_i{v}_i{v}_i^{\top }$. PSD: all ${\lambda }_i\ge 0$ ⟺ $v^{\top }Av\ge 0$; $X^{\top }X$ and $X{X}^{\top }$ are always PSD.
5. Projection: $P^2=P$. Trace = sum of the diagonal = sum of the eigenvalues; $\mathrm{tr}(ABC)=\mathrm{tr}(CAB)$; the trace of a projection is its rank.

Source of the definitions: the course’s mathematical appendix. Everything below is in ${\mathbb{R}}^d$.

Vectors, scalar product, norms

Scalar product and norms

• $⟨v,w⟩=v^{\top }w={\sum }_{i=1}^d{v}_i{w}_i$.
• Euclidean norm $\Vert v{\Vert }_2=\sqrt{⟨v,v⟩}$ (the length). ${\ell }_1$ norm $\Vert v{\Vert }_1={\sum }_i|v_i|$ (lasso). ${\ell }_0$ “norm” $\Vert v{\Vert }_0$ = number of non-zero entries (sparsity).
• For unit vectors, $⟨v,w⟩=\cos \angle (v,w)$. $⟨v,w⟩=0$ ⟺ $v\perp w$.
• Cauchy-Schwarz: $|⟨v,w⟩|\le \Vert v\Vert \Vert w\Vert$.

Example: $v=(1,2)$, $w=(3,-1)$: $⟨v,w⟩=1$, $\Vert v\Vert =\sqrt{5}$, $\Vert v{\Vert }_1=3$.

Hyperplanes. $\{x:⟨w,x⟩=0\}$ is a line (in ${\mathbb{R}}^2$) or plane through the origin, with normal vector $w$. A linear classifier predicts $\mathrm{sign}⟨w,x⟩$: which side of the hyperplane $x$ lies on. The signed distance of a labeled point is $y⟨w,x⟩/\Vert w\Vert$ (L2).

Memory aid

$⟨w,x⟩$ measures “how much $x$ points in direction $w$“. Divide by $\Vert w\Vert$ to get a true distance. Scaling $w$ does not change the classifier, only the number $⟨w,x⟩$.

Matrices

Matrix products

$A\in {\mathbb{R}}^{m\times n}$, $B\in {\mathbb{R}}^{n\times k}$: $(AB{)}_{ij}={\sum }_l{A}_{il}{B}_{lj}$ (row $i$ of $A$ times column $j$ of $B$). Rules: $(AB{)}^{\top }=B^{\top }{A}^{\top }$; in general $AB\ne BA$.

The data matrix. $X\in {\mathbb{R}}^{n\times d}$ has the data points $x_1^{\top },\dots ,x_n^{\top }$ as rows. Then

• $Xw=(⟨x_1,w⟩,\dots ,⟨x_n,w⟩{)}^{\top }$: all predictions of the linear model at once.
• $X^{\top }v={\sum }_{i=1}^n{v}_i{x}_i$: a linear combination of the data points. This is why gradient descent on least squares stays in the span of the data (L8).
• $X{X}^{\top }\in {\mathbb{R}}^{n\times n}$ holds all scalar products $⟨x_i,x_j⟩$ (a kernel matrix); $X^{\top }X\in {\mathbb{R}}^{d\times d}$ is $n$ times the empirical covariance (for centered data).

Mini example

$X=\left(\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\end{array}\right)$: $X{X}^{\top }=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$ ($⟨x_1,x_1⟩=2$, $⟨x_1,x_2⟩=1$). $X^{\top }\left(\genfrac{}{}{0ex}{}{4/3}{-2/3}\right)=\frac{4}{3}{x}_1-\frac{2}{3}{x}_2=(\frac{4}{3},-\frac{2}{3},\frac{2}{3})$.

Rank, inverse, linear systems

Rank and inverse

• Rank = maximal number of linearly independent columns = rows = dimension of the image $\{Aw\}$.
• $A\in {\mathbb{R}}^{n\times n}$ is invertible ($A{A}^{-1}=A^{-1}A=I$) iff it has full rank $n$ iff $\det A\ne 0$ iff no eigenvalue is 0.
• $2\times 2$: ${\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)}^{-1}=\frac{1}{ad-bc}\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$.

Example: ${\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)}^{-1}=\frac{1}{3}\left(\begin{array}{cc}2& -1\\ -1& 2\end{array}\right)$.

Kernel (null space) and range

• $\ker X=\{v:Xv=0\}$: directions the data “does not see”. $\mathrm{range}(X^{\top })=\{X^{\top }\alpha \}$: the span of the data points.
• Every $w\in {\mathbb{R}}^d$ splits uniquely as $w=w_{\parallel }+w_{\perp }$ with $w_{\parallel }\in \mathrm{range}(X^{\top })$, $w_{\perp }\in \ker X$, and $w_{\parallel }\perp w_{\perp }$ (so $\Vert w{\Vert }^2=\Vert w_{\parallel }{\Vert }^2+\Vert w_{\perp }{\Vert }^2$, Pythagoras).

Linear systems $Xw=y$ ($n$ equations, $d$ unknowns):

• $n>d$, full column rank: usually no exact solution; least squares $w=(X^{\top }X{)}^{-1}{X}^{\top }y$ (L5).
• $n<d$, full row rank: infinitely many solutions $w_0+v$, $v\in \ker X$; the one with the smallest norm is $X^{\top }(X{X}^{\top }{)}^{-1}y$ (L8).

Memory aid

Tall matrix (more points than dimensions): too many equations, fit as well as possible. Wide matrix (more dimensions than points): too few equations, pick the shortest solution. $n=d$: exactly one solution, but fragile (the interpolation threshold).

Eigenvalues and eigenvectors

Eigenvalue

$v\ne 0$ is an eigenvector of $A\in {\mathbb{R}}^{n\times n}$ with eigenvalue $\lambda$ if $Av=\lambda v$: in direction $v$, $A$ only stretches by the factor $\lambda$. The eigenvalues are the roots of $\det (A-\lambda I)=0$.

$2\times 2$ by hand

$A=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$: $\det (A-\lambda I)=(2-\lambda {)}^2-1=0\Rightarrow \lambda \in \{1,3\}$, eigenvectors $(1,-1)$ and $(1,1)$. Shortcut for $2\times 2$: ${\lambda }_1+{\lambda }_2=\mathrm{tr}A=4$, ${\lambda }_1{\lambda }_2=\det A=3$.

Symmetric matrices ( $A=A^{\top }$)

Real eigenvalues, orthonormal eigenvectors, and the spectral decomposition

$$A=VD{V}^{\top }=\sum _{i=1}^n{\lambda }_i{v}_i{v}_i^{\top },A^{-1}=\sum _i\frac{1}{{\lambda }_i}{v}_i{v}_i^{\top }\text{(if all }{\lambda }_i\ne 0).$$

Functions act on the eigenvalues: $A^k$ has eigenvalues ${\lambda }_i^k$, $I-\eta A$ has $1-\eta {\lambda }_i$.

Where it appears: GD on least squares converges iff all $|1-\eta {\lambda }_i|<1$, i.e. $0<\eta <2/{\lambda }_{\max }$ (L8); ridge shrinks the directions with small eigenvalues most (L5); the covariance spectrum decides benign overfitting (L8).

Positive (semi-)definite

Symmetric $A$ is positive semi-definite (PSD) if all eigenvalues are $\ge 0$, equivalently $v^{\top }Av\ge 0$ for all $v$, equivalently $A=B{B}^{\top }$ for some $B$. Positive definite: $>0$, invertible. $X^{\top }X$ and $X{X}^{\top }$ are always PSD, because $v^{\top }{X}^{\top }Xv=\Vert Xv{\Vert }^2\ge 0$; $X^{\top }X+n\lambda I$ is positive definite for $\lambda >0$, which is why ridge always has a unique solution.

Memory aid

Eigenvalues are the stretch factors of $A$ in its own natural axes. Invertible = no stretch factor is 0. PSD = no direction gets flipped.

SVD and the generalized inverse

Singular value decomposition

Every $\Phi \in {\mathbb{R}}^{n\times d}$ is $\Phi =U\Sigma V^{\top }$ with orthogonal $U\in {\mathbb{R}}^{n\times n}$, $V\in {\mathbb{R}}^{d\times d}$ and a diagonal $\Sigma$ with the singular values ${\sigma }_i\ge 0$. The non-zero ${\sigma }_i^2$ are the non-zero eigenvalues of both ${\Phi }^{\top }\Phi$ and $\Phi {\Phi }^{\top }$.

Generalized (Moore-Penrose) inverse

For symmetric $A={\sum }_i{\lambda }_i{v}_i{v}_i^{\top }$: $A^{+}={\sum }_{i:{\lambda }_i\ne 0}\frac{1}{{\lambda }_i}{v}_i{v}_i^{\top }$: invert where possible, leave the null space alone. $A^{+}=A^{-1}$ if $A$ is invertible; $A{A}^{+}A=A$. Least squares in general: $w=(X^{\top }X{)}^{+}{X}^{\top }y$ (L5).

Projections and the trace

Projection

$P$ is a projection if $P^2=P$ (projecting twice changes nothing); orthogonal if additionally $P=P^{\top }$. Example: $P=X^{\top }(X{X}^{\top }{)}^{-1}X$ projects onto the span of the data points: it keeps $w_{\parallel }$ and kills $w_{\perp }$ (L8).

Trace

$\mathrm{tr}(A)={\sum }_i{A}_{ii}={\sum }_i{\lambda }_i$. Cyclic: $\mathrm{tr}(ABC)=\mathrm{tr}(CAB)=\mathrm{tr}(BCA)$. A number is its own trace: $v^{\top }Av=\mathrm{tr}(v^{\top }Av)=\mathrm{tr}(Av{v}^{\top })$. Trace of a projection = its rank. ${\sum }_j{e}_j^{\top }A{e}_j=\mathrm{tr}A$.

The trace trick (used in the proofs of L8)

For a random vector $y$ with $E(y{y}^{\top })={\sigma }^2{I}_n$ and a fixed matrix $A$: $E(y^{\top }Ay)=E\mathrm{tr}(Ay{y}^{\top })=\mathrm{tr}(AE(y{y}^{\top }))={\sigma }^2\mathrm{tr}(A)$. With $A=(X{X}^{\top }{)}^{-1}$ this gives the variance term of the minimum norm interpolator (L8).

Self-check

Question cards (5)

Compute the inverse of $\left(\begin{array}{cc}3& 1\\ 1& 1\end{array}\right)$.

Answer

$\det =2$: $\frac{1}{2}\left(\begin{array}{cc}1& -1\\ -1& 3\end{array}\right)$.

Eigenvalues of $\left(\begin{array}{cc}4& 0\\ 0& 1\end{array}\right)$ and the largest step size for which GD on $\frac{1}{2}{w}^{\top }Aw$ converges?

Answer

4 and 1 (diagonal entries). GD needs $|1-4\eta |<1$, so $\eta <0.5=2/{\lambda }_{\max }$.

$X$ has 3 rows and 10 columns, full rank. How many solutions does $Xw=y$ have, and what is $\dim \ker X$?

Answer

Infinitely many; rank 3, so $\dim \ker X=10-3=7$.

Why is $X^{\top }X$ positive semi-definite?

Answer

$v^{\top }{X}^{\top }Xv=\Vert Xv{\Vert }^2\ge 0$ for every $v$.

What is the trace of the projection $X^{\top }(X{X}^{\top }{)}^{-1}X$ for $X\in {\mathbb{R}}^{n\times d}$ of rank $n$?

Answer

$n$: cyclic trace gives $\mathrm{tr}((X{X}^{\top }{)}^{-1}X{X}^{\top })=\mathrm{tr}(I_n)=n$.

Related

• Math overview · Calculus and Optimization · Random Variables and Expectation