The norm zoo: $\ell_p$, spectral, Frobenius, nuclear and Schatten norms

Before this lesson: lesson 08 (the SVD, Eckart–Young–Mirsky, polar decomposition and the pseudoinverse) and lesson 03 (inverse, determinant, dot product and orthogonal projection). Time: about 70 minutes, plus the notebook.

---

Why this matters #

A norm is a choice of how to measure size, and the choice changes the answer. Penalizing $\|w\|_1$ gives sparse models (lasso); penalizing $\|w\|_2^2$ gives small, dense ones (ridge). For matrices, the spectral norm measures the worst-case stretch: it is the Lipschitz constant of a linear layer and the basis of spectral normalization. The nuclear norm is the convex stand-in for rank, used for matrix completion and low-rank recovery. Error budgets for compression (lesson 08) and condition numbers (lesson 13) are also stated in these norms.

1. Predict first #

2. The picture #

The unit ball of a norm is the set $\{x : \|x\| \le 1\}$. In the plane it looks like this:

• $\ell_2$: a disk.
• $\ell_1$: a diamond with corners on the axes, $(\pm1, 0)$ and $(0, \pm1)$.
• $\ell_\infty$: a square with corners at $(\pm1, \pm1)$.

Interactive figure: loading…

To find the point of a line with the smallest norm, inflate the ball until it first touches the line. The disk touches at the foot of the perpendicular, which in general has no zero coordinate. The diamond almost always touches first at a corner, and corners lie on the axes: one coordinate is exactly zero. This one picture is the main reason why $\ell_1$ gives sparse solutions.

Interactive figure: loading…

For a matrix $A$, the singular values $\sigma_1 \ge \sigma_2 \ge \dots \ge 0$ are the axis lengths of the ellipse $\{Ax : \|x\|_2 = 1\}$ (lesson 08). The three main matrix norms are three ways to summarize these lengths: the longest one, the root of the sum of squares, and the sum.

3. Definitions and main results #

Norms #

A norm on $\mathbb{R}^n$ is a function $\|\cdot\|$ with, for all $x, y$ and scalars $c$:

1. $\|x\| \ge 0$, and $\|x\| = 0$ only for $x = 0$ (definiteness);
2. $\|cx\| = |c|\,\|x\|$ (homogeneity);
3. $\|x + y\| \le \|x\| + \|y\|$ (triangle inequality).

The $\ell_p$ norms, for $p \ge 1$: $\|x\|_p = \big(\sum_i |x_i|^p\big)^{1/p}$, and $\|x\|_\infty = \max_i |x_i|$ (the limit $p \to \infty$). Facts you will use:

• $\|x\|_p$ is non-increasing in $p$: $\|x\|_\infty \le \|x\|_2 \le \|x\|_1$.
• In the other direction: $\|x\|_1 \le \sqrt n\,\|x\|_2$ and $\|x\|_2 \le \sqrt n\,\|x\|_\infty$.
• A bound used below: $|a^\top x| \le \|a\|_\infty\|x\|_1$. Proof: $|\sum_i a_i x_i| \le \sum_i |a_i|\,|x_i| \le \max_i |a_i| \sum_i |x_i|$.
• For a symmetric positive definite (SPD) matrix $S$, $\|x\|_S = \sqrt{x^\top S x}$ is also a norm (the energy norm).

Not norms. For $0 < p < 1$ the triangle inequality fails: with $x = (1,0)$, $y = (0,1)$, $\|x+y\|_{1/2} = (1 + 1)^2 = 4 > 2 = \|x\|_{1/2} + \|y\|_{1/2}$; the unit ball is not convex. The count of nonzeros, "$\|x\|_0$", fails homogeneity: $\|2x\|_0 = \|x\|_0$, not $2\|x\|_0$.

Dual norms and Hölder's inequality

Hölder's inequality: $|x^\top y| \le \|x\|_p\|y\|_q$ when $1/p + 1/q = 1$ (with $1/\infty = 0$). For $p = q = 2$ it is the Cauchy–Schwarz inequality. For $p = 1$, $q = \infty$ it is the bound $|a^\top x| \le \|a\|_\infty\|x\|_1$ above.

