ml.lab
Python sleeps until you run code
04 Eigenvectors and eigenvalues

Lesson 4 of 4

Singular values and the SVD

Every matrix, symmetric or not, is a rotation, a stretch along perpendicular axes and another rotation. Those stretches, the singular values, measure how much a matrix can grow a vector, bound gradients through a chain of layers, and give the best low-rank approximation.

About 65 minutes
By the end you can
  • Explain A=UΣV⊤\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top as rotate, stretch, rotate, and compute it for a 2x2 matrix from A⊤A\mathbf{A}^\top\mathbf{A}.

  • Use ∣Ax∣≤σ1∣x∣|\mathbf{A}\mathbf{x}| \le \sigma_1|\mathbf{x}| to bound how much a matrix, or a chain of matrices, can grow a vector.

  • Explain why initialization scales and orthogonal matrices keep singular values near 1.

  • Build the best rank-k approximation of a matrix and count the numbers it saves.

Look again at a shear, this time S=[1201]\mathbf{S} = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}. It is triangular, so its eigenvalues are its diagonal entries, 1 and 1, and its spectral radius is 1. If eigenvalues measured stretch, this matrix would stretch nothing. Yet S(0,1)=(2,1)\mathbf{S}(0,\allowbreak 1) = (2,\allowbreak 1), which has length 4+1=5≈2.24\sqrt{4 + 1} = \sqrt{5} \approx 2.24, and before the end of this lesson we will find a direction that it stretches by 1+2≈2.411 + \sqrt{2} \approx 2.41.

Eigenvalues answer the question "which directions survive repeated multiplication, and at what rate?" They do not answer "how much can one multiplication stretch a vector?", which is what you need to know when a gradient passes through a different matrix at every layer or every time step. That second question has its own answer, the singular values.

The road there runs through the previous lesson. Every matrix A\mathbf{A}, square or not, comes with a symmetric matrix attached, A⊤A\mathbf{A}^\top\mathbf{A}, and the spectral theorem applied to it gives the whole answer. The plan: first the picture (every matrix is a rotation, a stretch and a rotation), then how to compute it, then what the largest stretch guarantees, and last how keeping only the biggest stretches compresses a matrix.

Rotate, stretch, rotate

One multiplication stretches different directions by different amounts. For a symmetric matrix the previous lesson gave the full story: a stretch along perpendicular axes. The surprise is that every matrix has such axes. It may also turn the result, so the axes it stretches along are not the axes it lands on.

Follow the unit circle, every vector of length 1, through the three moves. V⊤\mathbf{V}^\top turns it, and a turned circle is the same circle. Σ\boldsymbol{\Sigma} stretches it along the two axes, into an ellipse with half-widths σ1\sigma_1 and σ2\sigma_2. U\mathbf{U} turns that ellipse into place. So the unit circle goes in and an ellipse comes out, with semi-axes σ1u1\sigma_1\mathbf{u}_1 and σ2u2\sigma_2\mathbf{u}_2.

Four stages from left to right. A circle with two perpendicular diameters, one blue and one coral. The same circle turned so the two diameters lie horizontal and vertical. An ellipse stretched along those same two axes, wider than tall. The same ellipse turned to a tilt, its two axes still perpendicular.Every matrix in three moves: turn, stretch along perpendicular axes, turn again.

For a 2x2 matrix you can check the ellipse directly. Every point of the unit circle is x=cos⁡t v1+sin⁡t v2\mathbf{x} = \cos t\,\mathbf{v}_1 + \sin t\,\mathbf{v}_2 for some angle tt, because v1,v2\mathbf{v}_1,\allowbreak \mathbf{v}_2 are perpendicular unit vectors. The matrix sends v1\mathbf{v}_1 to σ1u1\sigma_1\mathbf{u}_1 and v2\mathbf{v}_2 to σ2u2\sigma_2\mathbf{u}_2 (that is what the three moves do to them), so by linearity Ax=σ1cos⁡t u1+σ2sin⁡t u2\mathbf{A}\mathbf{x} = \sigma_1\cos t\,\mathbf{u}_1 + \sigma_2\sin t\,\mathbf{u}_2. Measured along the perpendicular directions u1,u2\mathbf{u}_1,\allowbreak \mathbf{u}_2, its coordinates are (σ1cos⁡t, σ2sin⁡t)(\sigma_1\cos t,\allowbreak \ \sigma_2\sin t), which trace an ellipse with half-widths σ1\sigma_1 and σ2\sigma_2.

The instrument below draws exactly this for A=[3045]\mathbf{A} = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}: the white unit circle, its image as a violet ellipse, and the two semi-axes labelled σ1\sigma_1 and σ2\sigma_2, whose lengths are in the readouts. The blue and coral arrows are the columns of A\mathbf{A}, where ı^\hat{\imath} and ȷ^\hat{\jmath} land, and you can drag their tips.

