Lossy Compression and the Rate-Distortion Tradeoff

Lossless compression asks: what is the shortest exact description of this data? Entropy answers it, and no scheme beats that floor.

Lossy compression asks a different question entirely: given that I may only spend R bits per sample, what is the closest reconstruction I can produce? The output is not the input. That is the point, not a defect.

This reframing matters because the two are often ranked as if lossy were a compromised version of lossless. They optimise different objectives. A lossless coder has one degree of freedom, the code. A lossy coder has two, the code and how much fidelity to surrender, and the second one dominates the result.

The practical consequence: asking "how much does JPEG compress?" is not a well-formed question. It compresses as much as you ask it to. The real question is what you get back.

Fix a distortion measure, usually squared error. For a source and a tolerance D, the rate-distortion function R(D) is the smallest rate, in bits per sample, at which some coder achieves average distortion no worse than D.

Claude Shannon set this out in "Coding Theorems for a Discrete Source With a Fidelity Criterion", published in the Institute of Radio Engineers International Convention Record, volume 7, 1959. It is the lossy counterpart to his 1948 source coding theorem, and it has the same shape: a hard boundary no engineering can cross, proved without constructing a single practical codec.

R(D) is non-increasing. Demand less fidelity and the required rate falls. Two endpoints anchor it:

• D = 0 recovers lossless coding, where R is the entropy.
• Beyond some distortion, R(D) reaches zero: the tolerance is so loose that transmitting nothing at all satisfies it.

Shannon solved the Gaussian case in that same paper. For a Gaussian source of variance sigma squared under squared-error distortion, the rate-distortion function is

R(D) = (1/2) * log2( sigma^2 / D )     for D <= sigma^2
R(D) = 0                               for D >  sigma^2

Shannon states the second branch himself, noting that if the remaining variance is zero or negative then R is zero, since a single fixed point suffices. The base-2 half-log form above is the modern textbook rendering, not his notation.

Put numbers on it, with sigma squared = 1:

D = 0.25  ->  R = 0.5 * log2(4)   = 1.00 bit/sample
D = 0.01  ->  R = 0.5 * log2(100) = 3.32 bits/sample
D = 1.00  ->  R = 0.5 * log2(1)   = 0    bits/sample

Now the useful reading. Halving D costs exactly half a bit per sample, because 0.5 * log2(2) = 0.5. Every extra half bit buys you a factor-of-two reduction in squared error, forever. Quality is logarithmic in rate, which is why codec bitrate ladders climb in ratios rather than steps.

Rate-distortion theory says a bound exists. It does not say how to reach it. Transform coding is the practical answer for images and audio.

The idea: raw samples are highly correlated, and correlated samples waste bits because each one partly repeats its neighbours. Apply a linear transform that decorrelates them and concentrates the energy into a few coefficients. Then spend bits where the energy is and almost none elsewhere.

The discrete cosine transform was introduced by N. Ahmed, T. Natarajan and K. R. Rao in "Discrete Cosine Transform", IEEE Transactions on Computers, volume C-23, number 1, pages 90 to 93, January 1974. Note the volume carries a C prefix, part of the designation for that era of the journal.

The DCT is not the optimal decorrelating transform. That is the Karhunen-Loeve transform, which is signal-dependent and expensive: you must compute and transmit its basis. The DCT is a fixed, signal-independent approximation that comes close on natural images and has a fast algorithm. That trade, slightly worse compaction for vastly cheaper computation and no side information, is why it won.

Every stage except one is reversible. The colour conversion, the block split, the DCT, the zigzag scan and the entropy coding all preserve information exactly, up to arithmetic rounding. Chroma subsampling throws away some colour resolution, and quantisation throws away the rest. Everything downstream of quantisation is lossless packing of an already lossy result.

Quantisation divides each DCT coefficient by a value from a table and rounds to an integer. Large divisors on high-frequency coefficients round most of them to zero, and long runs of zeros compress to almost nothing.

ITU-T Recommendation T.81 gives an example luminance table in Annex K. Its first row reads:

16  11  10  16  24  40  51  61

The values grow toward the bottom right, which is the high-frequency corner, so fine detail is quantised hardest.

Two precision points that are widely got wrong. First, these tables are not the JPEG quantisation tables. Annex K states they are "provided as examples only and are not necessarily suitable for any particular application", the annex itself "does not form an integral part of this Recommendation", and clause F.1.1.4 says plainly: "No default quantization tables are specified in this Specification." Every encoder ships its own, which is a large part of why encoders differ in quality at equal file size.

Second, Annex K does note that halving these values usually yields a reconstruction "nearly indistinguishable from the source image". That is a statement about the quantiser, not about any compression ratio.

There is a widely repeated claim that JPEG is visually indistinguishable at around ten to one compression. It is difficult to source, and the figure most people are reaching for is measured in different units entirely.

Gregory Wallace, in the JPEG overview article revised from the April 1991 Communications of the ACM piece, gives a quality scale in bits per pixel, defined as the total compressed bits including chrominance divided by the number of luminance samples:

• around 0.25 bits/pixel: moderate to good quality
• around 0.75 bits/pixel: good to very good
• 1.5 to 2.0 bits/pixel: usually indistinguishable from the original

Wallace immediately hedges it: "These levels are only a guideline, quality and compression can vary significantly according to source image characteristics and scene content."

Converting 1.5 bits/pixel into a ratio requires assuming a 24-bit-per-pixel source, an inference Wallace never makes. Quote the bits per pixel, attribute it to Wallace, and keep the hedge. A number that has quietly changed units on its way to you is worse than no number.

Image coding discards what the eye weights least. Audio coding goes further and exploits a specific property of hearing: masking. A loud tone raises the threshold of audibility for nearby frequencies, and for a short window in time around it. Anything pushed below that raised threshold cannot be heard, so it need not be coded.

This is a different principle from everything so far. The DCT exploits structure in the signal. Masking exploits structure in the receiver.

MP3 is Layer III of ISO/IEC 11172-3:1993, "Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbit/s, Part 3: Audio". The perceptual coding literature is surveyed by Ted Painter and Andreas Spanias in "Perceptual coding of digital audio", Proceedings of the IEEE, volume 88, number 4, pages 451 to 515, April 2000.

The baseline to beat is CD audio: 44,100 samples per second, 16 bits, 2 channels.

44100 * 16 * 2 = 1,411,200 bit/s, about 1411 kbps

Claims like "AAC at 96 kbps matches MP3 at 128 kbps" circulate widely and are hard to source. Here is what a real controlled test found.

EBU Tech 3296, "EBU subjective listening tests on low-bitrate audio codecs" (June 2003), used 28 subjects and tested codecs including AAC and MP3 head to head at 48 and 64 kbit/s stereo. At 64 kbit/s the report records that "the worst codec at this bitrate (i.e. mp3) was only in the fair category".

That looks like a clean win until you read the caveat the same report attaches: the AAC encoder tested "did not provide a better quality when increasing the bitrate from 48 kbit/s to 64 kbit/s" because the version under test "had not been optimized for bitrates higher than 48 kbit/s".

So the honest reading is narrower than the headline. The test covers 16 to 64 kbit/s only, and it evaluates specific encoder implementations from 2003, not the formats in the abstract. A codec comparison is always a comparison of encoders at a bitrate on a corpus with a listener panel. Strip any of those four and the number stops meaning anything.

Video reuses the image machinery and adds the trick that dominates its gains: motion compensation. Rather than coding each frame, the encoder predicts a block from a displaced region of an already-decoded frame, transmits the motion vector, and codes only the residual. On typical footage the residual is far cheaper than the frame.

Generational gains are real but routinely overstated, because the headline number depends on the metric. Ohm, Sullivan, Schwarz, Tan and Wiegand measured HEVC against H.264/AVC in IEEE Transactions on Circuits and Systems for Video Technology, volume 22, number 12, pages 1669 to 1684, December 2012:

The familiar "HEVC halves the bitrate" comes from the subjective column, and the paper says explicitly that the subjective improvement "somewhat exceeds the improvement measured by the PSNR metric". The later JCT-VC verification test by Tan and colleagues, same journal, volume 26, number 1, pages 76 to 90, January 2016, reports 59% subjective against 44% by PSNR.

Always state whose measurement and by which metric. A codec claim without both is not checkable.

Neural compression replaces the hand-designed transform with a learned one. An encoder network maps the image to a latent, the latent is quantised and entropy coded under a learned probability model, and a decoder network reconstructs. Crucially the whole thing is trained on the rate-distortion objective directly, minimising rate plus lambda times distortion, so the tradeoff this lesson began with becomes the literal loss function.

The foundational pair are Balle, Laparra and Simoncelli, "End-to-end Optimized Image Compression", ICLR 2017, and Balle, Minnen, Singh, Hwang and Johnston, "Variational image compression with a scale hyperprior", ICLR 2018.

Because squared error correlates poorly with perceived quality, this field often optimises or evaluates against learned perceptual metrics such as LPIPS, from Zhang, Isola, Efros, Shechtman and Wang, "The Unreasonable Effectiveness of Deep Features as a Perceptual Metric", CVPR 2018. LPIPS is the metric's name, not the paper's title.

Standardisation has begun. JPEG AI is ISO/IEC 6048 and ITU-T T.840; Part 1, the core coding system, was published in 2025 as ITU-T T.840.1 and ISO/IEC 6048-1:2025. The remaining parts are planned, not published.

A closing gotcha on reading claims. AOMedia's own site advertises AV1 as "30% better compression" against unnamed "alternatives", citing a third-party study. The VVC figure of roughly 50% over HEVC comes from Bross and colleagues, IEEE TCSVT volume 31, number 10, October 2021, whose authors are the standard's own editors, and whose measured PSNR results are 25.1% for all-intra and about 42% for random access at UHD. Neither claim is dishonest. Neither is neutral either.