The dual norm of a norm $\|\cdot\|$ is $\|y\|_* = \max_{\|x\| \le 1} x^\top y$: the largest "score" $x^\top y$ over the unit ball. Hölder's inequality is sharp, so the dual of $\ell_p$ is $\ell_q$. So $\ell_1$ and $\ell_\infty$ are dual to each other, and $\ell_2$ is its own dual.

For $\ell_1$ the maximizer of $x^\top y$ over the unit ball is a corner $\pm e_j$ with $j = \arg\max_i |y_i|$, so $\max_{\|x\|_1 \le 1} x^\top y = \|y\|_\infty$. This is the same "corner" picture as in section 2. Dual norms appear in optimality conditions (the subgradient of $\|x\|$ is a vector of dual norm at most 1) and in steepest descent: the steepest-descent step in $\ell_\infty$ is $-\operatorname{sign}(\nabla f)$, the step of signSGD and close to Adam's early steps.

Why $\ell_1$ promotes sparsity #

Theorem 1 (one constraint). Let $a \neq 0$. Among all $x$ with $a^\top x = b$, the smallest $\ell_1$ norm is $|b|/\|a\|_\infty$, reached by the 1-sparse vector $x = (b/a_j)\,e_j$ with $j = \arg\max_i |a_i|$. The smallest $\ell_2$ norm is reached at $x = b\,a/\|a\|_2^2$, which (for $b \neq 0$) is nonzero wherever $a$ is.

Proof.

1. By the bound above, $|b| = |a^\top x| \le \|a\|_\infty \|x\|_1$. So every feasible $x$ has $\|x\|_1 \ge |b|/\|a\|_\infty$.
2. $x = (b/a_j)e_j$ is feasible ($a^\top x = a_j \cdot b/a_j = b$) and has $\|x\|_1 = |b|/|a_j| = |b|/\|a\|_\infty$: the lower bound is reached.
3. For $\ell_2$, the minimizer is the orthogonal projection of $0$ onto the line (lesson 03), which is along the normal vector $a$: $x = b\,a/\|a\|_2^2$. $\blacksquare$

Soft-thresholding. Lasso solvers reduce the problem to one coordinate at a time. For one coordinate, the question is: given a number $z$ (what the data want) and a penalty weight $\lambda > 0$, which $x$ minimizes

Theorem 2 (soft-thresholding). The minimizer of $g$ is $x^\star = S_\lambda(z) = \operatorname{sign}(z)\max(|z| - \lambda, 0)$. The minimizer of the ridge objective $\tfrac12(x - z)^2 + \tfrac\lambda2 x^2$ is $z/(1 + \lambda)$.

Proof, step by step. $g$ is a parabola plus a "V". Both are convex, so $g$ is convex, and a point where $g$ stops going down and starts going up is the global minimum. The V has a kink at $x = 0$, so we look at three cases.

1. Case $x > 0$. Here $|x| = x$, so $g(x) = \tfrac12(x - z)^2 + \lambda x$ and $g'(x) = x - z + \lambda$. Setting $g'(x) = 0$ gives $x = z - \lambda$. This point is in the case ($x > 0$) only when $z > \lambda$.
2. Case $x < 0$. Here $|x| = -x$, so $g'(x) = x - z - \lambda$, and $g'(x) = 0$ gives $x = z + \lambda$. This point is in the case ($x < 0$) only when $z < -\lambda$.
3. Case $x = 0$ (the kink). $g$ has no derivative at 0, but it has two one-sided slopes: $g'(0^-) = -z - \lambda$ from the left and $g'(0^+) = -z + \lambda$ from the right. The point $x = 0$ is the minimum when $g$ goes down into it and up after it: $g'(0^-) \le 0 \le g'(0^+)$, that is, $-\lambda \le z \le \lambda$.
4. The three conditions $z > \lambda$, $z < -\lambda$ and $|z| \le \lambda$ cover every $z$ exactly once. Together: $x^\star = z - \lambda$, $z + \lambda$ or $0$, which is the formula $\operatorname{sign}(z)\max(|z| - \lambda, 0)$.
5. Ridge. The ridge objective has no kink: its derivative $x - z + \lambda x = 0$ gives $x = z/(1 + \lambda)$, which is zero only if $z = 0$. $\blacksquare$

In the language of convex analysis, step 3 says $0 \in -z + \lambda\,\partial|x|(0)$, where the subdifferential $\partial|x|(0) = [-1, 1]$ is the set of slopes of lines that touch the V at 0 from below.

