LINEAR-ALGEBRA · Interactive Practice | Unit 30 · Video 2

Why Your Photos Are 95% Lies: The Linear Algebra Behind JPEG

IKey Ideas Reference

Concept	Expression	Meaning
Change of basis	$\mathbf{x} = c_1 \mathbf{b}_1 + c_2 \mathbf{b}_2 + \cdots + c_n \mathbf{b}_n$	Rewrite the same vector in a new vocabulary
Coefficient	$c_k = \mathbf{b}_k \cdot \mathbf{x}$ (orthonormal case)	How much of pattern $\mathbf{b}_k$ appears in $\mathbf{x}$
Thresholding	Keep $c_k$ if $\lvert c_k \rvert \geq \tau$ , else set to $0$	The lossy step — information disappears here
Compression ratio	$\dfrac{\text{numbers stored originally}}{\text{coefficients kept}}$	e.g. $64/3 \approx 21{:}1$

IIVisualization 1 — A Basis Localized in Space

Each Haar basis vector watches a different slice of the signal — some the whole thing, some just two neighboring pixels.

Basis vector

💡 Unlike a Fourier sine wave, which stretches across the whole signal, most Haar vectors are zero almost everywhere — that locality is what lets one coefficient pin down an edge.

IIIVisualization 2 — Throwing Coefficients Away

A smooth signal hides in a few large coefficients — keep those, zero the rest, and barely notice.

Coefficients kept (k) 5

💡 Natural image blocks are smooth, so their energy piles into a few low-frequency coefficients — that sparsity, not the basis by itself, is what makes JPEG work.

IVVisualization 3 — Fourier vs. Wavelets

Smooth signals are sparse in Fourier; sharp edges are sparse in wavelets — sparsity depends on the basis.

💡 This is why JPEG 2000 and the FBI's fingerprint format (WSQ) use wavelets: a fingerprint is all edges, and edges are sparse in Haar, not Fourier.

VQuiz Questions

Question 1

In the JPEG pipeline, an 8×8 pixel block (64 numbers) is rewritten using the Fourier basis to get 64 coefficients $c_1, c_2, \ldots, c_{64}$ .

At this step — before any thresholding — has any information been lost?

✅ Correct! Change of basis just renames the same vector in a new vocabulary.

❌ Not quite. Don't confuse the change of basis step with the thresholding step. Only thresholding loses information.

Show solution

Solution:

A change of basis just rewrites the same vector using different "vocabulary" — it does not throw anything away. If $\mathbf{x}$ is the original pixel vector and $\mathbf{c}$ is the Fourier-coefficient vector, then we can always recover

$\mathbf{x} = c_1 \mathbf{b}_1 + c_2 \mathbf{b}_2 + \cdots + c_{64} \mathbf{b}_{64}.$

The lossy step in JPEG is thresholding (Act 2), where small coefficients are set to zero. The change-of-basis step itself (Act 1) is perfectly reversible.

Question 2

Suppose an 8×8 block (64 numbers) is compressed by keeping only 4 of its 64 Fourier coefficients. What is the compression ratio?

✅ Correct! $64 / 4 = 16$ , so the compression ratio is 16:1.

❌ Not quite. Compression ratio = (original numbers) / (stored numbers).

Show solution

Solution:

Compression ratio compares the original number of values to the stored number of values:

$\text{ratio} = \frac{\text{original}}{\text{kept}} = \frac{64}{4} = 16.$

So we get 16:1 compression. The reconstruction still produces all 64 pixel values, but we only had to store 4 numbers to get there.

❌ 4:1 — that's just the number of coefficients kept, not the ratio.
❌ 60:1 — that's the number discarded, not the ratio.
❌ 64:1 — that would require keeping only 1 coefficient.

Question 3

You need to compress an image containing sharp fingerprint ridges (lots of edges and fine-scale local features). The FBI famously chose a wavelet-based standard for this task rather than JPEG's Fourier-based one.

Why are wavelets a better fit than Fourier here?

✅ Correct! Localization in space is the wavelet's superpower for edges.

❌ Not quite. The key word is localization — wavelets know where features are, not just how wavy they are.

Show solution

Solution:

Fourier basis vectors stretch across the entire interval. A sharp edge — a single sudden jump — cannot be captured by any one Fourier vector, so the edge "spreads out" across many high-frequency coefficients. That kills sparsity, and sparsity is what makes compression work.

Haar wavelets, by contrast, are localized in both space and frequency. A jump at position 4 mostly lights up the wavelet that sits at position 4 — a few coefficients, not many.

This is exactly why the FBI's fingerprint compression standard (WSQ) shrinks each fingerprint by roughly 15:1 while preserving identifying ridge detail, and why JPEG 2000 also uses wavelets.

❌ "Store more information per coefficient" — coefficients are just real numbers in either basis.
❌ "Wavelets are lossless" — wavelet compression still thresholds, which is lossy.
❌ "Fourier coefficients don't exist" — they exist, there are just too many significant ones for an edge.

Question 4

True or False: The Fourier basis and the Haar wavelet basis in $\mathbb{R}^8$ span different subspaces of $\mathbb{R}^8$ — that is, there are vectors expressible in one basis that cannot be expressed in the other.

✅ Correct! Both are bases of the same space $\mathbb{R}^8$ — they just describe vectors using different vocabularies.

❌ Not quite. Recall the video: the Fourier checkerboard equals a sum of four Haar wavelets. Every vector in $\mathbb{R}^8$ can be expressed in either basis.

Show solution

Solution:

False. Any basis of $\mathbb{R}^8$ spans all of $\mathbb{R}^8$ — that's literally what "basis" means. The Fourier basis and the Haar wavelet basis describe the same space, just in different vocabularies.

The video made this explicit by writing the Fourier checkerboard vector as a sum of four Haar wavelets:

$(1, -1, 1, -1, 1, -1, 1, -1) = (1, -1, 0, 0, 0, 0, 0, 0) + (0, 0, 1, -1, 0, 0, 0, 0) + (0, 0, 0, 0, 1, -1, 0, 0) + (0, 0, 0, 0, 0, 0, 1, -1).$

Every vector expressible in one basis is expressible in the other. What differs is which vectors are sparse (have few nonzero coefficients):

Smooth signals are sparse in Fourier.
Sharp / localized signals are sparse in Haar.

Same space, different strengths.

Solved: 0 / 4