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
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):
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×n grid, storing one layer takes m+n numbers (one column of length m plus one row of length n) instead of m×n numbers, so k layers take k(m+n) numbers.
Real photographs and datasets almost always have tiny noise that forces an exact rebuild to use all 1,000 layers, which takes 1,000×(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, its layers are already added together and mixed up inside the grid. We want a way to pull out the best layers of A, sorted from strongest pattern to weakest detail.
To do that, we put together two facts:
Column-times-row multiplication: multiplying a left matrix by a right matrix adds column 1 of the left matrix times row 1 of the right matrix, plus column 2 times row 2, and so on.
Singular Value Decomposition (A=UΣVT): U has perpendicular unit columns ui,Σ has diagonal singular values σ1≥σ2≥⋯≥0 ordered from largest to smallest, and VT has perpendicular unit rows viT.
Pulling Out the Best Layers with the SVD
Multiplying UΣ multiplies each column ui by σi, and multiplying by VT pairs each scaled column with the matching row viT:
Keeping the first k terms in this sum and dropping the rest gives the best Rank k approximation of A:
Ak=σ1u1v1T+σ2u2v2T+⋯+σkukvkT
The subscript k in Ak tells you how many layers are kept, not a row or column entry. Also notice that VT is already transposed in A=UΣVT, so you read each horizontal row viT straight across row i of VT without transposing it again.
3
Worked Example: Rank 1 and Rank 2 Approximations
Let's find the best Rank 1 approximation A1 and Rank 2 approximation A2 of
Multiply σ1, column 1 of U, and row 1 of VT to build A1Pull the 31 out of both vectors first (90×31×31=10) so you only have to multiply whole numbers.
So A1 is the closest Rank 1 matrix to A (with every row a multiple of [102020]), A2 gets closer to A by adding a second layer, and adding the third layer 27u3v3T rebuilds A with zero error.
4
Measuring Error and Energy Kept with Singular Values
To measure how close Ak is to A, we need a way to measure the overall size of a matrix. The Frobenius norm∥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 and the approximation error ∥A−Ak∥F directly from the singular values without squaring millions of entries.
Measuring Error and Energy Kept with Singular Values
Splitting the SVD sum at layer k separates the kept approximation Ak from the leftover error matrix A−Ak:
Each unscaled layer uiviT has squared size 1, 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 k 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+⋯+σk2+σk+12+⋯+σr2σ12+σ22+⋯+σk2
Be careful with the squares: the squared singular values σi2 add up (not the unsquared σi), and ∥A−Ak∥F is the size of the leftover layers, not ∥A∥F−∥Ak∥F.
Let's find the error and energy share for our 3×3 example where σ1=90,σ2=36, and σ3=27.
Text solution
Sum the squared singular values for the total energy of ASquare all three singular values and add them up.
∥A∥F2=902+362+272=8100+1296+729=10,125
Add the discarded squares and take the square root for each errorA1 drops σ2=36 and σ3=27, while A2 drops only σ3=27.
∥A−A1∥F∥A−A2∥F=362+272=2025=45,=272=27
Divide the kept squares by 10,125 for the share keptCheck how much of the total energy 1 layer and 2 layers keep.
Share kept by A1Share kept by A2=10,1258100=80%,=10,1258100+1296=10,1259396≈92.8%
So two layers alone keep 92.8% of the matrix's total energy while leaving an error of 27.
In a photograph, the first few layers have large σi and hold almost all the main picture and squared energy σi2. The remaining layers in A−Ak have tiny σ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 k 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
If you only need a single entry of Ak at row i and column j (such as User i's predicted rating on Movie j), don't multiply out the full matrices. In each layer σmumvmT, the entry at row i and column j only uses entry i of column um and entry j of row vmT:
Every matrix A is a stack of perpendicular column-times-row layers sorted by strength:
A=σ1u1v1T+σ2u2v2T+⋯+σrurvrT
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, [6923]=[23][31], 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 k approximation Ak
Keep the first k layers σ1u1v1T+⋯+σkukvkT, reading each ui from column i of U and each viT from row i of VT. If you only need one entry at row i, column j, don't build the whole matrix: just add σm(um)i(vmT)j across the k 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. For singular values 4,3,0, the total energy is ∥A∥F2=42+32=25 (so ∥A∥F=5), the Rank 1 error is ∥A−A1∥F=32+02=3, and A1 keeps 2542=64% of the energy.
When low-rank storage stops saving space
On an m×n grid, k layers store k(m+n) numbers instead of mn. Once k(m+n)>mn (such as past 250 layers on a 500×500 grid), storing the layers takes more numbers than storing the original grid.
6
Practice
1
Every row of the matrix M=69−3−2−3146−223−1 is a multiple of the base pattern [3−121]. Write M as a single column-times-row layer using that horizontal row, and state the rank of M.
Compare the first entry of each row in M (6,9, and −3) to the first entry 3 of the base pattern: what number multiplies the base row to make each row?
Divide the first entry of each row by 3 to get the vertical row multipliers 2,3, and −1:
M=23−1[3−121]
(Watch out: write the multipliers as a vertical column 23−1, not a horizontal row [23−1], and don't say rank(M)=3 just because M has three nonzero rows.) Because the whole grid is built from a single non-zero layer, rank(M)=1.
What is the rank of B, and how can B be written using the fewest possible layers?
Watch out: don't say rank(B)=3 just by counting the three written layers, and don't add the unscaled first column 12−1+2−13=312 before factoring out the 2.
Compare the three horizontal rows: are any two of them multiples of the same base pattern?
Notice that the first horizontal row [242] is 2 times the third horizontal row [121]. Pull that factor of 2 into the first vertical column so both layers share the exact same horizontal row:
12−1[242]=24−2[121]
(Watch out: don't say rank(B)=3 just by counting the three written layers, and don't add the unscaled first column 12−1+2−13=312 before factoring out the 2.) Now combine the first and third columns:
24−2+2−13[121]=431[121]
The remaining two layers do not have rows or columns that are multiples of each other, so rank(B)=2 and
B=431[121]+301[10−1]
3
A matrix A has the Singular Value Decomposition A=UΣVT with
(Watch out: VT is already transposed, so taking its first column [323132] instead of its first row gives the wrong matrix 10202051010102020.) Next, build Layer 2 with σ2=18, column 2 of U, and row 2 of VT:
(Watch out: don't stop at Layer 2; remember to add Layer 1 and Layer 2 together to get A2.)
A2=A1+σ2u2v2T=1422162162813142
4
A 4×4 matrix A has singular values σ1=20,σ2=12,σ3=9, and σ4=0. Without knowing U or VT, find (a) the Frobenius norm ∥A∥F, (b) the approximation error ∥A−A1∥F, and (c) the approximation error ∥A−A3∥F.
Watch out: don't add the unsquared singular values 20+12+9=41.
Which singular values stay in Ak, and which ones are left in the discarded error A−Ak?
(a) Square and add all singular values, then take the square root:
∥A∥F=202+122+92+02=400+144+81=625=25
(Watch out: don't add the unsquared singular values 20+12+9=41.)
(b) A1 keeps σ1=20 and drops σ2=12,σ3=9, and σ4=0:
∥A−A1∥F=122+92+02=144+81=225=15
(Watch out: don't subtract the unsquared norms ∥A∥F−∥A1∥F=25−20=5; subtract the squared sizes 625−400=225 and then take the square root.)
(c) A3 drops only σ4=0 (three layers rebuild A exactly):
∥A−A3∥F=02=0
5
A 500×500 grid A has five nonzero singular values: σ1=25,σ2=15,σ3=10,σ4=5, and σ5=5. (a) What is the fewest number of layers k needed to keep at least 90% of the total squared size (energy) of A, and what percentage does it keep? (b) How many numbers are needed to store those k layers compared with the original 500×500 grid, and what percentage of the data is saved? (c) On a 500×500 grid, beyond how many layers does storing the layers take more numbers than storing the original grid?
Watch out: if you add the unsquared singular values 25+15+10+5+5=60, three layers give 50/60≈83.3% and trick you into picking k=4 layers.
(a) Compare the running total of σi2 (not σi) to the total sum of squares. (b)–(c) How many numbers are in one vertical column plus one horizontal row of a 500×500 grid?
(a) The total squared size is 252+152+102+52+52=625+225+100+25+25=1,000.
(Watch out: if you add the unsquared singular values 25+15+10+5+5=60, three layers give 6050≈83.3% and trick you into picking k=4 layers.)
Two layers keep 1,000625+225=85%, while three layers keep 1,000625+225+100=1,000950=95%, so k=3 layers (keeping 95%).
(b) One layer stores a column of 500 numbers and a row of 500 numbers, or 500+500=1,000 numbers. (Watch out: don't count only 500 numbers per layer, which would give 1,500 numbers in (b) and 500 layers in (c).) Three layers take 3×1,000=3,000 numbers compared with 500×500=250,000 numbers, saving 250,000250,000−3,000=98.8%.
(c) At 250 layers, 250×1,000=250,000 numbers ties the original grid, so storing the layers takes more numbers beyond 250 layers (k≥251).
6
In a 4×3 user-movie ratings matrix A, the top two SVD layers have singular values σ1=20 and σ2=10, with unit vectors
Using the Rank 2 approximation A2, predict the missing rating for User 2 (row 2) on Movie 1 (column 1) without computing the full matrices.
Watch out: for User 2, be sure to use the second entry of u2, which is −0.5; taking the first entry +0.5 adds +4 instead of −4 and gives 10, and forgetting the weights σ1=20 and σ2=10 gives −0.1.Watch out: for User 2, be sure to use the second entry of u2, which is −0.5; taking the first entry +0.5 adds +4 instead of −4 and gives 10, and forgetting the weights σ1=20 and σ2=10 gives −0.1.
To find just row 2, column 1 of each layer σmumvmT, which single entry of um and which single entry of vmT multiply together?
Multiply each singular value by entry 2 of um and entry 1 of vmT, then add the two layers:
(A2)2,1=20(0.5)(0.6)+10(−0.5)(0.8)=6+(−4)=2
(Watch out: for User 2, be sure to use the second entry of u2, which is −0.5; taking the first entry +0.5 adds +4 instead of −4 and gives 10, and forgetting the weights σ1=20 and σ2=10 gives −0.1.) The predicted rating is 2 stars.