Interactive figure: loading…

The reason in one sentence: $|x|$ keeps slope $\pm1$ near 0, so a small data term cannot pull $x$ away from 0; $x^2$ has slope 0 at 0, so it never holds $x$ exactly at 0 (unless $z = 0$). Lasso solvers (ISTA, coordinate descent) apply this step to each coordinate.

The same picture works for a full least-squares loss. Lasso and ridge can be written as constrained problems: minimize $\|Xw - y\|_2^2$ subject to $\|w\|_1 \le t$ or $\|w\|_2 \le t$ (each value of the penalty $\lambda$ matches some radius $t$). The level sets of the loss are ellipses around the unconstrained solution $\hat w$.

Interactive figure: loading…

Matrix norms from singular values #

Let $A \in \mathbb{R}^{m\times n}$ with SVD $A = U\Sigma V^\top$ and rank $r$.

Norm	Definition	Through singular values
spectral (operator 2-norm) $\lVert A\rVert_2$	$\max_{x\neq0} \lVert Ax\rVert_2/\lVert x\rVert_2$	$\sigma_1$
Frobenius $\lVert A\rVert_F$	$\big(\sum_{ij} a_{ij}^2\big)^{1/2} = \sqrt{\operatorname{tr}(A^\top A)}$	$\big(\sum_i \sigma_i^2\big)^{1/2}$
nuclear (trace norm) $\lVert A\rVert_*$	$\max_{\lVert B\rVert_2 \le 1}\operatorname{tr}(B^\top A)$	$\sum_i \sigma_i$

The spectral norm is the largest stretch factor of $A$. The Frobenius norm treats $A$ as a long vector of $mn$ entries. The nuclear norm is the sum of the singular values.

Theorem 3. $\|A\|_2 = \sigma_1$ and $\|A\|_F^2 = \sum_i \sigma_i^2$.

Proof.

1. Orthogonal matrices keep lengths. Put $y = V^\top x$, so $\|y\| = \|x\|$, and $\|Ax\| = \|U\Sigma y\| = \|\Sigma y\|$.
2. $\|\Sigma y\|^2 = \sum_i \sigma_i^2 y_i^2 \le \sigma_1^2\|y\|^2$. So $\|Ax\|/\|x\| \le \sigma_1$.
3. Equality at $x = v_1$: $Av_1 = \sigma_1 u_1$. Hence $\|A\|_2 = \sigma_1$.
4. $\|A\|_F^2 = \operatorname{tr}(A^\top A) = \operatorname{tr}(V\Sigma^\top\Sigma V^\top) = \operatorname{tr}(\Sigma^\top\Sigma V^\top V) = \sum_i \sigma_i^2$ (the trace is cyclic: $\operatorname{tr}(XY) = \operatorname{tr}(YX)$). $\blacksquare$

The induced 1- and $\infty$-norms, by hand #

Any vector norm gives an induced (operator) matrix norm: $\|A\|_p = \max_{x \ne 0} \|Ax\|_p/\|x\|_p$, the largest stretch measured in $\ell_p$. For $p = 2$ this is $\sigma_1$, which needs the SVD. For $p = 1$ and $p = \infty$ there are simple formulas.

$\|A\|_1$ = largest absolute column sum. Let $c_j = \sum_i |a_{ij}|$ be the absolute sum of column $j$. Step 1: use $|a + b| \le |a| + |b|$ inside, then swap the order of the two sums. Step 2: bound every $c_j$ by the largest one.

Step 3: equality holds at $x = e_j$ for the best column $j$, because $\|Ae_j\|_1 = c_j$. So $\|A\|_1 = \max_j c_j$.

$\|A\|_\infty$ = largest absolute row sum. Let $\rho_i = \sum_j |a_{ij}|$ be the absolute sum of row $i$. Step 1: bound each entry of $Ax$.

Step 2: take the largest entry: $\|Ax\|_\infty = \max_i |(Ax)_i| \le (\max_i \rho_i)\|x\|_\infty$.

Step 3: equality holds at $x_j = \operatorname{sign}(a_{ij})$ for the best row $i$. Then every term is $a_{ij}x_j = |a_{ij}|$, so $(Ax)_i = \rho_i$, and $\|x\|_\infty = 1$.

