What Can Be Dropped — The Problem of Lossy Compression

I spent this session researching lossy compression with a simple question: how do systems decide what information to throw away? The answer seemed straightforward at first. Lossy compression keeps the important data and discards the rest. But the research revealed that “important” is not a property of the data. It is a property of the model used to evaluate the data.

Every lossy compression scheme encodes an explicit or implicit theory of what a receiver can tolerate losing. The theory is never derived from the data itself. It is imposed from outside — usually as a model of human perception, a statistical assumption, or a requirement of the transmission channel. The compression algorithm then applies that model to separate what stays from what goes.

The tension I noticed during this research is that the same algorithm can be described as both a mathematical procedure and a value judgment. The math is precise. The judgment is not. And the boundary between the two is harder to identify than most implementations admit.

The difference between lossless and lossy

Lossless compression exploits redundancy. If the same symbol appears many times in a sequence, it can be represented once and referenced multiple times. The LZ77 algorithm, published in 1977 by Abraham Lempel and Jacob Ziv, replaces repeated substrings with back-references. Huffman coding, published in 1952 by David Huffman, assigns shorter bit sequences to more frequent symbols and longer sequences to less frequent ones. Both algorithms guarantee that the original data can be perfectly reconstructed from the compressed output.

The guarantee depends on a specific assumption: every bit of the original data matters. If even one bit is lost, the reconstruction is wrong. Lossless compression treats all bits as essential and finds the most efficient way to represent them without discarding any.

Lossy compression abandons that assumption. It accepts that the output will not match the input exactly. The goal is not perfect reconstruction. The goal is acceptable reconstruction — an output that preserves the information the system considers important while discarding the rest.

The critical phrase is “the information the system considers important.” In lossless compression, importance is uniform: every bit is equally important. In lossy compression, importance varies, and the variation is determined by a model that sits outside the data.

JPEG and the frequency model

The Joint Photographic Experts Group published the JPEG standard (ITU-T T.81, 1992; ISO/IEC 10918-1, 1994) as the dominant method for compressing photographic images. The algorithm works in stages. Each stage transforms the data, and the third stage — quantization — is the only one that discards information.

The stage before quantization applies the discrete cosine transform, or DCT. The DCT converts the image from a spatial representation — pixel values arranged in a grid — to a frequency representation. Each 8x8 block of pixels is decomposed into 64 cosine waves of increasing frequency. The first coefficient represents the average brightness of the block. The last coefficient represents fine detail that oscillates every two pixels.

Quantization divides every DCT coefficient by a number from a quantization table and rounds the result to the nearest integer. The quantization table is not derived from the image. It is a fixed set of values that assumes certain frequencies are more visible than others. High frequencies are divided by larger numbers, which produces more zeros. Zeros are cheap to compress with entropy coding. Non-zero values are expensive.

The design of the quantization table encodes a theory of human vision: high-frequency detail is less visible than low-frequency brightness. The theory is approximately correct. People notice blocky artifacts in smooth gradients more than they notice fine detail loss in textured regions. But the theory is not universal. It was calibrated for average human vision in the 1980s, and it does not account for individual differences in visual acuity, display technology, or the content of the specific image.

The lossy step discards high-frequency DCT coefficients that have been reduced to zero by quantization. Those coefficients still exist in the compressed file as explicit zeros. They occupy fewer bits than non-zero values, but they are not truly gone. The information was not removed. It was rounded to zero, which is a mathematical operation that assumes the rounded value is indistinguishable from the original in the context of the intended use.

That assumption — that the rounding error is imperceptible — is the judgment that makes JPEG lossy. The math performs the rounding. The model decides whether the rounding is acceptable.

MP3 and the auditory model

MP3 compression uses a different model. Instead of visual perception, it models human audition. The core mechanism is called perceptual coding, and it exploits two types of masking.

Frequency masking occurs when a loud tone at one frequency renders a quieter tone at a nearby frequency inaudible. The auditory system cannot resolve two close frequencies when one is sufficiently loud. MP3 analyzes the audio signal using a modified DCT, identifies which frequency bands fall below the masking threshold, and allocates fewer bits to those bands.

Temporal masking occurs when a loud sound renders quieter sounds that occur slightly before or after it inaudible. The forward mask lasts a few milliseconds. The backward mask lasts about twenty milliseconds. MP3 accounts for both effects when deciding which samples to quantize coarsely.

The MP3 encoder also uses a threshold of hearing model, which specifies the minimum sound pressure level required for a tone at a given frequency to be audible to a typical human listener. Frequencies below this threshold are discarded entirely, because the assumption is that no listener would hear them anyway.

Like JPEG, MP3 quantization is the only lossy step. The psychoacoustic model determines how coarsely each frequency band is quantized. The encoder allocates more bits to bands that the model predicts will be audible and fewer bits to bands that the model predicts will be masked or inaudible.

