Linear AlgebraThe Singular Value Decomposition3 of 6
The Singular Value Decomposition · 3

Low-Rank Approximation and Compression

A large grid of data can hold millions of numbers, and we want a way to store and work with it using only a tiny fraction of those numbers.

1

Compressing a Grid into Column-Times-Row Layers

First, let's see when an entire grid of numbers can be built from a single vertical column and a single horizontal row.

Compressing a Grid into Column-Times-Row Layers
1,0001{,}000
1,0001{,}000
1,000×1,000=1,000,000\begin{aligned} &1{,}000 \times 1{,}000 \\ &= 1{,}000{,}000 \end{aligned}
numbers needed=  ?\begin{aligned} &\text{numbers needed} \\ &= \;? \end{aligned}

When every row of a grid is a multiple of the same horizontal pattern, the whole grid factors into a single column-times-row product, called a Rank 1 matrix (or a single layer):

[246248124123110203010]=[24110]⏟row multipliers[1231]⏟base pattern\displaystyle \begin{bmatrix} 2 & 4 & 6 & 2 \\ 4 & 8 & 12 & 4 \\ 1 & 2 & 3 & 1 \\ 10 & 20 & 30 & 10 \end{bmatrix} = \underbrace{\layerone{\begin{bmatrix} 2 \\ 4 \\ 1 \\ 10 \end{bmatrix}}}_{\text{row multipliers}} \underbrace{\layerone{\begin{bmatrix} 1 & 2 & 3 & 1 \end{bmatrix}}}_{\text{base pattern}}

In a single column-times-row layer, every row of the pixel grid is a multiple of the top pattern, so one layer can only ever make lined-up horizontal and vertical bands like stripes or plaid.

In a single column-times-row layer, every row of the pixel grid is a scaled copy of the top pattern, so one layer can only ever make aligned stripes or plaid.

To build grids whose rows don't share a single pattern, we stack multiple column-times-row layers by adding them entry by entry. The rank of a matrix is the fewest layers needed to build it.

On an m×nm \times n grid, storing one layer takes m+nm + n numbers (one column of length mm plus one row of length nn) instead of m×nm \times n numbers, so kk layers take k(m+n)k(m + n) numbers.

5 layers\htmlClass{lc-blue}{\text{5 layers}}
10,000 numbers\text{10,000 numbers}
≈\approx
all 1,000 layers\htmlClass{lc-blue}{\text{all 1,000 layers}}
1,000,000 pixels\text{1,000,000 pixels}
the other 995 layers add\htmlClass{lc-orange}{\text{the other 995 layers add}}
only faint camera static\htmlClass{lc-orange}{\text{only faint camera static}}

Real photographs and datasets almost always have tiny noise that forces an exact rebuild to use all 1,0001{,}000 layers, which takes 1,000×(1,000+1,000)=2,000,0001{,}000 \times (1{,}000 + 1{,}000) = 2{,}000{,}000 numbers, twice as many as the original grid. Instead of keeping every layer just to keep invisible static, low-rank approximation keeps only the handful of strongest layers that hold the main picture.

2

Pulling Out the Best Layers with the SVD

When we start with a finished matrix A\built{A}, its layers are already added together and mixed up inside the grid. We want a way to pull out the best layers of A\built{A}, sorted from strongest pattern to weakest detail.

To do that, we put together two facts:

Pulling Out the Best Layers with the SVD
A\htmlClass{lc-blue}{A}
==
++
++
+⋯+ \cdots
UU
u1\htmlClass{lc-green}{u_1}
u2\htmlClass{lc-pink}{u_2}
u3\htmlClass{lc-violet}{u_3}
⋯\cdots
Σ\Sigma
σ1\htmlClass{lc-green}{\sigma_1}
σ2\htmlClass{lc-pink}{\sigma_2}
σ3\htmlClass{lc-violet}{\sigma_3}
⋱\ddots
VTV^T
v1T\htmlClass{lc-green}{v_1^T}
v2T\htmlClass{lc-pink}{v_2^T}
v3T\htmlClass{lc-violet}{v_3^T}
⋮\vdots
==
σ1u1\htmlClass{lc-green}{\sigma_1 u_1}
v1T\htmlClass{lc-green}{v_1^T}
Layer 1\htmlClass{lc-green}{\text{Layer 1}}
++
σ2u2\htmlClass{lc-pink}{\sigma_2 u_2}
v2T\htmlClass{lc-pink}{v_2^T}
Layer 2\htmlClass{lc-pink}{\text{Layer 2}}
+⋯+ \cdots

Multiplying UΣU\Sigma multiplies each column uiu_i by σi\sigma_i, and multiplying by VTV^T pairs each scaled column with the matching row viTv_i^T:

A\displaystyle \built{A} =UΣVT\displaystyle = U\Sigma V^T =σ1⏟weightu1v1T⏟Layer 1+σ2⏟weightu2v2T⏟Layer 2+⋯+σr⏟weighturvrT⏟Layer r\displaystyle = \layerone{\underbrace{\underbrace{\sigma_1}_{\text{weight}} u_1 v_1^T}_{\text{Layer 1}}} + \layertwo{\underbrace{\underbrace{\sigma_2}_{\text{weight}} u_2 v_2^T}_{\text{Layer 2}}} + \dots + \underbrace{\underbrace{\sigma_r}_{\text{weight}} u_r v_r^T}_{\text{Layer } r}

Keeping the first kk terms in this sum and dropping the rest gives the best Rank kk approximation of A\built{A}:

Ak\displaystyle \built{A_k} =σ1u1v1T+σ2u2v2T+⋯+σkukvkT\displaystyle = \layerone{\sigma_1 u_1 v_1^T} + \layertwo{\sigma_2 u_2 v_2^T} + \dots + \sigma_k u_k v_k^T

The subscript kk in Ak\built{A_k} tells you how many layers are kept, not a row or column entry. Also notice that VTV^T is already transposed in A=UΣVT\built{A} = U\Sigma V^T, so you read each horizontal row viTv_i^T straight across row ii of VTV^T without transposing it again.

3

Worked Example: Rank 1 and Rank 2 Approximations

Let's find the best Rank 1 approximation A1\built{A_1} and Rank 2 approximation A2\built{A_2} of

A=[424227048426042]\displaystyle \built{A} = \begin{bmatrix} 42 & 42 & 27 \\ 0 & 48 & 42 \\ 6 & 0 & 42 \end{bmatrix}

given its Singular Value Decomposition:

U=[23231323−13−2313−2323],Σ=[900003600027],VT=[1323232313−2323−2313]\displaystyle \begin{aligned} U &= \begin{bmatrix} \layerone{\tfrac{2}{3}} & \layertwo{\tfrac{2}{3}} & \layerthree{\tfrac{1}{3}} \\ \layerone{\tfrac{2}{3}} & \layertwo{-\tfrac{1}{3}} & \layerthree{-\tfrac{2}{3}} \\ \layerone{\tfrac{1}{3}} & \layertwo{-\tfrac{2}{3}} & \layerthree{\tfrac{2}{3}} \end{bmatrix}, \\ \Sigma &= \begin{bmatrix} \layerone{90} & 0 & 0 \\ 0 & \layertwo{36} & 0 \\ 0 & 0 & \layerthree{27} \end{bmatrix}, \\ V^T &= \begin{bmatrix} \layerone{\tfrac{1}{3}} & \layerone{\tfrac{2}{3}} & \layerone{\tfrac{2}{3}} \\ \layertwo{\tfrac{2}{3}} & \layertwo{\tfrac{1}{3}} & \layertwo{-\tfrac{2}{3}} \\ \layerthree{\tfrac{2}{3}} & \layerthree{-\tfrac{2}{3}} & \layerthree{\tfrac{1}{3}} \end{bmatrix} \end{aligned}
Worked Example: Rank 1 and Rank 2 Approximations
A1=σ1u1v1T=  ?A2=A1+σ2u2v2T=  ?\displaystyle \begin{aligned} \built{A_1} &= \layerone{\sigma_1 u_1 v_1^T} = \;? \\[4pt] \built{A_2} &= \built{A_1} + \layertwo{\sigma_2 u_2 v_2^T} = \;? \end{aligned}
Text solution
Multiply σ1\layerone{\sigma_1}, column 1 of UU, and row 1 of VTV^T to build A1\built{A_1}Pull the 13\frac{1}{3} out of both vectors first (90×13×13=10\layerone{90} \times \frac{1}{3} \times \frac{1}{3} = 10) so you only have to multiply whole numbers.
A1=σ1u1v1T=90[232313][132323]=10[221][122]=10[244244122]=[204040204040102020]\displaystyle \begin{aligned} \built{A_1} = \layerone{\sigma_1 u_1 v_1^T} &= \layerone{90} \layerone{\begin{bmatrix} \tfrac{2}{3} \\ \tfrac{2}{3} \\ \tfrac{1}{3} \end{bmatrix}} \layerone{\begin{bmatrix} \tfrac{1}{3} & \tfrac{2}{3} & \tfrac{2}{3} \end{bmatrix}} \\ &= 10 \begin{bmatrix} 2 \\ 2 \\ 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 2 \end{bmatrix} \\ &= 10 \begin{bmatrix} 2 & 4 & 4 \\ 2 & 4 & 4 \\ 1 & 2 & 2 \end{bmatrix} \\ &= \built{\begin{bmatrix} 20 & 40 & 40 \\ 20 & 40 & 40 \\ 10 & 20 & 20 \end{bmatrix}} \end{aligned}
Multiply σ2\layertwo{\sigma_2}, column 2 of UU, and row 2 of VTV^T to build Layer 2Pull out the fractions the same way (36×13×13=4\layertwo{36} \times \frac{1}{3} \times \frac{1}{3} = 4).
σ2u2v2T=36[23−13−23][2313−23]=4[2−1−2][21−2]=4[42−4−2−12−4−24]=[168−16−8−48−16−816]\displaystyle \begin{aligned} \layertwo{\sigma_2 u_2 v_2^T} &= \layertwo{36} \layertwo{\begin{bmatrix} \tfrac{2}{3} \\ -\tfrac{1}{3} \\ -\tfrac{2}{3} \end{bmatrix}} \layertwo{\begin{bmatrix} \tfrac{2}{3} & \tfrac{1}{3} & -\tfrac{2}{3} \end{bmatrix}} \\ &= 4 \begin{bmatrix} 2 \\ -1 \\ -2 \end{bmatrix} \begin{bmatrix} 2 & 1 & -2 \end{bmatrix} \\ &= 4 \begin{bmatrix} 4 & 2 & -4 \\ -2 & -1 & 2 \\ -4 & -2 & 4 \end{bmatrix} \\ &= \layertwo{\begin{bmatrix} 16 & 8 & -16 \\ -8 & -4 & 8 \\ -16 & -8 & 16 \end{bmatrix}} \end{aligned}
Add Layer 2 to A1\built{A_1} entry by entry to get A2\built{A_2}Add the second layer onto A1\built{A_1} rather than starting over.
A2=A1+σ2u2v2T=[204040204040102020]+[168−16−8−48−16−816]=[364824123648−61236]\displaystyle \begin{aligned} \built{A_2} &= \built{A_1} + \layertwo{\sigma_2 u_2 v_2^T} \\ &= \built{\begin{bmatrix} 20 & 40 & 40 \\ 20 & 40 & 40 \\ 10 & 20 & 20 \end{bmatrix}} \\ &\quad + \layertwo{\begin{bmatrix} 16 & 8 & -16 \\ -8 & -4 & 8 \\ -16 & -8 & 16 \end{bmatrix}} \\ &= \built{\begin{bmatrix} 36 & 48 & 24 \\ 12 & 36 & 48 \\ -6 & 12 & 36 \end{bmatrix}} \end{aligned}

