Change of Basis; Image Compression

An image is a vector

Coming near the end of the course, this lecture mixes the linear algebra of changing basis with an application you meet every day: compression. Compressing a signal, compressing an image — “that’s exactly change-of-basis.” Strang’s own example is the video of this very lecture: the full signal sits on the videotape, but what goes out on the web is compressed, which is why his motion looks jerky while the writing on the board comes through clearly — his motion “needs a whole lot of bits.”

Take a still image, black and white, $512 \times 512$ pixels — $2^9$ by $2^9$. Each pixel carries a grayscale value from $0$ to $255$, so eight bits per pixel ($2^8$ possibilities). The image is then a vector

$$\mathbf{x} \in \mathbb{R}^n, \qquad n = 512^2,$$

one component per pixel. A color image needs three times that. This is an enormous amount of information — the lectures could not be sent out without compressing it. Some compression is lossless, exploiting redundancies exactly; this lecture is about lossy compression, where information is deliberately thrown away.

Why the standard basis is lousy

As it arrives, the image is written in the standard basis: the vectors $(1, 0, \dots, 0)$, $(0, 1, 0, \dots, 0)$, and so on — every pixel gets its own value, maybe $121$ here and $124$ next door. But neighboring pixels are highly correlated: lots of nearly identical values for the blue shirt, a whole lot more for the blackboard. The extreme case is a blank blackboard before lecture — every gray level practically the same — and it would make no sense to report that image pixel by pixel. The standard basis makes no use of the fact that neighbors tend to agree.

So choose a better basis. One vector that would be extremely nice to have is the vector of all ones: that single vector completely carries a solid image. At the other extreme, the checkerboard vector $(1, -1, 1, -1, \dots)$ would carry the whole signal if the image alternated pixel by pixel — but a smooth image contains very little of that highest frequency. In between, a vector of half ones and half minus ones captures an image that is darker on one half and lighter on the other.

We are free to choose the basis, and “it’s a billion-dollar decision what we choose.” TV people prefer one basis based on how the signal is scanned, movie people prefer another — giant politics that reduces to a linear algebra problem. The best-known choice, the one JPEG uses, is the Fourier basis: the constant vector of all ones (the DC vector, to electrical engineers) together with the columns of the Fourier matrix, powers of a complex number $w$, from the FFT lecture. JPEG doesn’t transform the whole $512 \times 512$ image at once — that’s too much. It breaks the image into $8 \times 8$ blocks, $64$ pixels each, and changes basis in $\mathbb{R}^{64}$ block by block.

The compression pipeline: lossless, then lossy

Here is the whole scheme, and it’s important to see which step loses information.

$$\mathbf{x} \;\xrightarrow{\ \text{change basis (lossless)}\ }\; \mathbf{c} \;\xrightarrow{\ \text{threshold (lossy)}\ }\; \hat{\mathbf{c}} \;\xrightarrow{\ \text{reconstruct}\ }\; \hat{\mathbf{x}}$$

Sixty-four pixels come in; sixty-four coefficients come out. The change of basis is lossless — $\mathbb{R}^{64}$ has plenty of bases and we’ve simply chosen one and rewritten the signal in it. Then comes the compression step, and that’s lossy: thresholding. Set a threshold and throw away every coefficient below it — every basis vector present in an amount the eye can’t see, or can hardly see. The coefficient of the all-ones vector is usually large and is very seldom thrown away; the coefficient of the fast-alternating checkerboard vector is probably tiny in any smooth signal (that’s noise, and “very little noise in this lecture”). The result is a compressed set of coefficients $\hat{\mathbf{c}}$ with many zeros. Reconstruct by summing coefficients times basis vectors — but the sum no longer has $64$ terms; maybe two or three. From $64$ down to $3$ is compression of about $21$ to $1$, and “that’s the kind of compression you’re looking for.”

Strang’s favorite still-image story is the FBI. Fingerprints used to go to Washington as inky marks in filing cabinets — thirty million of them, with no way to retrieve one in under a week. Digitizing helped, but a raw fingerprint is still too many pixels to search. So the FBI had to choose a basis for compressing fingerprints, built a facility in West Virginia, and now a match takes minutes.

