Norms and Distance Metrics
Matrix Norms
Read aloud is unavailable in this browser.
Measuring Matrices: The Size of Linear Transformations
In the previous page, we learned how to measure the 'size' of vectors using norms. But machine learning is fundamentally about transformations—weight matrices that transform inputs to outputs, covariance matrices that describe data distributions, and Jacobians that capture how changes propagate through networks.
How do we measure the 'size' of a matrix? This question is more nuanced than it first appears. A matrix is not just a collection of numbers; it represents a linear transformation. Different matrix norms capture different aspects of this transformation: how much it can stretch vectors, how 'spread out' its values are, or how close it is to being singular.
Matrix norms are essential for understanding numerical stability, convergence of iterative algorithms, condition numbers, regularization in deep learning, and the analysis of neural network generalization.
By the end of this page, you will understand induced (operator) norms, element-wise (Frobenius) norms, and spectral norms. You'll learn how these relate to eigenvalues and singular values, and why matrix norms are critical for analyzing the stability and convergence of machine learning algorithms.
What Makes a Matrix Norm?
A matrix norm is a function $|\cdot|: \mathbb{R}^{m \times n} \to \mathbb{R}$ that satisfies the same three axioms as vector norms, applied to the space of $m \times n$ matrices:
Formal Definition:
A function $|\cdot|$ on matrices is a norm if for all matrices $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{m \times n}$ and all scalars $\alpha \in \mathbb{R}$:
- •Non-Negativity with Definiteness: $|\mathbf{A}| \geq 0$, and $|\mathbf{A}| = 0 \Leftrightarrow \mathbf{A} = \mathbf{0}$ (the zero matrix)
- •Absolute Homogeneity: $|\alpha \mathbf{A}| = |\alpha| |\mathbf{A}|$
- •Triangle Inequality: $|\mathbf{A} + \mathbf{B}| \leq |\mathbf{A}| + |\mathbf{B}|$
Additional Property for Square Matrices:
For norms on square matrices $\mathbb{R}^{n \times n}$, we often require an additional property:
Submultiplicativity: $|\mathbf{A}\mathbf{B}| \leq |\mathbf{A}| |\mathbf{B}|$
This property is essential for analyzing products of matrices, such as compositions of linear layers in neural networks or powers of matrices in iterative algorithms. A norm satisfying this property is called a submultiplicative norm or ring norm.
Matrix norms fall into two broad categories: Induced (Operator) Norms that measure how much a matrix can 'stretch' vectors, and Entry-wise (Element) Norms that treat the matrix as a flattened vector of entries. Each perspective is useful for different applications.
Induced (Operator) Norms
The most geometrically meaningful matrix norms are induced norms (also called operator norms or subordinate norms). They measure how much a matrix can 'stretch' vectors when viewed as a linear transformation.
Definition:
Given a vector norm $|\cdot|$ on $\mathbb{R}^n$, the induced matrix norm on $\mathbb{R}^{m \times n}$ is:
$$|\mathbf{A}| = \max_{\mathbf{x} eq \mathbf{0}} \frac{|\mathbf{A}\mathbf{x}|}{|\mathbf{x}|} = \max_{|\mathbf{x}|=1} |\mathbf{A}\mathbf{x}|$$
This is the maximum stretching factor—the largest ratio by which $\mathbf{A}$ can stretch any vector. Equivalently, it's the maximum norm of $\mathbf{Ax}$ over all unit vectors $\mathbf{x}$.
Key Induced Norms:
1. Matrix 1-Norm (Maximum Column Sum):
$$|\mathbf{A}|1 = \max{j} \sum_{i=1}^{m} |a_{ij}|$$
The maximum absolute column sum. Induced by the vector L1 norm.
2. Matrix ∞-Norm (Maximum Row Sum):
$$|\mathbf{A}|\infty = \max{i} \sum_{j=1}^{n} |a_{ij}|$$
The maximum absolute row sum. Induced by the vector L∞ norm.
3. Matrix 2-Norm (Spectral Norm):
$$|\mathbf{A}|2 = \sigma{\max}(\mathbf{A}) = \sqrt{\lambda_{\max}(\mathbf{A}^T\mathbf{A})}$$
The largest singular value of $\mathbf{A}$. Induced by the vector L2 norm. This is the most important matrix norm in machine learning.
Induced norms automatically satisfy $|\mathbf{AB}| \leq |\mathbf{A}| |\mathbf{B}|$. Proof: $|\mathbf{ABx}| \leq |\mathbf{A}| |\mathbf{Bx}| \leq |\mathbf{A}| |\mathbf{B}| |\mathbf{x}|$, so dividing by $|\mathbf{x}|$ and taking max gives the result. This property is crucial for analyzing products of weight matrices in deep networks.
12345678910111213141516171819202122232425262728293031323334353637383940414243
import numpy as np # Define a matrixA = np.array([[1, 2, 3], [4, 5, 6]]) print(f"Matrix A:{A}") # Matrix 1-norm: maximum column sumnorm_1 = np.linalg.norm(A, ord=1)col_sums = np.sum(np.abs(A), axis=0)print(f"Column sums: {col_sums}")print(f"Matrix 1-norm (max column sum): {norm_1}") # max(5, 7, 9) = 9 # Matrix ∞-norm: maximum row sumnorm_inf = np.linalg.norm(A, ord=np.inf)row_sums = np.sum(np.abs(A), axis=1)print(f"Row sums: {row_sums}")print(f"Matrix ∞-norm (max row sum): {norm_inf}") # max(6, 15) = 15 # Matrix 2-norm (spectral norm): largest singular valuenorm_2 = np.linalg.norm(A, ord=2)singular_values = np.linalg.svd(A, compute_uv=False)print(f"Singular values: {singular_values}")print(f"Matrix 2-norm (spectral): {norm_2}")print(f"σ_max(A) = {singular_values[0]:.6f}") # Verify submultiplicativityB = np.array([[1, 0], [0, 1], [1, 1]])AB = A @ Bprint(f"Verifying ||AB|| ≤ ||A|| ||B||:")print(f"||A||_2 = {np.linalg.norm(A, 2):.4f}")print(f"||B||_2 = {np.linalg.norm(B, 2):.4f}")print(f"||AB||_2 = {np.linalg.norm(AB, 2):.4f}")print(f"||A||_2 * ||B||_2 = {np.linalg.norm(A, 2) * np.linalg.norm(B, 2):.4f}")print(f"Submultiplicativity holds: {np.linalg.norm(AB, 2) <= np.linalg.norm(A, 2) * np.linalg.norm(B, 2) + 1e-10}")The Spectral Norm: King of Matrix Norms
The spectral norm (matrix 2-norm) is arguably the most important matrix norm in machine learning. It equals the largest singular value and measures the maximum geometric 'stretch' a matrix applies to any vector.
Definition:
$$|\mathbf{A}|2 = \sigma{\max}(\mathbf{A}) = \max_{\mathbf{x} eq 0} \frac{|\mathbf{A}\mathbf{x}|_2}{|\mathbf{x}|_2}$$
Computing the Spectral Norm:
For any matrix $\mathbf{A}$, the spectral norm equals:
- $\sqrt{\lambda_{\max}(\mathbf{A}^T\mathbf{A})}$ (square root of largest eigenvalue of $\mathbf{A}^T\mathbf{A}$)
- $\sqrt{\lambda_{\max}(\mathbf{A}\mathbf{A}^T)}$ (equivalently, using $\mathbf{A}\mathbf{A}^T$)
- The largest singular value from SVD: $\mathbf{A} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T$
Special Case: Symmetric Matrices
For symmetric matrices $\mathbf{A} = \mathbf{A}^T$, the spectral norm simplifies beautifully:
$$|\mathbf{A}|2 = \rho(\mathbf{A}) = \max{i} |\lambda_i|$$
The spectral norm equals the spectral radius—the largest absolute eigenvalue. This is because for symmetric matrices, singular values equal absolute eigenvalues.
- •Geometric Meaning: Maximum stretch factor of the linear transformation
- •Unitary Invariance: $|\mathbf{UAV}|_2 = |\mathbf{A}|_2$ for orthogonal/unitary $\mathbf{U}, \mathbf{V}$
- •Submultiplicativity: $|\mathbf{AB}|_2 \leq |\mathbf{A}|_2 |\mathbf{B}|_2$
- •Relation to SVD: Equals $\sigma_1$, the largest singular value
- •Condition Number: $\kappa(\mathbf{A}) = |\mathbf{A}|2 |\mathbf{A}^{-1}|2 = \sigma{\max}/\sigma{\min}$
Unlike the 1-norm and ∞-norm (which can be computed in O(mn) time), the spectral norm requires computing the largest singular value, which is O(min(m,n)·mn) via SVD or iterative methods like power iteration. For large matrices, this can be a bottleneck.
Spectral Norm in Machine Learning:
-
Spectral Normalization: In GANs and discriminator networks, dividing weight matrices by their spectral norm ($\mathbf{W} \to \mathbf{W}/|\mathbf{W}|_2$) controls Lipschitz continuity and stabilizes training.
-
Generalization Bounds: Many generalization bounds for neural networks involve the product of spectral norms across layers: $\prod_l |\mathbf{W}^{(l)}|_2$.
-
Gradient Analysis: The spectral norm of the Jacobian bounds how much small input changes become large output changes.
-
Low-Rank Approximation: Truncating small singular values (those below a threshold relative to $|\mathbf{A}|_2$) gives optimal low-rank approximations.
The Frobenius Norm: Element-wise L2
The Frobenius norm treats the matrix as a long vector of $mn$ entries and computes the vector L2 norm. It is the most commonly used 'element-wise' matrix norm.
Definition:
$$|\mathbf{A}|F = \sqrt{\sum{i=1}^{m} \sum_{j=1}^{n} |a_{ij}|^2} = \sqrt{\text{trace}(\mathbf{A}^T\mathbf{A})}$$
Equivalently, in terms of singular values:
$$|\mathbf{A}|F = \sqrt{\sum{k=1}^{\min(m,n)} \sigma_k^2} = \sqrt{\sigma_1^2 + \sigma_2^2 + \cdots + \sigma_r^2}$$
where $r = \text{rank}(\mathbf{A})$.
- •Easy to Compute: Just sum of squared entries, O(mn) time
- •Differentiable: Smooth everywhere except zero matrix
- •Unitary Invariance: $|\mathbf{UAV}|_F = |\mathbf{A}|_F$
- •Natural Inner Product: Induces the Frobenius inner product $\langle\mathbf{A},\mathbf{B}\rangle_F = \text{trace}(\mathbf{A}^T\mathbf{B})$
- •Not Induced: Not induced by any vector norm
- •Not Submultiplicative: $|\mathbf{AB}|_F ot\leq |\mathbf{A}|_F|\mathbf{B}|_F$ in general
- •Sensitive to Dimension: Scales with $\sqrt{mn}$ even for identity-like matrices
- •Treats All Entries Equally: Doesn't distinguish between 'important' and 'unimportant' directions
Relationship Between Frobenius and Spectral Norms:
Two important inequalities connect these norms:
$$|\mathbf{A}|_2 \leq |\mathbf{A}|_F \leq \sqrt{\text{rank}(\mathbf{A})} \cdot |\mathbf{A}|_2$$
- The spectral norm is always smaller (or equal for rank-1 matrices)
- The gap is at most $\sqrt{r}$ where $r$ is the rank
- For nearly low-rank matrices, the gap is small
12345678910111213141516171819202122232425262728293031323334353637383940414243
import numpy as np # Define a matrixA = np.array([[1, 2, 3], [4, 5, 6]]) print(f"Matrix A:{A}") # Frobenius norm: multiple equivalent calculationsfrob_manual = np.sqrt(np.sum(A**2))frob_trace = np.sqrt(np.trace(A.T @ A))frob_builtin = np.linalg.norm(A, 'fro') print(f"Frobenius norm calculations:")print(f" Manual (√Σa²): {frob_manual:.6f}")print(f" Via trace: {frob_trace:.6f}")print(f" Built-in: {frob_builtin:.6f}") # In terms of singular valuessigma = np.linalg.svd(A, compute_uv=False)frob_svd = np.sqrt(np.sum(sigma**2))print(f" Via singular values √(Σσ²): {frob_svd:.6f}")print(f" Singular values: {sigma}") # Compare with spectral normspectral = np.linalg.norm(A, 2)rank_A = np.linalg.matrix_rank(A)print(f"Spectral norm: {spectral:.6f}")print(f"Frobenius norm: {frob_builtin:.6f}")print(f"Matrix rank: {rank_A}")print(f"Verifying: ||A||_2 ≤ ||A||_F ≤ √rank · ||A||_2")print(f" {spectral:.4f} ≤ {frob_builtin:.4f} ≤ {np.sqrt(rank_A) * spectral:.4f}") # Weight decay in neural networks uses squared Frobenius normlambda_reg = 0.01W = np.random.randn(100, 50)l2_regularization = lambda_reg * np.sum(W**2) # = λ ||W||_F²print(f"L2 regularization (weight decay): λ||W||_F² = {l2_regularization:.4f}")In deep learning, 'L2 regularization' or 'weight decay' adds $\lambda \sum_{i,j} w_{ij}^2 = \lambda |\mathbf{W}|_F^2$ to the loss. This penalizes large weights, encouraging the network to use smaller, distributed representations. It's the squared Frobenius norm, not the spectral norm.
The Nuclear Norm: Sum of Singular Values
The nuclear norm (also called trace norm or Schatten 1-norm) is the sum of singular values. It plays the same role for matrices that the L1 norm plays for vectors: it promotes sparsity in singular values, i.e., low rank.
Definition:
$$|\mathbf{A}|* = \sum{k=1}^{\min(m,n)} \sigma_k = \sigma_1 + \sigma_2 + \cdots + \sigma_r$$
where $\sigma_k$ are the singular values of $\mathbf{A}$.
Alternatively:
$$|\mathbf{A}|_* = \text{trace}(\sqrt{\mathbf{A}^T\mathbf{A}})$$
Why Nuclear Norm Promotes Low Rank:
Just as L1 regularization on a vector encourages many entries to be exactly zero, nuclear norm regularization on a matrix encourages many singular values to be exactly zero—which means low rank.
The nuclear norm is the tightest convex relaxation of the rank function:
$$\text{rank}(\mathbf{A}) \approx |\mathbf{A}|_*$$
Since minimizing rank directly is NP-hard, nuclear norm minimization is used as a tractable convex surrogate.
- •Matrix Completion: Netflix problem—fill missing entries while encouraging low rank. Solve: $\min |\mathbf{M}|_*$ s.t. observed entries match.
- •Robust PCA: Decompose $\mathbf{M} = \mathbf{L} + \mathbf{S}$ where $\mathbf{L}$ is low-rank (small nuclear norm) and $\mathbf{S}$ is sparse (small L1).
- •Recommender Systems: User-item matrices are approximately low-rank; nuclear norm regularization exploits this.
- •Image Denoising: Natural images have low-rank structure; nuclear norm minimization recovers clean images.
12345678910111213141516171819202122232425262728293031323334353637383940
import numpy as np # Define a matrixA = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) # Note: rank 2, one singular value is ~0 print(f"Matrix A:{A}") # Nuclear norm: sum of singular valuessigma = np.linalg.svd(A, compute_uv=False)nuclear = np.sum(sigma)nuclear_builtin = np.linalg.norm(A, 'nuc') print(f"Singular values: {sigma}")print(f"Rank (numerical): {np.sum(sigma > 1e-10)}")print(f"Nuclear norm: {nuclear:.6f}")print(f"Built-in nuclear norm: {nuclear_builtin:.6f}") # Compare all major matrix normsprint(f"Comparing matrix norms for A:")print(f" Spectral (2-norm): {np.linalg.norm(A, 2):.4f} = σ_max")print(f" Frobenius: {np.linalg.norm(A, 'fro'):.4f} = √(Σσ²)")print(f" Nuclear: {np.linalg.norm(A, 'nuc'):.4f} = Σσ") # Low-rank vs full-rank comparisonprint(f"--- Low-rank matrix ---")L = np.outer([1, 2, 3], [1, 1, 1]) # Rank 1print(f"Rank-1 matrix L:{L}")sigma_L = np.linalg.svd(L, compute_uv=False)print(f"Singular values: {sigma_L}")print(f"Nuclear norm: {np.linalg.norm(L, 'nuc'):.4f}")print(f"Frobenius norm: {np.linalg.norm(L, 'fro'):.4f}")print(f"Ratio Nuclear/Frobenius: {np.linalg.norm(L, 'nuc')/np.linalg.norm(L, 'fro'):.4f}")# For rank-1, nuclear = Frobenius since only one singular valueThe nuclear norm is the dual norm of the spectral norm: $|\mathbf{A}|* = \max{|\mathbf{B}|_2 \leq 1} \text{trace}(\mathbf{B}^T\mathbf{A})$. This duality is analogous to L1 and L∞ being duals for vectors, and it plays a crucial role in optimization algorithms.
Condition Numbers: Measuring Sensitivity
The condition number of a matrix measures how sensitively the solution to a system of linear equations changes with small perturbations in the input. It's defined using matrix norms and is fundamental to numerical analysis.
Definition:
For an invertible matrix $\mathbf{A}$:
$$\kappa(\mathbf{A}) = |\mathbf{A}| \cdot |\mathbf{A}^{-1}|$$
For the spectral norm (most common):
$$\kappa_2(\mathbf{A}) = |\mathbf{A}|2 \cdot |\mathbf{A}^{-1}|2 = \frac{\sigma{\max}(\mathbf{A})}{\sigma{\min}(\mathbf{A})}$$
The condition number is always $\geq 1$, with equality for scalar multiples of orthogonal matrices.
Interpretation:
Consider solving $\mathbf{Ax} = \mathbf{b}$. If we perturb $\mathbf{b}$ slightly to $\mathbf{b} + \Delta\mathbf{b}$, how much does the solution change?
$$\frac{|\Delta\mathbf{x}|}{|\mathbf{x}|} \leq \kappa(\mathbf{A}) \cdot \frac{|\Delta\mathbf{b}|}{|\mathbf{b}|}$$
- Low condition number ($\kappa \approx 1$): The problem is well-conditioned. Small input errors cause small output errors.
- High condition number ($\kappa \gg 1$): The problem is ill-conditioned. Small input errors can cause large output errors.
- Very high condition number ($\kappa \to \infty$): The matrix is nearly singular. Numerical solutions are unreliable.
| Condition Number | Classification | Numerical Reliability |
|---|---|---|
| κ ≈ 1 | Perfectly conditioned | Excellent; solutions are stable |
| κ ≈ 10 | Well-conditioned | Very good; minor precision loss |
| κ ≈ 10³ | Moderately conditioned | Acceptable; ~3 digits of precision may be lost |
| κ ≈ 10⁶ | Ill-conditioned | Problematic; significant precision loss |
| κ ≈ 10¹⁵ or higher | Severely ill-conditioned | Unreliable; near numerical singularity |
123456789101112131415161718192021222324252627282930313233343536373839404142434445
import numpy as np # Well-conditioned matrix: orthogonal matrices have condition number 1theta = np.pi/6Q = np.array([[np.cos(theta), -np.sin(theta)], [np.sin(theta), np.cos(theta)]])print(f"Rotation matrix Q:{Q}")print(f"Condition number: {np.linalg.cond(Q):.6f} (ideal = 1)") # Moderately conditionedA = np.array([[1, 2], [3, 7]])print(f"Matrix A:{A}")print(f"Condition number: {np.linalg.cond(A):.2f}") # Ill-conditioned: Hilbert matrix (notorious example)def hilbert(n): return np.array([[1/(i+j+1) for j in range(n)] for i in range(n)]) for n in [3, 5, 7, 10]: H = hilbert(n) kappa = np.linalg.cond(H) print(f"Hilbert matrix H_{n}: condition number = {kappa:.2e}") # Demonstrating ill-conditioning effectsprint(f"--- Demonstrating ill-conditioning ---")n = 7H = hilbert(n)x_true = np.ones(n)b = H @ x_true # Solve with slight perturbationb_perturbed = b + 1e-8 * np.random.randn(n)x_computed = np.linalg.solve(H, b)x_perturbed = np.linalg.solve(H, b_perturbed) print(f"Perturbation in b: {np.linalg.norm(b_perturbed - b):.2e}")print(f"Change in solution: {np.linalg.norm(x_perturbed - x_computed):.2e}")print(f"Condition number: {np.linalg.cond(H):.2e}")print("Ill-conditioning amplifies small errors dramatically!")ill-conditioned matrices appear frequently: (1) Gram matrices $\mathbf{X}^T\mathbf{X}$ with correlated features, (2) Hessians near saddle points, (3) Deep network Jacobians. This is why regularization (adding $\lambda\mathbf{I}$) helps—it bounds the condition number by $\frac{\sigma_{\max} + \lambda}{\sigma_{\min} + \lambda}$.
Comprehensive Matrix Norms Reference
Let's consolidate all the matrix norms we've covered into a comprehensive reference. For a matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ with singular values $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$ where $r = \text{rank}(\mathbf{A})$:
| Norm | Definition | In Terms of SVD | Primary Use |
|---|---|---|---|
| 1-norm $|\mathbf{A}|_1$ | max column sum | — | Sparse optimization |
| ∞-norm $|\mathbf{A}|_\infty$ | max row sum | — | Row-wise bounds |
| Spectral $|\mathbf{A}|_2$ | max $|\mathbf{Ax}|_2/|\mathbf{x}|_2$ | $\sigma_1$ | Lipschitz bounds, stability |
| Frobenius $|\mathbf{A}|_F$ | $\sqrt{\sum_{i,j} a_{ij}^2}$ | $\sqrt{\sum_k \sigma_k^2}$ | Regularization (weight decay) |
| Nuclear $|\mathbf{A}|_*$ | trace$(\sqrt{\mathbf{A}^T\mathbf{A}})$ | $\sum_k \sigma_k$ | Low-rank recovery |
Key Relationships:
$$|\mathbf{A}|_2 \leq |\mathbf{A}|_F \leq \sqrt{r} |\mathbf{A}|_2$$
$$|\mathbf{A}|2 \leq |\mathbf{A}|* \leq r |\mathbf{A}|_2$$
$$|\mathbf{A}|_* \leq \sqrt{r} |\mathbf{A}|_F$$
These inequalities show how the choice of norm affects the magnitude and how rank plays a role.
KEEP LEARNING
There’s more to understand.
You’re reading the introduction. Create a free account to read the complete lesson, save notes and keep track of your progress.