So A1\built{A_1} is the closest Rank 1 matrix to A\built{A} (with every row a multiple of [102020]\begin{bmatrix} 10 & 20 & 20 \end{bmatrix}), A2\built{A_2} gets closer to A\built{A} by adding a second layer, and adding the third layer 27u3v3T\layerthree{27u_3v_3^T} rebuilds A\built{A} with zero error.

4

Measuring Error and Energy Kept with Singular Values

To measure how close Ak\built{A_k} is to A\built{A}, we need a way to measure the overall size of a matrix. The Frobenius norm ∥A∥F\|\built{A}\|_F is the square root of the sum of the squares of all entries in the grid, just like the Pythagorean length of a vector. We want to find both ∥A∥F\|\built{A}\|_F and the approximation error ∥A−Ak∥F\|\lost{A - A_k}\|_F directly from the singular values without squaring millions of entries.

Measuring Error and Energy Kept with Singular Values
42\htmlStyle{color:var(--lc-black)}{42}
42\htmlStyle{color:var(--lc-black)}{42}
27\htmlStyle{color:var(--lc-black)}{27}
0\htmlStyle{color:var(--lc-white)}{0}
48\htmlStyle{color:var(--lc-black)}{48}
42\htmlStyle{color:var(--lc-black)}{42}
6\htmlStyle{color:var(--lc-white)}{6}
0\htmlStyle{color:var(--lc-white)}{0}
42\htmlStyle{color:var(--lc-black)}{42}
A\htmlClass{lc-blue}{A}
20\htmlStyle{color:var(--lc-white)}{20}
40\htmlStyle{color:var(--lc-black)}{40}
40\htmlStyle{color:var(--lc-black)}{40}
20\htmlStyle{color:var(--lc-white)}{20}
40\htmlStyle{color:var(--lc-black)}{40}
40\htmlStyle{color:var(--lc-black)}{40}
10\htmlStyle{color:var(--lc-white)}{10}
20\htmlStyle{color:var(--lc-white)}{20}
20\htmlStyle{color:var(--lc-white)}{20}
A1=σ1u1v1T\htmlClass{lc-blue}{A_1} = \htmlClass{lc-green}{\sigma_1 u_1 v_1^T}
∥A−A1∥F=  ?\|\htmlClass{lc-orange}{A - A_1}\|_F = \;?

Splitting the SVD sum at layer kk separates the kept approximation Ak\built{A_k} from the leftover error matrix A−Ak\lost{A - A_k}:

