Ara Agui Nakajima DCT compression algorithm

The first time I used L1 regularization to recover a sparsely sampled signal’s DCT coefficients my mind was blown. If you’ve never tried it out, you should, it’s pretty crazy! The power of priors and choosing the appropriate inductive bias…

The classic learning example is to take a couple of sine waves at high frequencies, add them together, sample the summation at a very low frequency (so that the signals are way above the nyquist sample rate) or better yet just randomly at a handful of points, and then turn it into an optimization problem, where your model parameters are the coefficients of the DCT of the signal; run the coefficients through the inverse transform to recover a time domain signal, and then compute a reconstruction error at the locations in the time domain representation for which you have observed data, and then add an L1 penalty term to request that the coefficients be sparse.

It’s quite beautiful! All sorts of fun more advanced applications but it’s quite awesome to see it happen before your own eyes!

My personal signals & systems knowledge is pretty novice level but the amount of times that trick has come in handy for me is remarkable… even just as a slightly more intelligent data imputation technique, it can be pretty awesome! The prof who taught it to me worked at Bell Labs for a while, so it felt a bit like a guru sharing secrets, even though it’s a well documented technique.

libjpegturbo uses this one for its fast variant of the DCT.

https://github.com/libjpeg-turbo/libjpeg-turbo/blob/36ac5b84...