Example. $A = \begin{pmatrix} 1 & -2 \\ 3 & 4 \end{pmatrix}$.

• Column sums: $|1| + |3| = 4$ and $|-2| + |4| = 6$. So $\|A\|_1 = 6$, reached at $e_2$: $Ae_2 = (-2, 4)$ and $\|Ae_2\|_1 = 6$.
• Row sums: $|1| + |-2| = 3$ and $|3| + |4| = 7$. So $\|A\|_\infty = 7$, reached at the signs of row 2, $x = (1, 1)$: $Ax = (-1, 7)$ and $\|Ax\|_\infty = 7$.

Interactive figure: loading…

The Frobenius and nuclear norms are not induced norms: every induced norm has $\|I\| = \max_x \|x\|/\|x\| = 1$, but $\|I_n\|_F = \sqrt n$ and $\|I_n\|_* = n$.

Useful properties:

• Unitary invariance: $\|QAZ\| = \|A\|$ for orthogonal $Q$, $Z$, for all three norms (the singular values do not change).
• Inequalities (vector norm inequalities applied to $\sigma \in \mathbb{R}^r$): $\|A\|_2 \le \|A\|_F \le \sqrt r\,\|A\|_2$ and $\|A\|_F \le \|A\|_* \le \sqrt r\,\|A\|_F$.
• Submultiplicativity: $\|AB\| \le \|A\|\,\|B\|$ for induced norms and for Frobenius; also the mixed bound $\|AB\|_F \le \|A\|_2\,\|B\|_F$.

The spectral norm as a Lipschitz constant #

A function $f$ is $L$-Lipschitz if $\|f(x) - f(y)\| \le L\|x - y\|$ for all $x, y$: outputs move at most $L$ times as much as inputs. The smallest such $L$ is the Lipschitz constant $\operatorname{Lip}(f)$. Here we build the bound for a network step by step.

1. A linear layer. $\|Wx - Wy\|_2 = \|W(x - y)\|_2 \le \|W\|_2\,\|x - y\|_2$, with equality when $x - y$ is parallel to $v_1$. So $\operatorname{Lip}(x \mapsto Wx) = \sigma_1(W)$ exactly.
2. An activation. ReLU acts entry by entry, and $|\max(a, 0) - \max(b, 0)| \le |a - b|$ for numbers. Square and add over the entries: ReLU is 1-Lipschitz. The same holds for tanh.
3. A composition. If $g$ is $L_g$-Lipschitz and $h$ is $L_h$-Lipschitz, then $\|h(g(x)) - h(g(y))\| \le L_h\|g(x) - g(y)\| \le L_hL_g\|x - y\|$.
4. A network. For $f = W_L \circ \phi \circ \dots \circ \phi \circ W_1$ with 1-Lipschitz activations $\phi$, step 3 applied layer by layer gives $\operatorname{Lip}(f) \le \prod_l \|W_l\|_2$.

A 2-layer example. Let $W_1 = \begin{pmatrix} 2 & 0 \\ 0 & 1/2 \end{pmatrix}$, $W_2 = \begin{pmatrix} 1/2 & 0 \\ 0 & 2 \end{pmatrix}$ and $f(x) = W_2\operatorname{ReLU}(W_1x)$. The bound is $\|W_2\|_2\|W_1\|_2 = 2 \cdot 2 = 4$. But $W_1$ stretches the $e_1$ direction by 2 and $W_2$ shrinks the same direction by $1/2$, so $f(x) = (\operatorname{ReLU}(x_1), \operatorname{ReLU}(x_2))$, and the true constant is 1. With $W_2 = W_1$ instead, $f(x) = (4\operatorname{ReLU}(x_1), \tfrac14\operatorname{ReLU}(x_2))$: two points on the positive $x_1$-axis move 4 times apart, so the bound 4 is reached. The product bound is tight only when the top directions of consecutive layers line up.

Spectral normalization (Miyato et al., 2018) uses $W/\hat\sigma_1(W)$ in each layer, so every layer is (up to the estimation error of $\hat\sigma_1$) 1-Lipschitz and the bound is at most 1. The estimate $\hat\sigma_1$ comes from one power-iteration step per training step, reusing the vector from the previous step. Two limits: the product bound is often loose (as in the example), and for a convolution the paper normalizes the reshaped $d_\text{out}\times(d_\text{in}hw)$ kernel matrix, which is only a proxy for the operator norm of the convolution.