A=σ1u1v1T+⋯+σkukvkT⏟Ak (kept layers)+σk+1uk+1vk+1T+⋯+σrurvrT⏟A−Ak (discarded layers)\displaystyle \begin{aligned} \built{A} = {}&\underbrace{\layerone{\sigma_1 u_1 v_1^T} + \dots + \sigma_k u_k v_k^T}_{\built{A_k} \text{ (kept layers)}} \\ &+ \underbrace{\lost{\sigma_{k+1} u_{k+1} v_{k+1}^T + \dots + \sigma_r u_r v_r^T}}_{\lost{A - A_k} \text{ (discarded layers)}} \end{aligned}

Each unscaled layer uiviTu_i v_i^T has squared size 11, and the layers are perpendicular to each other. So the squared size of any stack of layers is just the sum of its squared singular values (and by the Eckart-Young Theorem, no other Rank kk matrix can get a smaller error):

Total squared size (energy):∥A∥F2=σ12+σ22+⋯+σr2Approximation error:∥A−Ak∥F=σk+12+σk+22+⋯+σr2Share of energy kept:Share kept=σ12+σ22+⋯+σk2σ12+⋯+σk2+σk+12+⋯+σr2\displaystyle \begin{aligned} &\text{Total squared size (energy):} \\ &\|\built{A}\|_F^2 = \layerone{\sigma_1^2} + \layertwo{\sigma_2^2} + \dots + \sigma_r^2 \\[8pt] &\text{Approximation error:} \\ &\|\lost{A - A_k}\|_F = \sqrt{\lost{\sigma_{k+1}^2 + \sigma_{k+2}^2 + \dots + \sigma_r^2}} \\[8pt] &\text{Share of energy kept:} \\ &\text{Share kept} \\ &= \frac{\layerone{\sigma_1^2} + \layertwo{\sigma_2^2} + \dots + \sigma_k^2}{\layerone{\sigma_1^2} + \dots + \sigma_k^2 + \lost{\sigma_{k+1}^2 + \dots + \sigma_r^2}} \end{aligned}

Be careful with the squares: the squared singular values σi2\sigma_i^2 add up (not the unsquared σi\sigma_i), and ∥A−Ak∥F\|\lost{A - A_k}\|_F is the size of the leftover layers, not ∥A∥F−∥Ak∥F\|\built{A}\|_F - \|\built{A_k}\|_F.

Let's find the error and energy share for our 3×33 \times 3 example where σ1=90\layerone{\sigma_1} = \layerone{90}, σ2=36\layertwo{\sigma_2} = \layertwo{36}, and σ3=27\layerthree{\sigma_3} = \layerthree{27}.

Text solution
Sum the squared singular values for the total energy of A\built{A}Square all three singular values and add them up.
∥A∥F2\displaystyle \|\built{A}\|_F^2 =902+362+272\displaystyle = \layerone{90^2} + \layertwo{36^2} + \layerthree{27^2} =8100+1296+729\displaystyle = \layerone{8100} + \layertwo{1296} + \layerthree{729} =10,125\displaystyle = 10{,}125
Add the discarded squares and take the square root for each errorA1\built{A_1} drops σ2=36\lost{\sigma_2} = \lost{36} and σ3=27\lost{\sigma_3} = \lost{27}, while A2\built{A_2} drops only σ3=27\lost{\sigma_3} = \lost{27}.
∥A−A1∥F=362+272=2025=45,∥A−A2∥F=272=27\displaystyle \begin{aligned} \|\lost{A - A_1}\|_F &= \sqrt{\lost{36^2 + 27^2}} \\ &= \sqrt{2025} = 45, \\ \|\lost{A - A_2}\|_F &= \sqrt{\lost{27^2}} = 27 \end{aligned}
Divide the kept squares by 10,12510{,}125 for the share keptCheck how much of the total energy 11 layer and 22 layers keep.
Share kept by A1=810010,125=80%,Share kept by A2=8100+129610,125=939610,125≈92.8%\displaystyle \begin{aligned} \text{Share kept by } \built{A_1} &= \frac{\layerone{8100}}{10{,}125} \\ &= 80\%, \\ \text{Share kept by } \built{A_2} &= \frac{\layerone{8100} + \layertwo{1296}}{10{,}125} \\ &= \frac{9396}{10{,}125} \\ &\approx 92.8\% \end{aligned}

So two layers alone keep 92.8%92.8\% of the matrix's total energy while leaving an error of 2727.

In a photograph, the first few layers have large σi\sigma_i and hold almost all the main picture and squared energy σi2\sigma_i^2. The remaining layers in A−Ak\lost{A - A_k} have tiny σi\sigma_i and hold only faint static that adds up to almost none of the total squared size.

The first few SVD layers of a photograph capture almost all of its visual structure and squared size, while the long tail of weaker layers adds up to faint static.
5

Low-Rank Approximation in the Real World

Real-world grids pack their main patterns into the top layers, while random noise spreads thinly across all the layers, so the weak leftover layers are almost pure noise. That means keeping only the top kk layers lets us compress images, clean noise from data, predict missing movie ratings, and update massive AI weight grids using LoRA (Low-Rank Adaptation).