Computing the SVD by hand

The picture says what the SVD is. To compute it, we need the directions vi\mathbf{v}_i that get stretched the most and the least. The symmetric matrix A⊤A\mathbf{A}^\top\mathbf{A} finds them.

A⊤A\mathbf{A}^\top\mathbf{A} is symmetric. Transpose it, using the transpose rule (which reverses the order) and then (A⊤)⊤=A(\mathbf{A}^\top)^\top = \mathbf{A}:

(A⊤A)⊤=A⊤(A⊤)⊤=A⊤A.(\mathbf{A}^\top\mathbf{A})^\top = \mathbf{A}^\top(\mathbf{A}^\top)^\top = \mathbf{A}^\top\mathbf{A}.

It measures stretch. For any x\mathbf{x},

x⊤A⊤A x=(Ax)⊤(Ax)=∣Ax∣2≥0.\mathbf{x}^\top\mathbf{A}^\top\mathbf{A}\,\mathbf{x} = (\mathbf{A}\mathbf{x})^\top(\mathbf{A}\mathbf{x}) = |\mathbf{A}\mathbf{x}|^2 \ge 0.

In particular, if v\mathbf{v} is a unit eigenvector of A⊤A\mathbf{A}^\top\mathbf{A} with eigenvalue μ\mu, then v⊤A⊤Av=μ v⊤v=μ\mathbf{v}^\top\mathbf{A}^\top\mathbf{A}\mathbf{v} = \mu\,\mathbf{v}^\top\mathbf{v} = \mu, so μ=∣Av∣2\mu = |\mathbf{A}\mathbf{v}|^2: each eigenvalue of A⊤A\mathbf{A}^\top\mathbf{A} is the squared stretch of its own eigenvector, and none is negative.

So take the perpendicular unit eigenvectors v1,v2,…\mathbf{v}_1,\allowbreak \mathbf{v}_2,\allowbreak \ldots of A⊤A\mathbf{A}^\top\mathbf{A} that the spectral theorem promises, and write its eigenvalues, largest first, as σ12≥σ22≥⋯≥0\sigma_1^2 \ge \sigma_2^2 \ge \cdots \ge 0. The numbers σi≥0\sigma_i \ge 0 are the singular values of A\mathbf{A}, and ∣Avi∣=σi|\mathbf{A}\mathbf{v}_i| = \sigma_i. For each σi>0\sigma_i > 0 define ui=Avi/σi\mathbf{u}_i = \mathbf{A}\mathbf{v}_i/\sigma_i, the direction vi\mathbf{v}_i lands in, scaled to length 1, so that

Avi=σi ui.\mathbf{A}\mathbf{v}_i = \sigma_i\,\mathbf{u}_i.

The ui\mathbf{u}_i turn out to be perpendicular to each other too, which is what makes U\mathbf{U} orthogonal.

Go slower: Why the u vectors are perpendicular, and how A = U Σ Vᵀ follows

Take two indices ii and jj with σi,σj>0\sigma_i,\allowbreak \sigma_j > 0. Write the dot product as a transpose product, use the transpose rule, then A⊤Avj=σj2vj\mathbf{A}^\top\mathbf{A}\mathbf{v}_j = \sigma_j^2\mathbf{v}_j:

ui⋅uj=(Avi)⊤(Avj)σiσj=vi⊤A⊤A vjσiσj=σj2 vi⋅vjσiσj.\mathbf{u}_i\cdot\mathbf{u}_j = \frac{(\mathbf{A}\mathbf{v}_i)^\top(\mathbf{A}\mathbf{v}_j)}{\sigma_i\sigma_j} = \frac{\mathbf{v}_i^\top\mathbf{A}^\top\mathbf{A}\,\mathbf{v}_j}{\sigma_i\sigma_j} = \frac{\sigma_j^2\,\mathbf{v}_i\cdot\mathbf{v}_j}{\sigma_i\sigma_j}.

The v\mathbf{v}'s are perpendicular unit vectors, so vi⋅vj\mathbf{v}_i\cdot\mathbf{v}_j is 0 when i≠ji \ne j, giving ui⋅uj=0\mathbf{u}_i\cdot\mathbf{u}_j = 0. When i=ji = j it is 1, giving ui⋅ui=σi2/σi2=1\mathbf{u}_i\cdot\mathbf{u}_i = \sigma_i^2/\sigma_i^2 = 1.

