Rate-distortion function

Minimum asymptotic lossy coding rate for a memoryless source and single-letter distortion.

Specification version 1Published 1959-03-011 evidence records

About this problem

The question, scope, and sources behind this Registry record.

Formal question

Determine the minimum asymptotic coding rate achieving expected distortion at most D.

Scope & constraints

source: stationary memoryless
logBase: 2
distortion: single-letter expected distortion
finiteAlphabets: true

Primary sources

Coding theorems for a discrete source with a fidelity criterion — Rate-distortion function Rate-distortion theorem

What we know

Current frontiers derived from accepted Claims.

Exact established valueR(D) = min_{p(xhat|x): E d(X,Xhat)<=D} I(X;Xhat)

The accepted equality closes this optimization result.

Claims

Assertions tied to evidence, attribution, and review.

2026

CLM-INFO-003211= R(D) = min_{p(xhat|x): E d(X,Xhat)<=D} I(X;Xhat)EXACT VALUEThe cited theorem establishes R(D) = min_{p(xhat|x): E d(X,Xhat)<=D} I(X;Xhat) under the current specification; this does not assert universal empirical attainability.Source: Coding theorems for a discrete source with a fidelity criterion — Rate-distortion function ↗

PROVEN

Timeline

The frontier as it changed over time.

How this frontier is derived

Only accepted Claims matching the current specification contribute to the displayed bounds. Strict inequalities remain open; contradictory Claims require editorial review.

—No breakthrough events recorded yetEvents appear here when an accepted Claim tightens a bound or closes the frontier.