Low-Rank Approximation in the Real World
==
++
++
++
big-picture\text{big-picture}
trend\text{trend}
random\text{random}
static\text{static}

If you only need a single entry of Ak\built{A_k} at row ii and column jj (such as User ii's predicted rating on Movie jj), don't multiply out the full matrices. In each layer σmumvmT\sigma_m u_m v_m^T, the entry at row ii and column jj only uses entry ii of column umu_m and entry jj of row vmTv_m^T:

(Ak)ij=σ1(u1)i(v1T)j+σ2(u2)i(v2T)j+⋯+σk(uk)i(vkT)j\displaystyle \begin{aligned} (\built{A_k})_{ij} &= \layerone{\sigma_1 (u_1)_i (v_1^T)_j} + \layertwo{\sigma_2 (u_2)_i (v_2^T)_j} \\ &\quad + \dots + \sigma_k (u_k)_i (v_k^T)_j \end{aligned}

Key concepts

Every matrix A\built{A} is a stack of perpendicular column-times-row layers sorted by strength:

A\displaystyle \built{A} =σ1u1v1T+σ2u2v2T+⋯+σrurvrT\displaystyle = \layerone{\sigma_1 u_1 v_1^T} + \layertwo{\sigma_2 u_2 v_2^T} + \dots + \sigma_r u_r v_r^T
Spotting and combining layers without the SVD

If every row of a grid is already a multiple of one pattern, factor it straight into a column times that row (for example, [6293]=[23][31]\begin{bmatrix} 6 & 2 \\ 9 & 3 \end{bmatrix} = \layerone{\begin{bmatrix} 2 \\ 3 \end{bmatrix}}\layerone{\begin{bmatrix} 3 & 1 \end{bmatrix}}, Rank 1). If two layers in a sum have horizontal rows that are multiples of each other, pull the multiple into the column and add the columns together to combine them into one layer (if their vertical columns are multiples instead, pull the multiple into the row and add the rows).

Building the best Rank kk approximation Ak\built{A_k}

Keep the first kk layers σ1u1v1T+⋯+σkukvkT\layerone{\sigma_1 u_1 v_1^T} + \dots + \sigma_k u_k v_k^T, reading each uiu_i from column ii of UU and each viTv_i^T from row ii of VTV^T. If you only need one entry at row ii, column jj, don't build the whole matrix: just add σm(um)i(vmT)j\sigma_m (u_m)_i (v_m^T)_j across the kk layers.

Measuring size, error, and energy kept (don't build the matrices)

When you only need norms or energy percentages, work purely with the squared singular values σi2\sigma_i^2. For singular values 4,3,0\layerone{4}, \layertwo{3}, \layerthree{0}, the total energy is ∥A∥F2=42+32=25\|\built{A}\|_F^2 = \layerone{4^2} + \layertwo{3^2} = 25 (so ∥A∥F=5\|\built{A}\|_F = 5), the Rank 1 error is ∥A−A1∥F=32+02=3\|\lost{A - A_1}\|_F = \sqrt{\lost{3^2 + 0^2}} = 3, and A1\built{A_1} keeps 4225=64%\frac{\layerone{4^2}}{25} = 64\% of the energy.

When low-rank storage stops saving space

On an m×nm \times n grid, kk layers store k(m+n)k(m + n) numbers instead of mnmn. Once k(m+n)>mnk(m + n) > mn (such as past 250250 layers on a 500×500500 \times 500 grid), storing the layers takes more numbers than storing the original grid.

6

Practice

1

Every row of the matrix M=[6−2429−363−31−2−1]M = \begin{bmatrix} 6 & -2 & 4 & 2 \\ 9 & -3 & 6 & 3 \\ -3 & 1 & -2 & -1 \end{bmatrix} is a multiple of the base pattern [3−121]\begin{bmatrix} 3 & -1 & 2 & 1 \end{bmatrix}. Write MM as a single column-times-row layer using that horizontal row, and state the rank of MM.

Compare the first entry of each row in MM (66, 99, and −3-3) to the first entry 33 of the base pattern: what number multiplies the base row to make each row?

Divide the first entry of each row by 33 to get the vertical row multipliers 2\layerone{2}, 3\layerone{3}, and −1\layerone{-1}:
M=[23−1][3−121]\displaystyle M = \layerone{\begin{bmatrix} 2 \\ 3 \\ -1 \end{bmatrix}} \layerone{\begin{bmatrix} 3 & -1 & 2 & 1 \end{bmatrix}}
(Watch out: write the multipliers as a vertical column [23−1]\layerone{\begin{bmatrix} 2 \\ 3 \\ -1 \end{bmatrix}}, not a horizontal row [23−1]\begin{bmatrix} 2 & 3 & -1 \end{bmatrix}, and don't say rank⁡(M)=3\operatorname{rank}(M) = 3 just because MM has three nonzero rows.) Because the whole grid is built from a single non-zero layer, rank⁡(M)=1\operatorname{rank}(M) = 1.
2

A 3×33 \times 3 matrix BB is built by adding three layers:

B=[12−1][242]+[301][10−1]+[2−13][121]\displaystyle \begin{aligned} B &= \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix} \begin{bmatrix} 2 & 4 & 2 \end{bmatrix} \\ &\quad + \begin{bmatrix} 3 \\ 0 \\ 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & -1 \end{bmatrix} \\ &\quad + \begin{bmatrix} 2 \\ -1 \\ 3 \end{bmatrix} \begin{bmatrix} 1 & 2 & 1 \end{bmatrix} \end{aligned}

What is the rank of BB, and how can BB be written using the fewest possible layers?

Compare the three horizontal rows: are any two of them multiples of the same base pattern?

Notice that the first horizontal row [242]\layerone{\begin{bmatrix} 2 & 4 & 2 \end{bmatrix}} is 22 times the third horizontal row [121]\layerthree{\begin{bmatrix} 1 & 2 & 1 \end{bmatrix}}. Pull that factor of 22 into the first vertical column so both layers share the exact same horizontal row:
[12−1][242]=[24−2][121]\displaystyle \layerone{\begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix} \begin{bmatrix} 2 & 4 & 2 \end{bmatrix}} = \layerone{\begin{bmatrix} 2 \\ 4 \\ -2 \end{bmatrix} \begin{bmatrix} 1 & 2 & 1 \end{bmatrix}}
(Watch out: don't say rank⁡(B)=3\operatorname{rank}(B) = 3 just by counting the three written layers, and don't add the unscaled first column [12−1]+[2−13]=[312]\layerone{\begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix}} + \layerthree{\begin{bmatrix} 2 \\ -1 \\ 3 \end{bmatrix}} = \begin{bmatrix} 3 \\ 1 \\ 2 \end{bmatrix} before factoring out the 22.) Now combine the first and third columns:
([24−2]+[2−13])[121]=[431][121]\displaystyle \left(\layerone{\begin{bmatrix} 2 \\ 4 \\ -2 \end{bmatrix}} + \layerthree{\begin{bmatrix} 2 \\ -1 \\ 3 \end{bmatrix}}\right) \begin{bmatrix} 1 & 2 & 1 \end{bmatrix} = \layerone{\begin{bmatrix} 4 \\ 3 \\ 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 1 \end{bmatrix}}
The remaining two layers do not have rows or columns that are multiples of each other, so rank⁡(B)=2\operatorname{rank}(B) = 2 and
B=[431][121]+[301][10−1]\displaystyle B = \layerone{\begin{bmatrix} 4 \\ 3 \\ 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 1 \end{bmatrix}} + \layertwo{\begin{bmatrix} 3 \\ 0 \\ 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & -1 \end{bmatrix}}
3