Video adds one more idea. You could compress each frame as a still image, but successive frames are extremely correlated. So use prediction and correction: assume the next frame equals the current one, then code and compress only the small correction. The whole game of compression, in time or in space, is exploiting the fact that things change smoothly, so each value can be predicted from the previous one.

The wavelet basis

The competition for Fourier is called wavelets. In the $8 \times 8$ case (Strang drops to one dimension — eight pixel values along a row), the simple wavelet basis for $\mathbb{R}^8$ is:

$$\begin{bmatrix} 1\\1\\1\\1\\1\\1\\1\\1 \end{bmatrix},\; \begin{bmatrix} 1\\1\\1\\1\\-1\\-1\\-1\\-1 \end{bmatrix},\; \begin{bmatrix} 1\\1\\-1\\-1\\0\\0\\0\\0 \end{bmatrix},\; \begin{bmatrix} 0\\0\\0\\0\\1\\1\\-1\\-1 \end{bmatrix},\; \begin{bmatrix} 1\\-1\\0\\0\\0\\0\\0\\0 \end{bmatrix},$$

plus three more like the last one, with the $1, -1$ pair sliding along: in positions $3,4$, positions $5,6$, and positions $7,8$. Coarse scales first, fine details last. And every vector in $\mathbb{R}^8$ is some combination of these — for instance, the fast checkerboard $(1,-1,1,-1,1,-1,1,-1)$ is exactly the sum of the last four wavelets.

Now the linear algebra step: given the pixel values $\mathbf{p} = (p_1, \dots, p_8)$ in the standard basis, find the coefficients $c_1, \dots, c_8$ with $\mathbf{p} = c_1 \mathbf{w}_1 + \cdots + c_8 \mathbf{w}_8$. But a combination of vectors is a matrix times a vector — “the step we’re constantly taking in this course”: put the basis vectors into the columns of a matrix $W$. Then

$$\mathbf{p} = W\mathbf{c} \qquad\Longrightarrow\qquad \mathbf{c} = W^{-1}\mathbf{p}.$$

That formula exposes the critical point: a good basis has a nice, fast inverse. Two requirements make a basis good:

1. Fast. You must be able to multiply by $W$ and by $W^{-1}$ quickly, or the transform costs more time than you can afford. Fourier passes because of the FFT; there is a fast wavelet transform too. The wavelet vectors are all ones, minus ones, and zeros — fast in binary. Better still, check the dot products: four $+1$s against four $-1$s gives zero; two against two gives zero. The basis is orthogonal. Divide by the lengths ($\sqrt 8$, $\sqrt 4$, $\sqrt 2$, …) to make it orthonormal, and then — Section 4.4 — $W^{-1} = W^T$. The inverse is as fast as the forward transform.
2. Good compression. The fastest thing of all is not to change basis — but the standard basis is poor for compression: throw away $90\%$ of the pixel values and the picture just goes dark. A good basis needs a few basis vectors to come close to the signal, so that discarding $c_5, c_6, c_7, c_8$ loses only little blips.

JPEG 2000, the next compression standard, includes wavelets — though the FBI uses a smoother wavelet, without the jump from $1$ to $-1$.

The matrix of a transformation — and what changing basis does to it

Now the math half of the lecture: the connection between a linear transformation $T$, which needs no coordinates, and the matrix that describes it once coordinates are chosen. The matrix is the coordinate-based description of the transformation.

Suppose $T$ maps eight-dimensional space to eight-dimensional space — a rotation, say, or a projection. With respect to one basis $\mathbf{v}_1, \dots, \mathbf{v}_8$ it has a matrix $A$; with respect to a second basis $\mathbf{w}_1, \dots, \mathbf{w}_8$ it has a matrix $B$. What’s the connection?

Strang admits this part of the lecture is, fittingly, “compressed” — the conclusion is what he wants you to spot: change the basis, and two things happen. Every vector gets new coordinates, by the rule $\mathbf{x} = W\mathbf{c}$. Every transformation gets a new matrix, related to the old one by similarity, with $M = W$.

How do you build the matrix $A$ in the first place? Recall from the last lecture: if you know what $T$ does to the eight basis vectors, you know $T$ completely. Why? Because every input is a combination $\mathbf{x} = c_1\mathbf{v}_1 + \cdots + c_8\mathbf{v}_8$ — that’s the whole point of a basis, every vector is a combination of the basis vectors in exactly one way — and linearity forces

