(no subject)

[impossiblewizardry]

One thing you can do to compress an image is do a wavelet transform, delete low coefficients, and transform back.

Suppose you’re using an orthogonal wavelet basis, and let’s call the matrix of the transformation W. I’ll denote the transpose by W’.

You have an image which is represented as a vector x. What is the squared error if we reconstruct an image from wavelet coefficients v?

||W’ v - x||²

||W’ v - W’ W x||²

(W’ v - W’ W x)’ (W’ v - W’ W x)

(v - W x)’ W W’ (v - W x)

||v - W x||²

So, whatever error you introduce to the wavelet coefficients by deleting small ones, that’s how much error you introduce to the image itself which is reconstructed from those coefficients. And that’s why, if you must delete a certain number of coefficients, it is best to delete the smallest ones.

I don’t think people really do compression like this, because of course you don’t have to be so binary about whether you keep a coefficient. You instead decdie how many bits you want to use to store a coefficient. JPEG uses a cosine transform rather than a wavelet transform, and uses fewer bits to store higher frequency coefficients. JPEG2000, which is based on wavelets, maybe it does something similar.

BUT if we imagine that we’re doing it like this, we’re deleting small coefficients and keeping the rest as is, basically what we’re doing is we’re projecting the image on a subset of the wavelet basis. And what I showed above implies that, to minimize the squared reconstruction error, the optimal subset of size k are the k vectors with the highest coefficients.

This framing seems analogous to principle components analysis. But in principle components analysis, I would start with a large set of images. And I would decide to use the same basis of size k for each of them (instead of, for each image, using whichever k basis vectors had the highest coefficients in that specific image). And then, instead of picking these vectors from a predefined basis like a wavelet basis, I would just find the optimum k vectors, out of all possible vectors, to minimize the summed reconstruction error across all images.