A matrix A\built{A} has the Singular Value Decomposition A=UΣVT\built{A} = U\Sigma V^T with

U=[1323232313−2323−2313],Σ=[45000180009],VT=[23231313−232323−13−23]\displaystyle \begin{aligned} U &= \begin{bmatrix} \tfrac{1}{3} & \tfrac{2}{3} & \tfrac{2}{3} \\ \tfrac{2}{3} & \tfrac{1}{3} & -\tfrac{2}{3} \\ \tfrac{2}{3} & -\tfrac{2}{3} & \tfrac{1}{3} \end{bmatrix}, \\ \Sigma &= \begin{bmatrix} 45 & 0 & 0 \\ 0 & 18 & 0 \\ 0 & 0 & 9 \end{bmatrix}, \\ V^T &= \begin{bmatrix} \tfrac{2}{3} & \tfrac{2}{3} & \tfrac{1}{3} \\ \tfrac{1}{3} & -\tfrac{2}{3} & \tfrac{2}{3} \\ \tfrac{2}{3} & -\tfrac{1}{3} & -\tfrac{2}{3} \end{bmatrix} \end{aligned}

Find the best Rank 1 approximation A1\built{A_1} and the best Rank 2 approximation A2\built{A_2} of A\built{A}.

Since the third matrix is already given as VTV^T, do you read v1T\layerone{v_1^T} and v2T\layertwo{v_2^T} from its columns or from its rows?