The nuclear norm and low rank #

$\operatorname{rank}(A)$ is the number of nonzero $\sigma_i$ (an "$\ell_0$" of $\sigma$), while $\|A\|_*$ is the $\ell_1$ norm of $\sigma$. So the nuclear norm plays the role of $\ell_1$ for rank.

Why not minimize the rank directly? The rank is not a convex function. A convex $f$ satisfies $f(\tfrac12 A + \tfrac12 B) \le \tfrac12 f(A) + \tfrac12 f(B)$. Take $A = E_{11} = \operatorname{diag}(1, 0)$ and $B = E_{22} = \operatorname{diag}(0, 1)$. Each has rank 1, but $\tfrac12 A + \tfrac12 B = \tfrac12 I$ has rank $2 > \tfrac12 \cdot 1 + \tfrac12 \cdot 1 = 1$. Problems like "find the matrix of smallest rank that fits these entries" are NP-hard in general. The nuclear norm is a norm, so it is convex: here $\|\tfrac12 I\|_* = 1 = \tfrac12\|A\|_* + \tfrac12\|B\|_*$, and convex problems with it can be solved efficiently.

The proximal step of the nuclear norm (the matrix version of soft-thresholding) is singular value soft-thresholding: $U\Sigma V^\top \mapsto U\max(\Sigma - \lambda, 0)V^\top$. It sets the small singular values exactly to zero, so it gives low rank in the same way that soft-thresholding gives zeros. On the set $\{\|A\|_2 \le 1\}$, $\|A\|_*$ is the convex envelope (the largest convex function below) of the rank (Fazel), which is why it is the standard convex surrogate (matrix completion, robust PCA).

Schatten $p$-norms #

Definition. For $p \ge 1$, the Schatten $p$-norm is $\|A\|_{S_p} = \big(\sum_i \sigma_i^p\big)^{1/p}$, the $\ell_p$ norm of the singular value vector.

• $p = 1$: nuclear norm. $p = 2$: Frobenius norm. $p = \infty$: spectral norm.
• They are norms for $p \ge 1$ (the triangle inequality needs a real proof, via von Neumann's trace inequality); for $0 < p < 1$ they are not (non-convex rank surrogates).
• All are unitarily invariant, and non-increasing in $p$.
• Eckart–Young–Mirsky holds in every unitarily invariant norm: the truncated SVD $A_k$ is the best approximation of rank at most $k$ in every $S_p$, with error $\big(\sum_{j>k}\sigma_j^p\big)^{1/p}$.

Duality of the Schatten norms

$S_p$ and $S_q$ are dual for $1/p + 1/q = 1$: $\|A\|_{S_q} = \max_{\|B\|_{S_p} \le 1}\operatorname{tr}(B^\top A)$, with the matrix inner product $\operatorname{tr}(B^\top A) = \sum_{ij} b_{ij}a_{ij}$. So the nuclear and the spectral norm are dual (this is the definition of $\|A\|_*$ in the table), and Frobenius is self-dual. The maximizer for the nuclear norm is $B = UV^\top$ (the orthogonal factor of the polar decomposition, lesson 08): $\operatorname{tr}(VU^\top U\Sigma V^\top) = \operatorname{tr}\Sigma = \sum_i\sigma_i$. The proof of the general case uses von Neumann's trace inequality $|\operatorname{tr}(B^\top A)| \le \sum_i \sigma_i(A)\sigma_i(B)$ and then Hölder's inequality for the singular value vectors.

Answers to section 1. (1) $\ell_2$: $(0.8, 1.6)$, no zero. $\ell_1$: $(0, 2)$, by Theorem 1 ($\|a\|_\infty = 2$ at $j = 2$). (2) All three are equal: a rank-one matrix has one nonzero singular value, $\sigma_1 = \|u\|_2\|v\|_2$.

4. Worked example #

Vectors. $x = (1, -2, 2)$: $\|x\|_1 = 5$, $\|x\|_2 = \sqrt{1+4+4} = 3$, $\|x\|_\infty = 2$. Check $\|x\|_\infty \le \|x\|_2 \le \|x\|_1 \le \sqrt3\,\|x\|_2 \approx 5.196$. ✓

Minimum norms on the line $x_1 + 2x_2 = 4$ ($a = (1,2)$, $b = 4$; the second figure):

Norm	Minimizer	Why
$\ell_2$	$b\,a/\lVert a\rVert^2 = (0.8, 1.6)$	projection; norm $4/\sqrt5 \approx 1.789$
$\ell_1$	$(0, 2)$	corner of the diamond; $\ell_1$ norm $2$ (the $\ell_2$ answer has $2.4$)
$\ell_\infty$	$(4/3, 4/3)$	corner of the square: equal coordinates

Soft-thresholding with $\lambda = 1$: $z = (3, 0.5, -1.5) \mapsto (2, 0, -0.5)$. The first entry is in case 1 ($3 > 1$, so $3 - 1$), the second in case 3 ($|0.5| \le 1$, so 0), the third in case 2 ($-1.5 < -1$, so $-1.5 + 1$). Ridge with $\lambda = 1$ gives $z/2 = (1.5, 0.25, -0.75)$: smaller, but no zeros.

A matrix. $A = \begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix}$. $A^\top A = \begin{pmatrix} 25 & 20 \\ 20 & 25 \end{pmatrix}$ has eigenvalues $45$ and $5$, so $\sigma_1 = 3\sqrt5 \approx 6.708$ and $\sigma_2 = \sqrt5 \approx 2.236$ (check: $\sigma_1\sigma_2 = 15 = |\det A|$).

