§2.5–2.10Norms · Special Matrices · Eigendecomposition · SVD · Pseudoinverse · Trace

§2.5 Norms — measuring the size of a vector

Machine learning measures vector size with a norm norm A size measure for vectors: f(x)=0 ⟹ x=0, triangle inequality, |α|-homogeneity; the Lᵖ family (‖x‖ₚ). defined in ch. 2 — open in glossary , most often from the $L^p$ family:

Formally a norm is any function with three properties: $f(\boldsymbol{x}) = 0 \Rightarrow \boldsymbol{x} = \boldsymbol{0}$; the triangle inequality $f(\boldsymbol{x}+\boldsymbol{y}) \le f(\boldsymbol{x}) + f(\boldsymbol{y})$; and homogeneity $f(\alpha\boldsymbol{x}) = |\alpha| f(\boldsymbol{x})$.

The family members you will meet constantly:

• $L^2$ (Euclidean) — so common it is written plainly $\|\boldsymbol{x}\|$. Its square is just $\boldsymbol{x}^\top\boldsymbol{x}$, which is far nicer analytically: each derivative $\partial \|x\|_2^2 / \partial x_i = 2x_i$ depends only on its own element, while derivatives of the unsquared norm entangle the whole vector.
• $L^1$ — $\|\boldsymbol{x}\|_1 = \sum_i |x_i|$. The squared $L^2$ norm grows very slowly near the origin; when the difference between exactly-zero and small-but-nonzero matters, $L^1$ grows at the same rate everywhere ($\epsilon$ of movement costs exactly $\epsilon$).
• "$L^0$" — counting nonzero entries is not a norm (scaling by $\alpha$ doesn’t change the count, violating homogeneity); the term is a common abuse. $L^1$ is the usual substitute.
• $L^\infty$ (max norm) — $\|\boldsymbol{x}\|_\infty = \max_i |x_i|$.
• Frobenius norm frobenius norm The matrix analogue of L²: ‖A‖_F = √Σ A²_{i,j} = √Tr(AAᵀ). defined in ch. 2 — open in glossary for matrices — $\|\boldsymbol{A}\|_F = \sqrt{\sum_{i,j} A_{i,j}^2}$, the $L^2$ of a matrix flattened.

Finally, the dot product in norm language: $\boldsymbol{x}^\top\boldsymbol{y} = \|\boldsymbol{x}\|_2 \|\boldsymbol{y}\|_2 \cos\theta$ with $\theta$ the angle between them.

§2.6 Special matrices and vectors

• A diagonal matrix diagonal matrix Nonzero entries only on the main diagonal; diag(v)x = v⊙x — multiply and invert cheaply. defined in ch. 2 — open in glossary $\mathrm{diag}(\boldsymbol{v})$ is mostly zeros; multiplying is just element-wise scaling ($\mathrm{diag}(\boldsymbol{v})\boldsymbol{x} = \boldsymbol{v} \odot \boldsymbol{x}$) and inverting is element-wise reciprocals ($\mathrm{diag}(\boldsymbol{v})^{-1} = \mathrm{diag}([1/v_1, \dots, 1/v_n]^\top)$, existing iff every $v_i \ne 0$). Many algorithms get cheaper (and less expressive) when a general matrix is restricted to diagonal. Rectangular diagonal matrices exist too: multiply-then-pad (tall) or multiply-then-truncate (wide).
• A symmetric matrix symmetric matrix A = Aᵀ; arises from order-independent two-argument functions like distances. defined in ch. 2 — open in glossary equals its transpose — typical when entries come from an order-independent function, like distances: $A_{i,j} = A_{j,i}$.
• A unit vector unit vector A vector with ‖x‖₂ = 1. defined in ch. 2 — open in glossary has $\|\boldsymbol{x}\|_2 = 1$. Vectors with $\boldsymbol{x}^\top\boldsymbol{y} = 0$ are orthogonal (at 90° if nonzero); at most $n$ nonzero vectors in $\mathbb{R}^n$ can be mutually orthogonal; orthogonal + unit norm = orthonormal.
• An orthogonal matrix orthogonal matrix Square with mutually orthonormal rows AND columns: AᵀA = AAᵀ = I, so A⁻¹ = Aᵀ. defined in ch. 2 — open in glossary has mutually orthonormal rows AND columns: $\boldsymbol{A}^\top\boldsymbol{A} = \boldsymbol{A}\boldsymbol{A}^\top = \boldsymbol{I}$, hence $\boldsymbol{A}^{-1} = \boldsymbol{A}^\top$ — inversion for the price of a transpose. (Watch the naming trap: the matrix is called orthogonal but its rows are orthonormal; there is no special name for merely-orthogonal rows.)

§2.7 Eigendecomposition

Integers reveal their nature when factored into primes — $12 = 2 \times 2 \times 3$ tells us things no digit string does. Matrices factor too. An eigenvector eigenvector Nonzero v with Av = λv — multiplication by A only rescales it. defined in ch. 2 — open in glossary of $\boldsymbol{A}$ is a nonzero direction that multiplication by $\boldsymbol{A}$ only rescales, and its scale factor is the eigenvalue eigenvalue The scale factor λ paired with an eigenvector. defined in ch. 2 — open in glossary :