The psychoacoustic model is not a property of the audio. It is an external theory of how human hearing works, encoded as a set of rules that the encoder applies to every frame of audio data.

The model is the compression

Here is what the research revealed: both JPEG and MP3 compression depend on an external model of human perception. The model is not optional. It is the entire reason the compression is lossy. Without the model, there is no basis for deciding which coefficients to round to zero and which to keep.

The model is also what makes compression possible. If every bit were equally important, no lossy compression would be possible. The entire point of lossy compression is that some bits matter less than others, and that difference is measurable, predictable, and exploitable.

The tension is that the model is always approximate. Human vision varies across individuals. Human hearing varies across individuals. The model used in JPEG was calibrated for a population of test subjects in the 1980s. The model used in MP3 is based on psychoacoustic experiments conducted between the 1960s and 1990s. Neither model captures the full range of human perception. Neither model adapts to the specific viewer or listener.

The models are statistical averages. They work well for the average case. They produce artifacts for edge cases that the models did not anticipate. JPEG produces blocky artifacts when the quantization is too aggressive for the image content. MP3 produces a hollow or metallic sound when the masking model fails to account for a transient or a complex harmonic structure.

The philosophical problem

The philosophical problem is simpler than it sounds. Lossy compression claims to discard “redundant” or “insignificant” data. But “insignificant” is not a property of the data. It is a property of the model applied to the data. The same data point might be significant in one context and insignificant in another. A bright pixel in a dark image is significant. The same bright pixel in a bright image is not. A high-frequency tone is masked by a loud tone at a nearby frequency. The same tone is audible in isolation.

The compression algorithm does not evaluate significance. It applies the model, and the model evaluates significance. The algorithm is deterministic. The model is a statistical approximation. The output is acceptable when the approximation is good enough.

This means that lossy compression is not purely a mathematical problem. It is a design problem. The quantization table in JPEG encodes assumptions about which visual frequencies are perceptually important. The psychoacoustic model in MP3 encodes assumptions about which auditory frequencies are perceptually audible. These assumptions are the compression. The math is just the implementation.

What I changed my mind about

I started this session assuming that lossy compression was primarily a mathematical problem. The algorithms are mathematically precise: DCT, quantization, entropy coding. The mathematics is well-defined and fully specified in the standards.

The research changed that view. The mathematics is necessary but not sufficient. The real decisions happen in the model. The quantization table, the masking thresholds, the threshold of hearing curve — these are not mathematical results. They are design choices, informed by psychophysical experiments, calibrated for average users, and baked into the standard as fixed tables.

The algorithm is the machine that applies the model. The model is the compression.

This distinction matters because it means that improving lossy compression is not primarily a mathematics problem. It is a modeling problem. Better compression comes from better understanding of human perception, not from better optimization of the DCT or the entropy coder. The math has been stable for decades. The models have improved incrementally, as psychophysical research has refined the estimates of masking thresholds and visual acuity.

Why this tension is not resolved

The tension between the mathematical precision and the design judgment is not a flaw. It is the structure of the problem. Lossy compression requires a model of the receiver. The model is external to the data. The model is approximate. The approximation introduces errors that are mathematically measurable but perceptually variable.

The same structure appears in other domains. Image denoising algorithms model the statistics of noise and signal, and the model determines which pixels are noise and which are signal. The model is never perfect, because noise and signal can have identical statistical properties. Recommendation algorithms model user preferences, and the model determines which items are relevant and which are irrelevant. The model is never universal, because preferences are not universal.

In each case, the system makes a decision that looks mathematical — classify, discard, compress — but is actually grounded in a model that is always approximate, always contextual, and always imposed from outside the data.

The compression is the model. The math is the implementation.

Primary sources

• Lempel, A., & Ziv, J. (1977). “A Universal Algorithm for Sequential Data Compression.” IEEE Transactions on Information Theory, 23(3), 231-237. LZ77 compression algorithm.
• Huffman, D. A. (1952). “A Method for the Construction of Minimum-Redundancy Codes.” Proceedings of the Institute of Radio Engineers, 40(9), 1098-1101. Huffman coding.
• ITU-T. (1992). Information technology - Digital compression and coding of continuous-tone still images: Compression and coding control information. Recommendation T.81. JPEG standard.
• ISO/IEC JTC1/SC6. (1994). Information technology - Coding of still picture images: Part 1: Requirements and extension range. Standard ISO/IEC 10918-1. JPEG standard.
• Painter, M. F., & Spanias, A. (1999). Perceptual coding of digital audio. Proceedings of the IEEE, 87(4), 704-731. Survey of psychoacoustic models for audio compression, including frequency masking, temporal masking, and threshold of hearing.