the discrete cosine transform
Every time you view a JPEG photo, stream a video, or hear an MP3, a discrete cosine transform did the heavy lifting. It is a close cousin of the DFT that uses only real cosine waves instead of complex exponentials, and it has one magical property for compression: for the smooth, slowly-varying data typical of natural images and audio, it packs almost all the important information into just a few low-frequency coefficients, leaving the rest near zero and safe to discard.
The DCT expresses a block of samples as a sum of cosine waves of increasing frequency. The common form (DCT-II) of a length-N signal x is C_k = sum over n from 0 to N-1 of x_n * cos(pi * k * (n + 0.5) / N), giving N real coefficients: C_0 is proportional to the average, and higher C_k capture progressively finer wiggles. The reason it beats the DFT for compression is subtle but important. The DFT assumes your block repeats periodically, which usually creates a jump at the seam (leakage) and spreads energy across many bins. The DCT instead implicitly reflects the block at its edges before repeating, so the extended signal is continuous — no artificial jump — and the energy concentrates in the lowest few coefficients. This 'energy compaction' is exactly what makes compression work, and like the FFT the DCT has an O(N log N) fast algorithm.
In JPEG, an image is broken into 8x8 pixel blocks, each block is run through a 2D DCT, the resulting 64 coefficients are quantized (the high-frequency ones coarsely, since the eye barely notices them), and the near-zero coefficients are thrown away and the rest compressed. Decompression reverses the steps with an inverse DCT. This is LOSSY: information is genuinely discarded, which is honest to acknowledge — push the quantization too hard and you see the tell-tale 8x8 blocky artifacts of an over-compressed JPEG. The DCT's relatives, the discrete sine transform and various boundary variants, play the same role in spectral PDE solvers with different boundary conditions.
Take an 8-pixel row that fades smoothly from dark to light. Its DCT puts nearly all the energy in C_0 (the average) and C_1 (the single slow ramp), with C_2 through C_7 essentially zero. Keep just the first two coefficients, set the rest to zero, and the inverse DCT reproduces the row almost perfectly — six numbers stored as two.
Smooth data compacts into a few low-frequency cosines — the heart of JPEG.
JPEG and MP3 are LOSSY: the DCT itself is reversible, but the quantization step that follows it deliberately discards information and cannot be undone. Over-aggressive quantization produces the familiar 8x8 block artifacts.