• Spectral: $\|A\|_2 = 3\sqrt5 \approx 6.708$, reached at $v_1 = (1,1)/\sqrt2$: $Av_1 = (3, 9)/\sqrt2$, length $\sqrt{90/2} = \sqrt{45}$. ✓
• Frobenius: $\sqrt{9 + 16 + 25} = \sqrt{50} = \sqrt{45 + 5} \approx 7.071$. ✓
• Nuclear: $3\sqrt5 + \sqrt5 = 4\sqrt5 \approx 8.944$.
• Schatten-4: $(\sigma_1^4 + \sigma_2^4)^{1/4} = (45^2 + 5^2)^{1/4} = 2050^{1/4} \approx 6.729$, between $S_2$ and $S_\infty$.
• Induced $\|A\|_1 = \max(3 + 4,\ 0 + 5) = 7$ (columns), $\|A\|_\infty = \max(3 + 0,\ 4 + 5) = 9$ (rows).
• Inequalities with $r = 2$: $6.708 \le 7.071 \le 9.487$ and $7.071 \le 8.944 \le 10$. ✓
• Nuclear soft-thresholding with $\lambda = 3$: $\sigma \mapsto (3\sqrt5 - 3, 0) \approx (3.708, 0)$, a rank-one matrix.

5. In code #

The libraries confirm the numbers. The notebook for this lesson has these cells and the exercises.

import numpy as np
import torch
from sklearn.linear_model import Lasso, Ridge

x = np.array([1.0, -2.0, 2.0])
print([float(np.linalg.norm(x, p)) for p in (1, 2, np.inf)])   # [5.0, 3.0, 2.0]

A = np.array([[3.0, 0.0], [4.0, 5.0]])
print(np.linalg.svd(A, compute_uv=False))                      # [6.708 2.236] = 3√5, √5
print([round(float(np.linalg.norm(A, o)), 3) for o in (2, "fro", "nuc", 1, np.inf)])
# [6.708, 7.071, 8.944, 7.0, 9.0]: spectral, Frobenius, nuclear, max column sum, max row sum

# The spectral norm is the largest stretch: random directions never beat v1 = (1,1)/√2.
rng = np.random.default_rng(0)
Z = rng.standard_normal((2, 10_000))
print((np.linalg.norm(A @ Z, axis=0) / np.linalg.norm(Z, axis=0)).max())   # just below 6.708

# Soft-thresholding versus ridge, lambda = 1
z = np.array([3.0, 0.5, -1.5])
print(np.sign(z) * np.maximum(np.abs(z) - 1, 0), z / 2)       # [ 2.  0.  -0.5] [ 1.5  0.25 -0.75]