With $n$ independent eigenvectors as columns of $\boldsymbol{V}$ and eigenvalues in $\boldsymbol{\lambda}$, the eigendecomposition eigendecomposition A = V diag(λ)V⁻¹; real symmetric matrices give A = QΛQᵀ with orthogonal Q — scaling space by λᵢ along eigendirection i. defined in ch. 2 — open in glossary is $\boldsymbol{A} = \boldsymbol{V}\,\mathrm{diag}(\boldsymbol{\lambda})\,\boldsymbol{V}^{-1}$. Not every matrix has one (some need complex numbers; non-square matrices have none) — but every real symmetric matrix decomposes with real values and an orthogonal eigenbasis:

$\boldsymbol{A} = \boldsymbol{Q}\boldsymbol{\Lambda}\boldsymbol{Q}^\top$

What the decomposition tells you:

• Uniqueness: sort $\boldsymbol{\Lambda}$ descending; unique iff all eigenvalues distinct (repeated λ’s let any orthogonal basis of their span serve).
• Singularity: $\boldsymbol{A}$ is singular ⟺ some eigenvalue is 0 (watch the ellipse flatten in the widget as λ₂ → 0).
• Quadratic optimization: for $f(\boldsymbol{x}) = \boldsymbol{x}^\top\boldsymbol{A}\boldsymbol{x}$ with $\|\boldsymbol{x}\|_2 = 1$, $f$ equals $\lambda$ whenever $\boldsymbol{x}$ is the corresponding eigenvector; max/min over the sphere = max/min eigenvalue.
• Definiteness: all λ > 0 → positive definite positive definite All eigenvalues > 0; guarantees xᵀAx > 0 for x ≠ 0 (semidefinite allows zeros). defined in ch. 2 — open in glossary ($\boldsymbol{x}^\top\boldsymbol{A}\boldsymbol{x} = 0 \Rightarrow \boldsymbol{x} = 0$); λ ≥ 0 → positive semidefinite ($\forall \boldsymbol{x},\, \boldsymbol{x}^\top\boldsymbol{A}\boldsymbol{x} \ge 0$); mirrored for negative (semi)definite.

§2.8 Singular value decomposition

The SVD singular value decomposition A = UDVᵀ for ANY real matrix: orthogonal U, V and rectangular-diagonal D of singular values. defined in ch. 2 — open in glossary factors every real matrix — square or not — where eigendecomposition may not exist:

§2.9 The Moore-Penrose pseudoinverse

Non-square matrices have no inverse, but linear equations $\boldsymbol{A}\boldsymbol{x} = \boldsymbol{y}$ still want solving. The pseudoinverse moore-penrose pseudoinverse A⁺ = VD⁺Uᵀ: minimal-norm solution for wide A, least-squares closest solution for tall A. defined in ch. 2 — open in glossary is defined as $\boldsymbol{A}^+ = \lim_{\alpha \to 0}(\boldsymbol{A}^\top\boldsymbol{A} + \alpha\boldsymbol{I})^{-1}\boldsymbol{A}^\top$, but computed via the SVD:

Its behavior depends on $\boldsymbol{A}$‘s shape:

• Wide (more columns than rows, typically ∞ solutions): $\boldsymbol{x} = \boldsymbol{A}^+\boldsymbol{y}$ is the solution with minimal norm $\|\boldsymbol{x}\|_2$ among all of them.
• Tall (more rows than columns, possibly no solution): it gives the $\boldsymbol{x}$ making $\boldsymbol{A}\boldsymbol{x}$ as close as possible to $\boldsymbol{y}$ in $\|\boldsymbol{A}\boldsymbol{x} - \boldsymbol{y}\|_2$ — least squares, previewing chapter 4’s worked example.

§2.10 The trace operator

The trace trace Tr(A) = Σᵢ A_{i,i}; transpose-invariant and cyclic-permutation-invariant — the workhorse of matrix calculus. defined in ch. 2 — open in glossary sums the diagonal: $\mathrm{Tr}(\boldsymbol{A}) = \sum_i A_{i,i}$. It converts summation-notation gymnastics into algebra:

• $\|\boldsymbol{A}\|_F = \sqrt{\mathrm{Tr}(\boldsymbol{A}\boldsymbol{A}^\top)}$
• transpose-invariant: $\mathrm{Tr}(\boldsymbol{A}) = \mathrm{Tr}(\boldsymbol{A}^\top)$
• cyclic-permutation-invariant: $\mathrm{Tr}(\boldsymbol{A}\boldsymbol{B}\boldsymbol{C}) = \mathrm{Tr}(\boldsymbol{C}\boldsymbol{A}\boldsymbol{B}) = \mathrm{Tr}(\boldsymbol{B}\boldsymbol{C}\boldsymbol{A})$ — valid even when the cycled products have different shapes: for $\boldsymbol{A} \in \mathbb{R}^{m\times n}$, $\boldsymbol{B} \in \mathbb{R}^{n\times m}$, $\mathrm{Tr}(\boldsymbol{A}\boldsymbol{B}) = \mathrm{Tr}(\boldsymbol{B}\boldsymbol{A})$ though one is $m{\times}m$ and the other $n{\times}n$.
• a scalar is its own trace: $a = \mathrm{Tr}(a)$.