$$T(\mathbf{x}) = c_1\,T(\mathbf{v}_1) + c_2\,T(\mathbf{v}_2) + \cdots + c_8\,T(\mathbf{v}_8).$$

So the recipe builds $A$ column by column: apply $T$ to the first basis vector, expand the output in the basis,

$$T(\mathbf{v}_1) = a_{11}\mathbf{v}_1 + a_{21}\mathbf{v}_2 + \cdots + a_{81}\mathbf{v}_8,$$

and those numbers $a_{11}, \dots, a_{81}$ are the first column. Do the same with $T(\mathbf{v}_2)$ for the second column, and so on: sixty-four numbers, and the matrix represents $T$ in that basis.

The perfect basis: eigenvectors

Close with the best example of all. Suppose the basis $\mathbf{v}_1, \dots, \mathbf{v}_8$ consists of eigenvectors of $T$, so $T(\mathbf{v}_i) = \lambda_i \mathbf{v}_i$. What is $A$? Run the recipe, one minute flat. First input $\mathbf{v}_1$, output $\lambda_1 \mathbf{v}_1$ — and expanding that in the basis is already done: $\lambda_1$ times the first basis vector, zero times the others. So the first column is $\lambda_1$ and zeros. Second column: $\lambda_2$ in the second slot, zeros elsewhere. In the eigenvector basis,

$$A = \begin{bmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_8 \end{bmatrix}.$$

The matrix is diagonal.

Problems

Work these before revealing the solutions. Everything you need is in the lecture.

Problem 31.1 Wavelet coefficients

Take the wavelet basis for $\mathbb{R}^4$:

$$\mathbf{w}_1 = \begin{bmatrix} 1\\1\\1\\1 \end{bmatrix},\quad \mathbf{w}_2 = \begin{bmatrix} 1\\1\\-1\\-1 \end{bmatrix},\quad \mathbf{w}_3 = \begin{bmatrix} 1\\-1\\0\\0 \end{bmatrix},\quad \mathbf{w}_4 = \begin{bmatrix} 0\\0\\1\\-1 \end{bmatrix}.$$

Write the pixel vector $\mathbf{p} = (6, 4, 5, 1)$ as a combination $c_1\mathbf{w}_1 + c_2\mathbf{w}_2 + c_3\mathbf{w}_3 + c_4\mathbf{w}_4$. (Hint: this basis is orthogonal — use that instead of elimination.)

Show solution

Because the basis is orthogonal, dot both sides with each $\mathbf{w}_i$: all cross terms vanish, so $c_i = \dfrac{\mathbf{w}_i \cdot \mathbf{p}}{\mathbf{w}_i \cdot \mathbf{w}_i}$.

$$c_1 = \frac{6+4+5+1}{4} = 4, \qquad c_2 = \frac{6+4-5-1}{4} = 1, \qquad c_3 = \frac{6-4}{2} = 1, \qquad c_4 = \frac{5-1}{2} = 2.$$

Check: $4(1,1,1,1) + 1(1,1,-1,-1) + 1(1,-1,0,0) + 2(0,0,1,-1) = (6, 4, 5, 1)$. ✓ The big coefficient $c_1 = 4$ is the average brightness — the one you’d never threshold away.

Problem 31.2 Fast inverse from orthogonality

For the basis of Problem 31.1, verify that all four vectors are mutually orthogonal. Then rescale them to unit length, put them into the columns of a matrix $W$, and write down $W^{-1}$ without doing elimination.

Show solution

Check the six dot products: $\mathbf{w}_1 \cdot \mathbf{w}_2 = 1+1-1-1 = 0$; $\mathbf{w}_1 \cdot \mathbf{w}_3 = 1-1 = 0$; $\mathbf{w}_1 \cdot \mathbf{w}_4 = 1-1 = 0$; $\mathbf{w}_2 \cdot \mathbf{w}_3 = 1-1 = 0$; $\mathbf{w}_2 \cdot \mathbf{w}_4 = -1+1 = 0$; $\mathbf{w}_3 \cdot \mathbf{w}_4 = 0$. All orthogonal.

The lengths are $\|\mathbf{w}_1\| = \|\mathbf{w}_2\| = 2$ and $\|\mathbf{w}_3\| = \|\mathbf{w}_4\| = \sqrt{2}$. Dividing each column by its length gives

$$W = \begin{bmatrix} \tfrac12 & \tfrac12 & \tfrac{1}{\sqrt2} & 0 \\ \tfrac12 & \tfrac12 & -\tfrac{1}{\sqrt2} & 0 \\ \tfrac12 & -\tfrac12 & 0 & \tfrac{1}{\sqrt2} \\ \tfrac12 & -\tfrac12 & 0 & -\tfrac{1}{\sqrt2} \end{bmatrix},$$

an orthogonal matrix: orthonormal columns. Therefore $W^{-1} = W^T$ — just flip it across the diagonal. That is exactly the “good basis has a nice, fast inverse” property: the inverse transform costs the same as the forward one.

Problem 31.3 Matrix of T, column by column

Let $T$ be the projection of $\mathbb{R}^2$ onto the line through $(1, 1)$. Using the basis $\mathbf{v}_1 = (1, 1)$, $\mathbf{v}_2 = (1, -1)$, follow the lecture’s recipe to find the matrix $A$ of $T$ in this basis. Why did this basis make the answer so clean?

Show solution

First column: input $\mathbf{v}_1 = (1,1)$ lies on the line, so projection leaves it alone: $T(\mathbf{v}_1) = \mathbf{v}_1 = 1\cdot\mathbf{v}_1 + 0\cdot\mathbf{v}_2$. First column: $(1, 0)$.

Second column: input $\mathbf{v}_2 = (1,-1)$ is perpendicular to the line, so it projects to zero: $T(\mathbf{v}_2) = \mathbf{0} = 0\cdot\mathbf{v}_1 + 0\cdot\mathbf{v}_2$. Second column: $(0, 0)$.

$$A = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}$$