Now stack the equations Avi=σiui\mathbf{A}\mathbf{v}_i = \sigma_i\mathbf{u}_i side by side as columns: AV=UΣ\mathbf{A}\mathbf{V} = \mathbf{U}\boldsymbol{\Sigma}, where V\mathbf{V} has the vi\mathbf{v}_i as columns, U\mathbf{U} the ui\mathbf{u}_i, and Σ\boldsymbol{\Sigma} the σi\sigma_i on its diagonal (the same column argument as AP=PD\mathbf{A}\mathbf{P} = \mathbf{P}\mathbf{D} in the powers lesson). V\mathbf{V} is orthogonal, so V−1=V⊤\mathbf{V}^{-1} = \mathbf{V}^\top, and multiplying both sides on the right by V⊤\mathbf{V}^\top gives A=UΣV⊤\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top. (When some σi\sigma_i are zero, or A\mathbf{A} is not square, U\mathbf{U} is completed with extra perpendicular unit vectors; they get multiplied by zeros and change nothing.)

Worked example. Take A=[3045]\mathbf{A} = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}, the matrix in the instrument.

  1. Multiply out A⊤A\mathbf{A}^\top\mathbf{A}, row of A⊤\mathbf{A}^\top by column of A\mathbf{A}: A⊤A=[3405][3045]=[9+160+200+200+25]=[25202025].\mathbf{A}^\top\mathbf{A} = \begin{bmatrix} 3 & 4 \\ 0 & 5 \end{bmatrix}\begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix} = \begin{bmatrix} 9 + 16 & 0 + 20 \\ 0 + 20 & 0 + 25 \end{bmatrix} = \begin{bmatrix} 25 & 20 \\ 20 & 25 \end{bmatrix}.
  2. It has the pattern of [2112]\begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} (equal diagonal, equal off-diagonal), so its eigenvectors are (1,1)(1,\allowbreak 1) and (1,−1)(1,\allowbreak -1), and its eigenvalues are 25+20=4525 + 20 = 45 and 25−20=525 - 20 = 5. As unit vectors, v1=(1,1)/2\mathbf{v}_1 = (1,\allowbreak 1)/\sqrt{2} and v2=(1,−1)/2\mathbf{v}_2 = (1,\allowbreak -1)/\sqrt{2}.
  3. Take square roots: σ1=45=35≈6.708\sigma_1 = \sqrt{45} = 3\sqrt{5} \approx 6.708 and σ2=5≈2.236\sigma_2 = \sqrt{5} \approx 2.236. These are the 6.71 and 2.24 in the instrument.
  4. Find where each vi\mathbf{v}_i lands. Av1=(3+0, 4+5)/2=(3,9)/2\mathbf{A}\mathbf{v}_1 = (3 + 0,\allowbreak \ 4 + 5)/\sqrt{2} = (3,\allowbreak 9)/\sqrt{2}. Divide by σ1=35\sigma_1 = 3\sqrt{5}, using 2⋅35=310\sqrt{2} \cdot 3\sqrt{5} = 3\sqrt{10}: u1=(3,9)/(310)=(1,3)/10\mathbf{u}_1 = (3,\allowbreak 9)/(3\sqrt{10}) = (1,\allowbreak 3)/\sqrt{10}. Likewise Av2=(3−0, 4−5)/2=(3,−1)/2\mathbf{A}\mathbf{v}_2 = (3 - 0,\allowbreak \ 4 - 5)/\sqrt{2} = (3,\allowbreak -1)/\sqrt{2}, and dividing by σ2=5\sigma_2 = \sqrt{5} gives u2=(3,−1)/10\mathbf{u}_2 = (3,\allowbreak -1)/\sqrt{10}.
  5. Check: u1⋅u2=(1⋅3+3⋅(−1))/10=0\mathbf{u}_1\cdot\mathbf{u}_2 = (1 \cdot 3 + 3 \cdot (-1))/10 = 0, and each has length 10/10=1\sqrt{10}/\sqrt{10} = 1.

So A\mathbf{A} stretches the diagonal direction (1,1)/2(1,\allowbreak 1)/\sqrt{2} the most, by 6.708, onto the direction (1,3)/10(1,\allowbreak 3)/\sqrt{10}, and the other diagonal the least, by 2.236. A quick check: σ1σ2=45×5=225=15\sigma_1\sigma_2 = \sqrt{45 \times 5} = \sqrt{225} = 15, which is ∣det⁡A∣=∣3⋅5−0⋅4∣|\det\mathbf{A}| = |3 \cdot 5 - 0 \cdot 4|. In general ∣det⁡A∣|\det\mathbf{A}| is the product of the singular values, since the two rotations have determinant ±1\pm 1 and determinants multiply (the rule from module 3).