# ℓ1 gives exact zeros, ℓ2 does not (3 true nonzeros out of 20).
X = rng.standard_normal((50, 20))
w_true = np.zeros(20)
w_true[:3] = [2.0, -3.0, 1.5]
y = X @ w_true + 0.1 * rng.standard_normal(50)
print((Lasso(alpha=0.1).fit(X, y).coef_ == 0).sum(),     # 17: exactly the 17 unused features
      (Ridge(alpha=1.0).fit(X, y).coef_ == 0).sum())     # 0

# Spectral normalization: W / σ̂1, with σ̂1 from one power-iteration step per forward pass.
torch.manual_seed(0)
layer = torch.nn.utils.parametrizations.spectral_norm(torch.nn.Linear(64, 32))
xb = torch.randn(8, 64)
for _ in range(50):                  # training mode: each call refines σ̂1
    layer(xb)
print(torch.linalg.matrix_norm(layer.weight.detach(), ord=2).item())   # ≈ 1.0

6. Where it shows up #

• Sparse models. Lasso and compressed sensing (exact recovery of a sparse signal from few random measurements by minimizing $\|x\|_1$). In science: sparse regression of governing equations (SINDy), sparse sensor placement.
• Low rank. Matrix completion, robust PCA (low rank + sparse), low-rank regularization of weights. The nuclear norm is the convex tool; LoRA instead bounds the rank ($\le r$) by construction.
• Lipschitz control. Spectral normalization in GAN discriminators; Lipschitz bounds for robustness certificates and for stable long rollouts of learned time-stepping models.
• Error budgets. Compress a weight matrix to rank $k$: the spectral error is $\sigma_{k+1}$ (worst-case output change for a unit input); the squared Frobenius error $\sum_{j>k}\sigma_j^2$ is the mean squared output change $\mathbb{E}\|(A - A_k)x\|^2$ for $x \sim \mathcal{N}(0, I)$.
• Numerical analysis. Condition numbers $\kappa(A) = \|A\|\|A^{-1}\|$ and error bounds (lesson 13); $\|A\|_1$ and $\|A\|_\infty$ are cheap, $\|A\|_2$ needs the SVD or power iteration.

7. Common mistakes #

• Forgetting definiteness ($\|x\| = 0 \Rightarrow x = 0$) when checking the norm axioms.
• Calling "$\ell_0$" or $\ell_{1/2}$ a norm. "$\ell_0$" fails homogeneity; $\ell_{1/2}$ fails the triangle inequality.
• Confusing the matrix 2-norm with the Frobenius norm. np.linalg.norm(A) on a matrix returns the Frobenius norm; the spectral norm needs ord=2.
• Thinking the spectral norm is the largest entry. $\begin{pmatrix}1&1\\1&1\end{pmatrix}$ has entries $\le 1$ but $\|\cdot\|_2 = 2$.
• Mixing up rows and columns in $\|A\|_1$ and $\|A\|_\infty$. $\|A\|_1$ uses column sums (the maximizer is $e_j$); $\|A\|_\infty$ uses row sums (the maximizer is a sign vector).
• Overflow in $\sqrt{\sum x_i^2}$. For $x = (10^{200}, 10^{200})$ the squares overflow to inf. Scale by $\max_i|x_i|$ first (the way BLAS nrm2 avoids it).
• Treating $\prod_l \|W_l\|_2$ as the true Lipschitz constant. It is an upper bound, often loose (the 2-layer example: bound 4, true value 1).

8. Check yourself #

1. Give $\|x\|_1, \|x\|_2, \|x\|_\infty$ for $x = (2, -1, 0, 2)$.
   Answer

   $5$, $3$, $2$.
2. $A$ has singular values $4, 3, 0$. Give $\|A\|_2$, $\|A\|_F$, $\|A\|_*$ and $\|A\|_{S_3}$.
   Answer

   $4$; $\sqrt{16 + 9} = 5$; $7$; $(64 + 27)^{1/3} = 91^{1/3} \approx 4.498$.
3. Why is the minimizer of $\tfrac12(x - z)^2 + \lambda|x|$ exactly zero for $|z| \le \lambda$?
   Answer

   At $x = 0$ the left slope is $-z - \lambda \le 0$ and the right slope is $-z + \lambda \ge 0$: the convex function goes down into the kink and up after it. In subgradient form: $0 \in (x - z) + \lambda\,\partial|x|$ at $x = 0$ reads $z \in [-\lambda, \lambda]$.