The answer is diagonal because $\mathbf{v}_1$ and $\mathbf{v}_2$ are eigenvectors of the projection, with eigenvalues $\lambda_1 = 1$ and $\lambda_2 = 0$. This is the lecture’s closing point in miniature: in the eigenvector basis, the matrix of the transformation is diagonal.

Problem 31.4 Same T, two bases, similar matrices

The projection of Problem 31.3 has matrix $B = \frac12\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$ in the standard basis. Verify the lecture’s claim that $A$ and $B$ are similar: with $M = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$ (the eigenvector basis in its columns), check that $B = M A M^{-1}$.

Show solution

First $M^{-1}$: since $\det M = -2$,

$$M^{-1} = \frac{1}{-2}\begin{bmatrix} -1 & -1 \\ -1 & 1 \end{bmatrix} = \frac12\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}.$$

Now multiply:

$$M A = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix}, \qquad M A M^{-1} = \begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix} \cdot \frac12\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = \frac12\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} = B. \checkmark$$

Same transformation, two bases, two matrices — and the change-of-basis matrix $M$ is exactly the similarity: $B = MAM^{-1}$, equivalently $A = M^{-1}BM$. Note the shared fingerprints of similarity: both matrices have eigenvalues $1$ and $0$, and both have trace $1$.

Problem 31.5 Compression arithmetic

A grayscale image has $512 \times 512$ pixels at $8$ bits each. (a) How many bits is the raw image? (b) JPEG-style compression splits it into $8 \times 8$ blocks and, after the change of basis, keeps on average $4$ of the $64$ coefficients per block. What is the compression ratio? (c) Why can’t you get the same effect by simply keeping $4$ of every $64$ pixel values in the standard basis?

Show solution

(a) $512^2 \times 8 = 262{,}144 \times 8 = 2{,}097{,}152$ bits — about two million bits for one modest black-and-white image.

(b) Each block goes from $64$ coefficients to $4$, so the ratio is $64/4 = 16{:}1$ (roughly — the surviving coefficients still cost bits to encode, but the count of numbers drops sixteenfold). The number of blocks is $(512/8)^2 = 64^2 = 4096$, but the ratio is the same for every block.

(c) In the standard basis, each kept number describes one pixel and says nothing about the others: keep $4$ pixels of every $64$ and the other $60$ are simply gone — the picture “goes dark,” as the lecture says of throwing away $90\%$ of pixel values. In a good basis, the first few coefficients describe the whole block at once (its average, its coarse light–dark structure), so the discarded coefficients were only carrying small, high-frequency blips the eye barely sees.