Compressing an image with the SVD
Slide 3 split a matrix into rank-one pieces, loudest first. Now we use that on photos. A grey photo is just a big table of numbers, one per pixel, so it is a matrix. Think of a painter. First she blocks in the big areas, a dark sky and a light field. Then she adds the smaller shapes, and the fine detail comes last. The SVD splits a photo into layers in the same order: the first pieces carry the big shapes and the last ones carry tiny detail. Keep the first few pieces and throw the rest away. The picture still looks right, and you store far fewer numbers. That is image compression.
Lesson 8 · slide 4Image compression- A grey image with m rows and n columns of pixels is an m by n matrix.
- A_k, the first k SVD pieces, is the closest matrix of rank k to A (the Eckart–Young theorem): A − A_k stretches every unit vector by at most σₖ₊₁, and no other rank-k matrix does better.
- Storing A_k needs k(m + n + 1) numbers instead of mn.
- Fast-falling singular values mean the image compresses well.
Pictures are matrices
Give each pixel a number from 0 (white) to 1 (black). A small flag of three stripes, black, grey and white, with 4 pixels in each row, is a 3 by 4 matrix. Each row repeats one number, so the whole flag is a column of stripe values times a row of ones: one rank-one piece.
A 1000 by 1000 photo is a million numbers. Real photos are not one piece, but they are close to a sum of not too many pieces.
Keep k pieces
No matrix of rank k is closer to A than A_k. The error A − A_k is exactly the dropped pieces, so for every unit vector x, ‖(A − A_k)x‖ ≤ σₖ₊₁, the largest σ dropped. Small dropped σ's mean a good copy.
There is also a quick way to see how much each piece holds. Add up the squares of all the pixel values. That total equals σ₁² + σ₂² + σ₃² + …, in two steps:
So σ₁² divided by that total is the share piece 1 carries. The share tells you how much a piece holds; σₖ₊₁ bounds the worst error.
A worked example: a 4 by 4 block
Here is a tiny 4 by 4 corner of a picture: a black top half and a black block at the bottom left.
For a block this small, two pieces cost 2 · (4 + 4 + 1) = 18 numbers, more than the 16 pixels. The saving only shows up for big pictures, where k is tiny compared with m and n.
Keep reading with the full course
Finish lesson 8 and you will be able to: compress an image and keep only what matters.
Still locked here:
- The rest of this explanation
- 4 more examples with step-by-step solutions
- Five extra members-only problems with worked solutions
$20 once, lifetime access. Lessons 1 to 3 stay free.
Examples
Example 1 · A flag with stripes
Three horizontal stripes: each row is one number repeated: a number times the all-ones row.
Rank 1: one piece (a column of stripe values times a row of ones) rebuilds it exactly.
Questions and comments
Stuck on something, or found a mistake? Ask here and I'll answer. You sign in with GitHub.