Pair σ1=45\layerone{\sigma_1} = \layerone{45} with column 1 of UU and row 1 of VTV^T:
A1=σ1u1v1T=45[132323][232313]=5[122][221]=[10105202010202010]\displaystyle \begin{aligned} \built{A_1} = \layerone{\sigma_1 u_1 v_1^T} &= \layerone{45} \layerone{\begin{bmatrix} \tfrac{1}{3} \\ \tfrac{2}{3} \\ \tfrac{2}{3} \end{bmatrix}} \layerone{\begin{bmatrix} \tfrac{2}{3} & \tfrac{2}{3} & \tfrac{1}{3} \end{bmatrix}} \\ &= 5 \begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix} \begin{bmatrix} 2 & 2 & 1 \end{bmatrix} \\ &= \built{\begin{bmatrix} 10 & 10 & 5 \\ 20 & 20 & 10 \\ 20 & 20 & 10 \end{bmatrix}} \end{aligned}
(Watch out: VTV^T is already transposed, so taking its first column [231323]\begin{bmatrix} \tfrac{2}{3} & \tfrac{1}{3} & \tfrac{2}{3} \end{bmatrix} instead of its first row gives the wrong matrix [10510201020201020]\begin{bmatrix} 10 & 5 & 10 \\ 20 & 10 & 20 \\ 20 & 10 & 20 \end{bmatrix}.) Next, build Layer 2 with σ2=18\layertwo{\sigma_2} = \layertwo{18}, column 2 of UU, and row 2 of VTV^T:
σ2u2v2T=18[2313−23][13−2323]=2[21−2][1−22]=[4−882−44−48−8]\displaystyle \begin{aligned} \layertwo{\sigma_2 u_2 v_2^T} &= \layertwo{18} \layertwo{\begin{bmatrix} \tfrac{2}{3} \\ \tfrac{1}{3} \\ -\tfrac{2}{3} \end{bmatrix}} \layertwo{\begin{bmatrix} \tfrac{1}{3} & -\tfrac{2}{3} & \tfrac{2}{3} \end{bmatrix}} \\ &= 2 \begin{bmatrix} 2 \\ 1 \\ -2 \end{bmatrix} \begin{bmatrix} 1 & -2 & 2 \end{bmatrix} \\ &= \layertwo{\begin{bmatrix} 4 & -8 & 8 \\ 2 & -4 & 4 \\ -4 & 8 & -8 \end{bmatrix}} \end{aligned}
(Watch out: don't stop at Layer 2; remember to add Layer 1 and Layer 2 together to get A2\built{A_2}.)
A2=A1+σ2u2v2T=[1421322161416282]\displaystyle \built{A_2} = \built{A_1} + \layertwo{\sigma_2 u_2 v_2^T} = \built{\begin{bmatrix} 14 & 2 & 13 \\ 22 & 16 & 14 \\ 16 & 28 & 2 \end{bmatrix}}
4

A 4×44 \times 4 matrix A\built{A} has singular values σ1=20\layerone{\sigma_1} = \layerone{20}, σ2=12\layertwo{\sigma_2} = \layertwo{12}, σ3=9\layerthree{\sigma_3} = \layerthree{9}, and σ4=0\sigma_4 = 0. Without knowing UU or VTV^T, find (a) the Frobenius norm ∥A∥F\|\built{A}\|_F, (b) the approximation error ∥A−A1∥F\|\lost{A - A_1}\|_F, and (c) the approximation error ∥A−A3∥F\|\lost{A - A_3}\|_F.

Which singular values stay in Ak\built{A_k}, and which ones are left in the discarded error A−Ak\lost{A - A_k}?

(a) Square and add all singular values, then take the square root:
∥A∥F\displaystyle \|\built{A}\|_F =202+122+92+02\displaystyle = \sqrt{\layerone{20^2} + \layertwo{12^2} + \layerthree{9^2} + 0^2} =400+144+81\displaystyle = \sqrt{\layerone{400} + \layertwo{144} + \layerthree{81}} =625\displaystyle = \sqrt{625} =25\displaystyle = 25
(Watch out: don't add the unsquared singular values 20+12+9=4120 + 12 + 9 = 41.)
(b) A1\built{A_1} keeps σ1=20\layerone{\sigma_1} = \layerone{20} and drops σ2=12\lost{\sigma_2} = \lost{12}, σ3=9\lost{\sigma_3} = \lost{9}, and σ4=0\lost{\sigma_4} = \lost{0}:
∥A−A1∥F\displaystyle \|\lost{A - A_1}\|_F =122+92+02\displaystyle = \sqrt{\lost{12^2 + 9^2 + 0^2}} =144+81\displaystyle = \sqrt{\lost{144 + 81}} =225\displaystyle = \sqrt{225} =15\displaystyle = 15
(Watch out: don't subtract the unsquared norms ∥A∥F−∥A1∥F=25−20=5\|\built{A}\|_F - \|\built{A_1}\|_F = 25 - 20 = 5; subtract the squared sizes 625−400=225625 - 400 = 225 and then take the square root.)
(c) A3\built{A_3} drops only σ4=0\lost{\sigma_4} = \lost{0} (three layers rebuild A\built{A} exactly):
∥A−A3∥F\displaystyle \|\lost{A - A_3}\|_F =02\displaystyle = \sqrt{\lost{0^2}} =0\displaystyle = 0
5

A 500×500500 \times 500 grid A\built{A} has five nonzero singular values: σ1=25\sigma_1 = 25, σ2=15\sigma_2 = 15, σ3=10\sigma_3 = 10, σ4=5\sigma_4 = 5, and σ5=5\sigma_5 = 5. (a) What is the fewest number of layers kk needed to keep at least 90%90\% of the total squared size (energy) of A\built{A}, and what percentage does it keep? (b) How many numbers are needed to store those kk layers compared with the original 500×500500 \times 500 grid, and what percentage of the data is saved? (c) On a 500×500500 \times 500 grid, beyond how many layers does storing the layers take more numbers than storing the original grid?

(a) Compare the running total of σi2\sigma_i^2 (not σi\sigma_i) to the total sum of squares. (b)–(c) How many numbers are in one vertical column plus one horizontal row of a 500×500500 \times 500 grid?

(a) The total squared size is 252+152+102+52+52\layerone{25^2} + \layertwo{15^2} + \layerthree{10^2} + 5^2 + 5^2 =625+225+100+25+25{}= \layerone{625} + \layertwo{225} + \layerthree{100} + 25 + 25 =1,000{}= 1{,}000.
(Watch out: if you add the unsquared singular values 25+15+10+5+5=6025 + 15 + 10 + 5 + 5 = 60, three layers give 5060≈83.3%\frac{50}{60} \approx 83.3\% and trick you into picking k=4k = 4 layers.)
Two layers keep 625+2251,000=85%\frac{\layerone{625} + \layertwo{225}}{1{,}000} = 85\%, while three layers keep 625+225+1001,000=9501,000=95%\frac{\layerone{625} + \layertwo{225} + \layerthree{100}}{1{,}000} = \frac{950}{1{,}000} = 95\%, so k=3k = 3 layers (keeping 95%95\%).
(b) One layer stores a column of 500500 numbers and a row of 500500 numbers, or 500+500=1,000500 + 500 = 1{,}000 numbers. (Watch out: don't count only 500500 numbers per layer, which would give 1,5001{,}500 numbers in (b) and 500500 layers in (c).) Three layers take 3×1,000=3,0003 \times 1{,}000 = 3{,}000 numbers compared with 500×500=250,000500 \times 500 = 250{,}000 numbers, saving 250,000−3,000250,000=98.8%\frac{250{,}000 - 3{,}000}{250{,}000} = 98.8\%.
(c) At 250250 layers, 250×1,000=250,000250 \times 1{,}000 = 250{,}000 numbers ties the original grid, so storing the layers takes more numbers beyond 250250 layers (k≥251k \ge 251).
6

In a 4×34 \times 3 user-movie ratings matrix A\built{A}, the top two SVD layers have singular values σ1=20\layerone{\sigma_1} = \layerone{20} and σ2=10\layertwo{\sigma_2} = \layertwo{10}, with unit vectors

u1=[0.50.50.50.5],v1T=[0.60.80],u2=[0.5−0.50.5−0.5],v2T=[0.8−0.60]\displaystyle \begin{aligned} \layerone{u_1} &= \layerone{\begin{bmatrix} 0.5 \\ 0.5 \\ 0.5 \\ 0.5 \end{bmatrix}}, \\[4pt] \layerone{v_1^T} &= \layerone{\begin{bmatrix} 0.6 & 0.8 & 0 \end{bmatrix}}, \\[4pt] \layertwo{u_2} &= \layertwo{\begin{bmatrix} 0.5 \\ -0.5 \\ 0.5 \\ -0.5 \end{bmatrix}}, \\[4pt] \layertwo{v_2^T} &= \layertwo{\begin{bmatrix} 0.8 & -0.6 & 0 \end{bmatrix}} \end{aligned}

Using the Rank 2 approximation A2\built{A_2}, predict the missing rating for User 2 (row 2) on Movie 1 (column 1) without computing the full matrices.

To find just row 2, column 1 of each layer σmumvmT\sigma_m u_m v_m^T, which single entry of umu_m and which single entry of vmTv_m^T multiply together?

Multiply each singular value by entry 2 of umu_m and entry 1 of vmTv_m^T, then add the two layers:
(A2)2,1\displaystyle (\built{A_2})_{2,1} =20(0.5)(0.6)+10(−0.5)(0.8)\displaystyle = \layerone{20(0.5)(0.6)} + \layertwo{10(-0.5)(0.8)} =6+(−4)\displaystyle = \layerone{6} + (\layertwo{-4}) =2\displaystyle = 2
(Watch out: for User 2, be sure to use the second entry of u2\layertwo{u_2}, which is −0.5\layertwo{-0.5}; taking the first entry +0.5+0.5 adds +4+4 instead of −4-4 and gives 1010, and forgetting the weights σ1=20\layerone{\sigma_1} = \layerone{20} and σ2=10\layertwo{\sigma_2} = \layertwo{10} gives −0.1-0.1.) The predicted rating is 22 stars.