The Dispersion of Lossy Source Coding

Abstract

In this work we investigate the behavior of the minimal rate needed in order to guarantee a given probability that the distortion exceeds a prescribed threshold, at some fixed finite quantization block length. We show that the excess coding rate above the rate-distortion function is inversely proportional (to the first order) to the square root of the block length. We give an explicit expression for the proportion constant, which is given by the inverse Q-function of the allowed excess distortion probability, times the square root of a constant, termed the excess distortion dispersion. This result is the dual of a corresponding channel coding result, where the dispersion above is the dual of the channel dispersion. The work treats discrete memoryless sources, as well as the quadratic-Gaussian case.

2011 Data Compression Conference, to appear (submitted Nov. 2010)

Cited by in corpus (11)

• The Dispersion of Joint Source-Channel Coding
• Non-Asymptotic and Second-Order Achievability Bounds for Coding With Side-Information
• Refined Asymptotics for Rate-Distortion using Gaussian Codebooks for Arbitrary Sources
• Equivocations, Exponents and Second-Order Coding Rates under Various Rényi Information Measures
• Second-Order Coding Rates for Conditional Rate-Distortion
• Strong Successive Refinability and Rate-Distortion-Complexity Tradeoff
• Second-Order and Moderate Deviation Asymptotics for Successive Refinement
• Moderate-Deviations of Lossy Source Coding for Discrete and Gaussian Sources
• A Case Where Interference Does Not Affect The Channel Dispersion
• Nonasymptotic noisy lossy source coding
• On Dispersions of Discrete Memoryless Channels with Noncausal State Information at the Encoder