Two connections to what came before:

  • For a symmetric matrix, the singular values are the sizes of the eigenvalues. Start from A=QΛQ⊤\mathbf{A} = \mathbf{Q}\boldsymbol{\Lambda}\mathbf{Q}^\top. For each negative eigenvalue, move its minus sign into the matching column of the left-hand Q\mathbf{Q}: flipping a column keeps that matrix orthogonal, and the middle becomes the diagonal of sizes ∣λi∣|\lambda_i|. List the eigenvalues largest size first, moving the columns of both Q\mathbf{Q}'s to match, and that is an SVD. A symmetric matrix with eigenvalues 3 and −5-5 has singular values 5 and 3.
  • PCA is an SVD. If the centered data is X~=UΣV⊤\tilde{\mathbf{X}} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top, then X~⊤X~=VΣ⊤U⊤UΣV⊤=VΣ⊤ΣV⊤\tilde{\mathbf{X}}^\top\tilde{\mathbf{X}} = \mathbf{V}\boldsymbol{\Sigma}^\top\mathbf{U}^\top\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top = \mathbf{V}\boldsymbol{\Sigma}^\top\boldsymbol{\Sigma}\mathbf{V}^\top, and Σ⊤Σ\boldsymbol{\Sigma}^\top\boldsymbol{\Sigma} is diagonal with the σi2\sigma_i^2 on it. So the principal components are the columns of V\mathbf{V} and the variances are σi2/(n−1)\sigma_i^2/(n-1). Libraries usually compute PCA this way because it avoids forming X~⊤X~\tilde{\mathbf{X}}^\top\tilde{\mathbf{X}}, which squares the numbers and loses precision.

Back to the opening shear. S⊤S=[1021][1201]=[1225]\mathbf{S}^\top\mathbf{S} = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}\begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 2 & 5 \end{bmatrix} has trace 6 and determinant 5−4=15 - 4 = 1, so its characteristic equation is λ2−6λ+1=0\lambda^2 - 6\lambda + 1 = 0 and

λ=6±36−42=6±422=3±22.\lambda = \frac{6 \pm \sqrt{36 - 4}}{2} = \frac{6 \pm 4\sqrt{2}}{2} = 3 \pm 2\sqrt{2}.

Their square roots are neater than they look: (2±1)2=2±22+1=3±22(\sqrt{2} \pm 1)^2 = 2 \pm 2\sqrt{2} + 1 = 3 \pm 2\sqrt{2}, so the singular values are 2+1≈2.414\sqrt{2} + 1 \approx 2.414 and 2−1≈0.414\sqrt{2} - 1 \approx 0.414. Eigenvalues 1 and 1; singular values 2.414 and 0.414, whose product is (2+1)(2−1)=2−1=1=det⁡S(\sqrt{2} + 1)(\sqrt{2} - 1) = 2 - 1 = 1 = \det\mathbf{S}.

To recap: the singular values are the square roots of the eigenvalues of A⊤A\mathbf{A}^\top\mathbf{A}; the eigenvectors of A⊤A\mathbf{A}^\top\mathbf{A} are the input directions vi\mathbf{v}_i, and ui=Avi/σi\mathbf{u}_i = \mathbf{A}\mathbf{v}_i/\sigma_i are where they land. Work one through by hand.

On paperAn SVD by hand

Find the SVD of A=[22−11]\mathbf{A} = \begin{bmatrix} 2 & 2 \\ -1 & 1 \end{bmatrix} by hand, following the worked example in the lesson.

  1. Compute A⊤A\mathbf{A}^\top\mathbf{A}, its eigenvalues, and its unit eigenvectors v1,v2\mathbf{v}_1,\allowbreak \mathbf{v}_2.
  2. Take square roots to get σ1≥σ2\sigma_1 \ge \sigma_2.
  3. Compute ui=Avi/σi\mathbf{u}_i = \mathbf{A}\mathbf{v}_i/\sigma_i and check that they are perpendicular unit vectors.
  4. Check that σ1σ2=∣det⁡A∣\sigma_1\sigma_2 = |\det\mathbf{A}|.

Enter σ1\sigma_1 and σ2\sigma_2 below as a column, larger first. Exact forms such as sqrt(8) are accepted, or give 3 decimal places.

Work it on real paper: writing each step is the point. Then check your final answer here and compare your working with the walk-through.

sigma 1 and sigma 2 as a column, larger first (you can type sqrt(8))

One entry per box, top to bottom. 0.25, -2, 3/4 and sqrt(2) all work. Enter moves to the next empty box and checks once all are filled.

The gain of a matrix

The ellipse already says the most useful thing about singular values: no point of the unit circle lands farther out than σ1\sigma_1. Stated for every vector, not just unit ones, that is a bound on growth:

∣Ax∣≤σ1 ∣x∣for every x,|\mathbf{A}\mathbf{x}| \le \sigma_1\,|\mathbf{x}| \quad\text{for every } \mathbf{x},

