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

P = Wc: The Matrix Equation Behind Image Compression

IKey Formulas

Formula	Name	Description
$P = Wc$	Change of basis	Signal $P$ as combination of basis columns of $W$ with coefficients $c$
$c = W^{-1} P$	Inverse transform	Recover coefficients from the signal
$W^T W = I \Rightarrow W^{-1} = W^T$	Orthonormal property	Inverse is just the transpose — blazing fast
$\hat{w}_i = w_i / \lVert w_i \rVert$	Normalization	Turns an orthogonal basis into an orthonormal one

IIVisualization 1 — Coordinates Depend on the Basis

The same coefficients $c$ build a different vector $P = Wc$ once the basis $W$ changes.

Basis W c₁ 2 c₂ 1

IIIVisualization 2 — Sparsity Beats Pixels

Keep only the largest few coefficients in each basis, reconstruct, and compare the error.

Keep top-K 3

Standard (pixel) basis

Haar wavelet basis

💡 Packing a signal's energy into a few large coefficients — sparsification — is exactly what JPEG and JPEG 2000 exploit to compress images.

IVVisualization 3 — Orthogonal, but Not Yet Orthonormal

Distinct Haar columns dot to zero — yet a column dotted with itself is its squared length, not $1$ .

Column A 2 Column B 3

💡 Dividing each column by its length normalizes $W$ into an orthonormal matrix, where $W^{-1} = W^{T}$ .

VQuiz Questions

Question 1

Let $W = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ and $c = \begin{pmatrix} 3 \\ 2 \end{pmatrix}$ .

Using $P = Wc$ , what is $P$ ?

✅ Correct! $P = 3w_1 + 2w_2 = (5, 1)$ .

❌ Not quite. Remember: $Wc$ is the linear combination $c_1 w_1 + c_2 w_2$ where $w_i$ are the columns of $W$ .

Show solution

Solution:

Compute $Wc$ column by column: $P = c_1 w_1 + c_2 w_2 = 3 \begin{pmatrix} 1 \\ 1 \end{pmatrix} + 2 \begin{pmatrix} 1 \\ -1 \end{pmatrix} = \begin{pmatrix} 3+2 \\ 3-2 \end{pmatrix} = \begin{pmatrix} 5 \\ 1 \end{pmatrix}.$

Question 2

A matrix $W$ has columns that are mutually orthogonal, but each column has length $\sqrt{2}$ (not 1).

Is it true that $W^{-1} = W^T$ ?

✅ Correct! Orthogonal is not enough — you also need unit length (orthonormal). Here $W^T W = 2I$ , so $W^{-1} = \tfrac{1}{2} W^T$ .

❌ Not quite. Orthogonality gives $W^T W$ diagonal, but only orthonormal columns (unit length) make it the identity.

Show solution

Solution:

Orthogonal columns alone are not enough. If column $i$ has length $\sqrt{2}$ , then $w_i \cdot w_i = 2$ , so $W^T W = 2 I \quad \text{(not the identity).}$

This gives $W^{-1} = \tfrac{1}{2} W^T$ , not $W^T$ itself. You need columns of unit length — i.e., orthonormal — for $W^{-1} = W^T$ . Normalize each column by dividing by its length.

Question 3

Two competing strategies, both keep only 10% of the data:

Strategy A: keep 10% of the raw pixel values (standard basis), set the rest to 0.
Strategy B: keep the 10% largest wavelet coefficients, set the rest to 0, then reconstruct.

Why does Strategy B produce a far better image than Strategy A?

✅ Correct! Sparsification is the key — wavelets pack the signal's energy into a few coefficients.

❌ Not quite. Re-read the answer about energy concentration.

Show solution

Solution:

This is the sparsification criterion. A good basis $W$ should express the signal $P$ as $Wc$ where most entries of $c$ are tiny and only a few are large. Then we keep the big ones and discard the rest — losing almost nothing.

In the standard basis, every coefficient is a pixel. Discarding 90% of pixels literally creates holes in the image.
In the wavelet basis, a few coefficients capture the smooth structure; the small ones encode noise-level details. Throwing them away barely changes the reconstruction.

This is the core idea behind JPEG (DCT) and JPEG 2000 (wavelets).

Question 4

For a megapixel image, $W$ is roughly $10^6 \times 10^6$ . Computing $W^{-1}$ from scratch takes about $n^3 \approx 10^{18}$ operations — infeasible.

Which property of $W$ rescues us by making $c = W^{-1} P$ as cheap as one matrix-vector multiplication?

✅ Correct! Orthonormality turns the inverse into a transpose — and a transpose is essentially free.

❌ Not quite. Think about which property makes $W^T W = I$ , so that $W^{-1} = W^T$ .

Show solution

Solution:

When $W$ is orthonormal, $W^T W = I$ , so $W^{-1} = W^T$ . Transposing a matrix is essentially free — you just reinterpret the indices. So $c = W^{-1} P$ becomes $c = W^T P$ , a single matrix-vector multiplication.

This is exactly why the FFT, DCT, and wavelet transforms all use orthonormal bases: speed.

(Note: $W$ being diagonal would also be fast, but then it wouldn't mix coordinates at all — useless for compression. Square and integer-valued don't help with inversion cost.)

Solved: 0 / 4