4. A 3-layer ReLU network has weight matrices with spectral norms $2$, $0.5$, $3$. Give an upper bound on its Lipschitz constant (in $\ell_2$). Is it attained in general?
   Answer

   $2 \cdot 0.5 \cdot 3 = 3$. Not in general: it needs the top singular directions of consecutive layers to line up, and ReLU to pass them unchanged.
5. Show $\|A\|_2 \le \|A\|_F \le \sqrt r\,\|A\|_2$, and say when each side is an equality.
   Answer

   $\sigma_1^2 \le \sum_{i\le r}\sigma_i^2 \le r\sigma_1^2$. Left equality iff rank $\le 1$; right equality iff all $r$ nonzero singular values are equal (e.g. an orthogonal matrix, $r = n$).
6. Compute $\|A\|_1$ and $\|A\|_\infty$ for $A = \begin{pmatrix} 2 & -1 \\ -3 & 0 \end{pmatrix}$, and give a maximizing $x$ for each.
   Answer

   Column sums $5$ and $1$: $\|A\|_1 = 5$ at $x = e_1$, $Ae_1 = (2, -3)$. Row sums $3$ and $3$: $\|A\|_\infty = 3$, for example at the signs of row 1, $x = (1, -1)$: $Ax = (3, -3)$.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. What three rules make a function $\|\cdot\|$ a norm?

   Show answer

2. Why is $\|x\|_{1/2} = (\sum_i |x_i|^{1/2})^2$ not a norm?

   Show answer

3. Why does an $\ell_1$ penalty give exact zeros, while an $\ell_2$ penalty does not?

   Show answer

4. Give the soft-thresholding formula $S_\lambda(z)$.

   Show answer

5. Compute $S_1(z)$ for $z = (3, 0.5, -1.5)$.

   Show answer

6. What is $\|A\|_2$ in terms of the SVD, and which $x$ reaches it?

   Show answer

7. Write $\|A\|_F^2$ in three ways.

   Show answer

8. What are the induced norms $\|A\|_1$ and $\|A\|_\infty$?

   Show answer

9. What is the nuclear norm, and why is it used?

   Show answer

10. What is the Lipschitz constant of $x \mapsto Wx$, and what bound holds for a ReLU network?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Why does L1 regularization give sparse solutions?" — Corners of the $\ell_1$ ball on the axes; soft-thresholding sets small coefficients exactly to 0; $|x|$ keeps slope at 0.
• "What is the spectral norm and why do we care in deep learning?" — $\sigma_1$, the maximum stretch, the Lipschitz constant of a linear layer; spectral normalization, stability.
• "Spectral vs Frobenius vs nuclear?" — $\ell_\infty$, $\ell_2$, $\ell_1$ of the singular values: worst case, total energy, convex surrogate for rank.
• "Is the Frobenius norm an operator norm?" — No: $\|I\|_F = \sqrt n \neq 1$.

10. Practice #

The notebook for this lesson runs in Colab. It has five exercises, each with a check cell and a folded solution:

1. Write an overflow-safe $\ell_p$ norm (including $p = \infty$) and plot the unit balls.
2. Find the minimum-$\ell_1$ and minimum-$\ell_2$ points on a hyperplane $a^\top x = b$ (Theorem 1).
3. Write soft-thresholding, then use it in ISTA to solve a lasso problem and compare with scikit-learn.
4. Compute the spectral, Frobenius, nuclear, Schatten and induced 1 and ∞ norms of a matrix.
5. Recover a sparse vector from few measurements by minimizing $\|x\|_1$ with a linear program, and compare with the minimum-$\ell_2$ solution.

The notebook also estimates $\sigma_1$ by power iteration, the step inside spectral normalization.

11. Watch and read #

Lecture 8: Norms of Vectors and MatricesGilbert Strang · MIT 18.065 (2018) · 49 min

Sparsity and the L1 NormSteve Brunton · 11 min

• Driscoll and Braun, Fundamentals of Numerical Computation, free online: §2.7 Vector and matrix norms.
• Miyato et al., Spectral normalization for generative adversarial networks (ICLR 2018), §2.1–2.2 and Appendix A.
• Recht, Fazel and Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, §2 (norms, duality, Table 1, Theorem 2.2).