with equality when x\mathbf{x} points along v1\mathbf{v}_1. For a square matrix the smallest singular value is likewise the least it can stretch a vector: ∣Ax∣≥σn∣x∣|\mathbf{A}\mathbf{x}| \ge \sigma_n|\mathbf{x}|.

Go slower: Proof of the bound

Write x\mathbf{x} in the perpendicular unit basis v1,…,vn\mathbf{v}_1,\allowbreak \ldots,\allowbreak \mathbf{v}_n: x=c1v1+⋯+cnvn\mathbf{x} = c_1\mathbf{v}_1 + \cdots + c_n\mathbf{v}_n. Because the basis vectors are perpendicular with length 1, the Pythagorean theorem gives ∣x∣2=c12+⋯+cn2|\mathbf{x}|^2 = c_1^2 + \cdots + c_n^2.

Apply A\mathbf{A}, using Avi=σiui\mathbf{A}\mathbf{v}_i = \sigma_i\mathbf{u}_i: Ax=c1σ1u1+⋯+cnσnun\mathbf{A}\mathbf{x} = c_1\sigma_1\mathbf{u}_1 + \cdots + c_n\sigma_n\mathbf{u}_n. The ui\mathbf{u}_i are also perpendicular unit vectors, so again by Pythagoras

∣Ax∣2=c12σ12+⋯+cn2σn2.|\mathbf{A}\mathbf{x}|^2 = c_1^2\sigma_1^2 + \cdots + c_n^2\sigma_n^2.

Every σi2\sigma_i^2 is at most σ12\sigma_1^2, so

∣Ax∣2≤σ12 (c12+⋯+cn2)=σ12 ∣x∣2.|\mathbf{A}\mathbf{x}|^2 \le \sigma_1^2\,(c_1^2 + \cdots + c_n^2) = \sigma_1^2\,|\mathbf{x}|^2.

Take square roots. Equality needs all the weight on σ1\sigma_1, that is, x\mathbf{x} along v1\mathbf{v}_1. Replacing "at most σ12\sigma_1^2" by "at least σn2\sigma_n^2" gives the lower bound.

You will meet these numbers under other names. Many sources call σ1\sigma_1 the spectral norm of A\mathbf{A} and write it ∥A∥2\|\mathbf{A}\|_2 (double bars are the usual notation for a norm, and the 2 picks this particular one); np.linalg.norm(A, 2) computes it. For a square matrix, the ratio σ1/σn\sigma_1/\sigma_n of the most A\mathbf{A} stretches any direction to the least is the condition number κ\kappa that inverses and systems promised to make precise, and np.linalg.cond computes it exactly this way. For [3045]\begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}, κ=45/5=9=3\kappa = \sqrt{45}/\sqrt{5} = \sqrt{9} = 3.

Eigenvalues are bounded by σ1\sigma_1. An eigenvector is a vector too, so the bound applies to it. If Av=λv\mathbf{A}\mathbf{v} = \lambda\mathbf{v}, then ∣λ∣ ∣v∣=∣Av∣≤σ1∣v∣|\lambda|\,|\mathbf{v}| = |\mathbf{A}\mathbf{v}| \le \sigma_1|\mathbf{v}|; divide by ∣v∣|\mathbf{v}| to get ∣λ∣≤σ1|\lambda| \le \sigma_1, and so ρ(A)≤σ1\rho(\mathbf{A}) \le \sigma_1. For symmetric matrices they are equal. For the shear, ρ=1\rho = 1 while σ1≈2.414\sigma_1 \approx 2.414. For the matrix C=[0.5300.5]\mathbf{C} = \begin{bmatrix} 0.5 & 3 \\ 0 & 0.5 \end{bmatrix} in the trap of the powers lesson, ρ=0.5\rho = 0.5 while σ1≈3.08\sigma_1 \approx 3.08: the eigenvalues promise decay in the long run, and the large σ1\sigma_1 is what leaves room for the growth in its first steps.

To recap: σ1\sigma_1 is the gain of A\mathbf{A}, the most it can multiply any length; it goes by the names spectral norm and ∥A∥2\|\mathbf{A}\|_2; and it is never smaller than the spectral radius. The next exercise shows how far apart the two can be.

Work it outThe largest stretch

What is the largest singular value of A=[0−320]\mathbf{A} = \begin{bmatrix} 0 & -3 \\ 2 & 0 \end{bmatrix}? (Its eigenvalues are ±i6\pm i\sqrt{6}, of modulus about 2.449. That is not the answer.) Enter a single number.

sigma 1

Type a number: 0.25, -2, 3/4 and sqrt(2) all work. Enter checks.

Gains through a chain of layers

A single bound for a single matrix would be a curiosity. Its real use is that it chains: a vector passing through many different matrices, as activations do through a deep network and gradients do on the way back.

Chains of different matrices. Apply the bound one factor at a time. First ∣A1x∣≤σ1(A1) ∣x∣|\mathbf{A}_1\mathbf{x}| \le \sigma_1(\mathbf{A}_1)\,|\mathbf{x}|. Then A2\mathbf{A}_2 acts on the vector A1x\mathbf{A}_1\mathbf{x}, so ∣A2A1x∣≤σ1(A2) ∣A1x∣≤σ1(A2) σ1(A1) ∣x∣|\mathbf{A}_2\mathbf{A}_1\mathbf{x}| \le \sigma_1(\mathbf{A}_2)\,|\mathbf{A}_1\mathbf{x}| \le \sigma_1(\mathbf{A}_2)\,\sigma_1(\mathbf{A}_1)\,|\mathbf{x}|. And so on down the chain:

∣Ak⋯A2A1x∣≤σ1(Ak)⋯σ1(A2) σ1(A1) ∣x∣.|\mathbf{A}_k\cdots\mathbf{A}_2\mathbf{A}_1\mathbf{x}| \le \sigma_1(\mathbf{A}_k)\cdots\sigma_1(\mathbf{A}_2)\,\sigma_1(\mathbf{A}_1)\,|\mathbf{x}|.

Eigenvalues cannot give a bound like this, because the eigenvalues of a product are not the products of the eigenvalues. For example, [0100]\begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} and [0010]\begin{bmatrix} 0 & 0 \\ 1 & 0 \end{bmatrix} are triangular with both eigenvalues 0, yet their product [1000]\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} has the eigenvalue 1.

Gradients in real networks pass through a different matrix at every layer, and in a recurrent network through W⊤\mathbf{W}^\top times a different diagonal matrix D\mathbf{D} of tanh slopes at every step. Backpropagation through time uses exactly this bound. A diagonal matrix stretches by at most its largest entry in size, which for tanh slopes is at most 1. And W⊤\mathbf{W}^\top has the same singular values as W\mathbf{W}: transposing the SVD gives W⊤=VΣ⊤U⊤\mathbf{W}^\top = \mathbf{V}\boldsymbol{\Sigma}^\top\mathbf{U}^\top, another SVD with the same σi\sigma_i. So each step stretches the gradient by at most σ1(W)\sigma_1(\mathbf{W}), and if σ1(W)<1\sigma_1(\mathbf{W}) < 1 the gradient from kk steps back is guaranteed to shrink at least like σ1(W)k\sigma_1(\mathbf{W})^k. (The bound runs one way only: σ1>1\sigma_1 > 1 allows growth but does not force it.)

Initialization. A layer computes Wx\mathbf{W}\mathbf{x}. Stack dozens of layers and their stretches multiply, so a network whose weight matrices stretch too much blows its activations up, and one that shrinks too much fades them out. For a random n×nn \times n matrix whose entries are independent with mean 0 and variance 1/n1/n, the squared length is preserved on average: the expected value of ∣Wx∣2|\mathbf{W}\mathbf{x}|^2 is ∣x∣2|\mathbf{x}|^2. That is the reasoning behind the initialization scales in neurons and layers, which adjusts them for the nonlinearity.

Go slower: Why variance 1/n preserves length on average

Entry ii of Wx\mathbf{W}\mathbf{x} is ∑jWijxj\sum_j W_{ij}x_j. Its square is a double sum over pairs, ∑j∑lWijWil xjxl\sum_j\sum_l W_{ij}W_{il}\,x_jx_l. Take the expected value (the average over random draws of W\mathbf{W}, with x\mathbf{x} fixed), one term at a time. For j≠lj \ne l the two entries are independent with mean 0, so E[WijWil]=E[Wij] E[Wil]=0\mathbb{E}[W_{ij}W_{il}] = \mathbb{E}[W_{ij}]\,\mathbb{E}[W_{il}] = 0. For j=lj = l, E[Wij2]=1/n\mathbb{E}[W_{ij}^2] = 1/n, the variance. Only the j=lj = l terms survive:

E[(Wx)i2]=∑j1nxj2=∣x∣2n.\mathbb{E}\big[(\mathbf{W}\mathbf{x})_i^2\big] = \sum_j \frac{1}{n}x_j^2 = \frac{|\mathbf{x}|^2}{n}.

There are nn entries, each with that expected square, so E[∣Wx∣2]=n⋅∣x∣2/n=∣x∣2\mathbb{E}\big[|\mathbf{W}\mathbf{x}|^2\big] = n \cdot |\mathbf{x}|^2/n = |\mathbf{x}|^2.

"On average" hides a spread. This code draws such a matrix with n=256n = 256, prints its largest and smallest singular values, and counts how many singular values fall in each range; then it does the same for a random orthogonal matrix.

⌘+Enter runs · edit freelyPython sleeps until you run code

The mean of the squared singular values is close to 1, which is the "on average" promise. But the singular values themselves spread from nearly 0 up to about 2: a random direction keeps its length on average, while some directions are nearly erased and others roughly doubled, at every layer. An orthogonal matrix has every singular value exactly 1, which is why orthogonal initialization is a popular choice for recurrent weight matrices.

To recap: singular values multiply through a chain, so the product of the σ1\sigma_1's bounds any growth, and a network stays well behaved when its layers' singular values sit near 1. Test what singular values do and do not guarantee.

Quick checkWhat singular values guarantee

A 2x2 matrix A\mathbf{A} has singular values 4 and 0.5. Which statements must be true? Select every one.

Choose every option that applies, then check.

Keeping the top singular values

The SVD sorts a matrix's stretches from largest to smallest. Throwing away the small ones gives a cheaper matrix that does almost the same job. This is where the best layers in module 3's low-rank instrument came from.

Write the SVD with the outer-product view of matrix multiplication: UΣV⊤\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top is (column ii of UΣ\mathbf{U}\boldsymbol{\Sigma}) times (row ii of V⊤\mathbf{V}^\top), summed over ii. Column ii of UΣ\mathbf{U}\boldsymbol{\Sigma} is σiui\sigma_i\mathbf{u}_i and row ii of V⊤\mathbf{V}^\top is vi⊤\mathbf{v}_i^\top, so

A=σ1u1v1⊤+σ2u2v2⊤+⋯+σrurvr⊤.\mathbf{A} = \sigma_1\mathbf{u}_1\mathbf{v}_1^\top + \sigma_2\mathbf{u}_2\mathbf{v}_2^\top + \cdots + \sigma_r\mathbf{u}_r\mathbf{v}_r^\top.

Each term is a rank-one matrix, a column times a row, the kind you met in rank and low-rank updates, and rr, the number of nonzero singular values, is the rank of A\mathbf{A}. (Every output Ax\mathbf{A}\mathbf{x} is a combination of u1,…,ur\mathbf{u}_1,\allowbreak \ldots,\allowbreak \mathbf{u}_r, each ui=Avi/σi\mathbf{u}_i = \mathbf{A}\mathbf{v}_i/\sigma_i is itself an output, and perpendicular vectors are independent, so exactly rr dimensions survive.) This is how np.linalg.matrix_rank finds the rank, as that lesson promised: it counts the singular values above a small tolerance, so that rounding noise does not count as a dimension.

The terms come sorted by importance. Keeping the first kk gives

Ak=σ1u1v1⊤+⋯+σkukvk⊤.\mathbf{A}_k = \sigma_1\mathbf{u}_1\mathbf{v}_1^\top + \cdots + \sigma_k\mathbf{u}_k\mathbf{v}_k^\top.

The error formula is the easy half, and it follows from one fact: rotating or reflecting does not change the Frobenius norm.

Go slower: Why the error is the sum of the dropped squares

Step 1. For an orthogonal Q\mathbf{Q} and any matrix M\mathbf{M} with matching shape, ∣QM∣F=∣M∣F|\mathbf{Q}\mathbf{M}|_F = |\mathbf{M}|_F. The squared Frobenius norm is the sum of the squared lengths of the columns, column jj of QM\mathbf{Q}\mathbf{M} is Q\mathbf{Q} times column jj of M\mathbf{M}, and Q\mathbf{Q} keeps every length. The same holds for ∣MQ∣F|\mathbf{M}\mathbf{Q}|_F, because transposing does not change the sum of squared entries and MQ\mathbf{M}\mathbf{Q} transposed is Q⊤M⊤\mathbf{Q}^\top\mathbf{M}^\top, with Q⊤\mathbf{Q}^\top orthogonal too.

Step 2. Subtract: A−Ak=σk+1uk+1vk+1⊤+⋯+σrurvr⊤=UΣ′V⊤\mathbf{A} - \mathbf{A}_k = \sigma_{k+1}\mathbf{u}_{k+1}\mathbf{v}_{k+1}^\top + \cdots + \sigma_r\mathbf{u}_r\mathbf{v}_r^\top = \mathbf{U}\boldsymbol{\Sigma}'\mathbf{V}^\top, where Σ′\boldsymbol{\Sigma}' is Σ\boldsymbol{\Sigma} with its first kk diagonal entries set to zero.

Step 3. By step 1, applied once for U\mathbf{U} and once for V⊤\mathbf{V}^\top, ∣A−Ak∣F2=∣Σ′∣F2=σk+12+⋯+σr2|\mathbf{A} - \mathbf{A}_k|_F^2 = |\boldsymbol{\Sigma}'|_F^2 = \sigma_{k+1}^2 + \cdots + \sigma_r^2. With k=0k = 0 this gives ∣A∣F2=σ12+⋯+σr2|\mathbf{A}|_F^2 = \sigma_1^2 + \cdots + \sigma_r^2.

The hard half, that no other rank-kk matrix gets closer, needs a longer argument, and we take it on trust.

Worked example. For A=[3045]\mathbf{A} = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix} the best rank-one approximation uses σ1=35\sigma_1 = 3\sqrt{5}, u1=(1,3)/10\mathbf{u}_1 = (1,\allowbreak 3)/\sqrt{10} and v1=(1,1)/2\mathbf{v}_1 = (1,\allowbreak 1)/\sqrt{2} from the worked example above. The column (1,3)(1,\allowbreak 3) times the row (1,1)(1,\allowbreak 1) is [1133]\begin{bmatrix} 1 & 1 \\ 3 & 3 \end{bmatrix}, and the numbers in front combine as 35/(102)=35/20=35/(25)=3/23\sqrt{5}/(\sqrt{10}\sqrt{2}) = 3\sqrt{5}/\sqrt{20} = 3\sqrt{5}/(2\sqrt{5}) = 3/2:

A1=σ1u1v1⊤=32[1133]=[1.51.54.54.5].\mathbf{A}_1 = \sigma_1\mathbf{u}_1\mathbf{v}_1^\top = \frac{3}{2}\begin{bmatrix} 1 & 1 \\ 3 & 3 \end{bmatrix} = \begin{bmatrix} 1.5 & 1.5 \\ 4.5 & 4.5 \end{bmatrix}.

The error is A−A1=[3−1.50−1.54−4.55−4.5]=[1.5−1.5−0.50.5]\mathbf{A} - \mathbf{A}_1 = \begin{bmatrix} 3 - 1.5 & 0 - 1.5 \\ 4 - 4.5 & 5 - 4.5 \end{bmatrix} = \begin{bmatrix} 1.5 & -1.5 \\ -0.5 & 0.5 \end{bmatrix}. Its squared entries add to 2.25+2.25+0.25+0.25=52.25 + 2.25 + 0.25 + 0.25 = 5, which is σ22\sigma_2^2, as promised.

Storage. An m×nm \times n matrix has mnmn entries. Ak\mathbf{A}_k needs only the kk columns σiui\sigma_i\mathbf{u}_i (length mm) and the kk rows vi⊤\mathbf{v}_i^\top (length nn): k(m+n)k(m + n) numbers. For a 4096×40964096 \times 4096 matrix at k=16k = 16, that is 16×(4096+4096)=16×8192=131,07216 \times (4096 + 4096) = 16 \times 8192 = 131{,}072 numbers instead of 40962=16,777,2164096^2 = 16{,}777{,}216, under 1%. Whether that is a good trade depends entirely on how fast the singular values fall.

The instrument below is the one from module 3, now with the singular values shown. It treats a 16 by 16 picture of a face as a matrix A\mathbf{A} and shows three pictures side by side: A\mathbf{A}, its rank-kk version Ak\mathbf{A}_k, and what is missing, A−Ak\mathbf{A} - \mathbf{A}_k. Below them are the slider for kk, the layer σkukvk⊤\sigma_k\mathbf{u}_k\mathbf{v}_k^\top that was added last, and a bar for every singular value, with the kept ones in lime.

Now build the truncation yourself and look at an error curve for a picture made of two smooth patterns plus noise.

Code itKeep the top singular values

Build truncated-SVD tools and look at an error curve.

  • rank_k(A, k): keep the kk largest singular values from np.linalg.svd and multiply back.
  • reconstruction_errors(A): the Frobenius errors ∣A−Ak∣F|\mathbf{A} - \mathbf{A}_k|_F for k=0,1,…,min⁡(m,n)k = 0,\allowbreak 1,\allowbreak \ldots,\allowbreak \min(m,\allowbreak n), using rank_k.
  • smallest_rank(A, rel_tol): the smallest kk whose error is at most rel_tol times ∣A∣F|\mathbf{A}|_F, computed from the singular values alone with the Eckart-Young formula.

The code at the bottom draws a small image, its rank-2 version, and the error against kk.

⌘+Enter runsPython sleeps until you run code
Write your code where the starter says raise NotImplementedError, then press Run tests. Each check says what it expects.

Finally, the confusion this lesson set out to clear up, in your own words.

In your own wordsEigenvalues are not the gain

A colleague says: "All the eigenvalues of my weight matrix are smaller than 1 in size, so no vector can get longer when it passes through this layer." Explain what is wrong, using the difference between eigenvalues and singular values, and say when the colleague's reasoning would be right.

A few sentences first: 0 of 60 characters.

Saved in this browser as you type.

Next: the module checkpoint