PaperlayerView exact revision on arXiv

Source-linked AI summary

Fixed-length lossy compression in the finite blocklength regime

Victoria Kostina, Sergio Verdú

arXiv:1102.3944v3cs.IT

TL;DR

The paper asks how much rate is required to achieve a target distortion and excess probability at finite blocklength, where asymptotic results do not suffice. It derives general achievability and converse bounds, then shows that for stationary memoryless sources with separable distortion, the finite-blocklength rate is closely approximated by the rate-distortion function plus a dispersion term. The analysis also identifies zero-dispersion cases and uses a nonasymptotic refinement of the lossy AEP in the Gaussian approximation.

  • Problem

    At finite blocklength, existing lossy source-coding and reliability results do not determine the minimum rate needed to sustain a target fidelity and excess probability.

  • Method

    The paper derives general achievability and converse bounds and analyzes their asymptotic behavior for stationary memoryless sources with separable distortion.

  • Results

    For stationary memoryless sources, the bounds yield a close approximation of the finite-blocklength rate using the rate-distortion and rate-dispersion functions; the rate dispersion can vanish in characterized cases.

  • Takeaways & Limitations

    Unless the blocklength is small, rate dispersion together with the rate-distortion function gives a tight approximation to the finite-blocklength fidelity-rate tradeoff.

Abstract

from arXiv · show

This paper studies the minimum achievable source coding rate as a function of blocklength $n$ and probability $ε$ that the distortion exceeds a given level $d$. Tight general achievability and converse bounds are derived that hold at arbitrary fixed blocklength. For stationary memoryless sources with separable distortion, the minimum rate achievable is shown to be closely approximated by $R(d) + \sqrt{\frac{V(d)}{n}} Q^{-1}(ε)$, where $R(d)$ is the rate-distortion function, $V(d)$ is the rate dispersion, a characteristic of the source which measures its stochastic variability, and $Q^{-1}(ε)$ is the inverse of the standard Gaussian complementary cdf.

I. INTRODUCTION

The paper addresses fixed-length lossy compression when short blocklengths make asymptotic rate-distortion results insufficient. It develops general finite-blocklength bounds and studies their behavior for several memoryless source settings.

  • Motivation: Short blocklengths create an unavoidable rate penalty relative to the asymptotic rate-distortion function at a target fidelity.Delay and complexity constraints motivate assessing this penalty directly, since existing lossy coding and reliability theorems do not answer the fixed-blocklength question.
  • Contribution: New achievability and converse bounds characterize the minimum sustainable rate as a function of blocklength and excess probability for general sources and distortion measures.The paper frames excess distortion as the probability that reproduction distortion exceeds d.
  • Contribution: For stationary memoryless sources with separable distortion, the finite-blocklength coding rate is closely approximated using the rate-distortion and rate-dispersion functions.The approximation depends on blocklength n, excess probability ε, distortion level d, and V(d), the rate-dispersion function.
  • Evaluation: The bounds are evaluated for stationary discrete memoryless, Gaussian memoryless, and binary memoryless sources under specified distortion measures.The listed cases use symbol error, mean-square error, and bit error rate distortion, respectively.
  • Evaluation: In the equiprobable source with symbol error rate distortion, the rate-dispersion function is zero.This is identified as the most basic special case in the paper’s evaluation.
  • Operational definitions: The paper defines fixed-length lossy codes through encoder-decoder mappings and evaluates them under average or excess-distortion criteria.The excess-distortion criterion requires the probability of distortion exceeding d to be at most ε.

III. PRIOR WORK

Prior work develops asymptotic and finite-blocklength achievability and converse bounds for lossy compression, but existing converses can be loose at moderate blocklengths and some asymptotic analyses neglect distortion variability.

  • Achievability bounds: Existing work establishes general achievability results for lossy compression and specializes them to memoryless sources with separable distortion measures.The reviewed results include finite-alphabet and Gaussian source settings, including fixed- and variable-length schemes.
  • Converse bounds: Classical converse results use mutual information, error exponents, strong converses, and non-asymptotic bounds for fixed- and variable-length compression.These results cover general sources, finite-alphabet memoryless sources, and prefix-free variable-length codes.
  • Converse bounds: Theorem 5 provides loose lower bounds on R(n, d, ǫ) unless n is very large, where the rate-distortion function is already tight.This motivates sharper finite-blocklength converse bounds.
  • Asymptotic refinements: The lossy AEP and second-order refinements characterize asymptotic distortion-ball behavior and Gaussian fluctuations governed by the rate-dispersion function.The reviewed refinements include almost-sure expansions with logarithmic correction terms.
  • Asymptotic refinements: Prior redundancy analyses can be overly optimistic because average overhead over the distortion-rate function is dwarfed by stochastic distortion variability.This limitation is stated for analyses covering finite-alphabet, Gaussian, and abstract-alphabet sources.
  • Contributions: The paper introduces general achievability and converse results for arbitrary sources and distortion measures, including a binary-hypothesis-testing-based converse tighter than an earlier converse in some cases.The general results apply to the paper’s setup, while the newer converse uses binary hypothesis testing.

B. Achievability bounds

The section develops exact and computable achievability results for fixed-length lossy compression, then characterizes their asymptotic behavior through rate dispersion and Gaussian approximations.

  • General achievability: The paper gives an exact analysis of the excess distortion probability achieved by random coding for arbitrary sources and distortion measures.The expected excess probability equals E[1 − P_Y(B_d(X))]^M for independently generated reproduction codewords.
  • General achievability: Theorem 10 provides an achievability bound based on the exact random-coding performance, improving Shannon’s random-coding bound at the cost of greater computational difficulty.Its sharper performance expression is exact, whereas Shannon’s bound upper bounds that performance.
  • General achievability: Corollary 11 converts the exact random-coding expression into a more numerically stable achievability bound using (1 − x)^M ≤ e^−Mx.The optimization remains over reproduction distributions independent of the source.
  • Asymptotic behavior: The rate-dispersion function is defined as the variance of d-tilted information, measuring the stochastic variability governing finite-blocklength penalties.For the relevant rate-distortion-achieving reproduction distribution, the mean of the same random variable equals R(d).
  • Asymptotic behavior: For V(d) = 0, the d-tilted information is deterministic almost surely, and the lower bound can be strengthened non-asymptotically.The zero-dispersion condition is equivalent to d-tilted information being deterministic with probability 1.

C. Proof of Theorem 12

The proof of Theorem 12 combines nonasymptotic bounds with concentration tools to establish the Gaussian approximation for positive and zero rate dispersion, and then derives distortion-dispersion consequences.

  • Proof of Theorem 12: The proof uses a Berry–Esseen central limit theorem to control sums of independent d-tilted information variables when V(d) > 0.The converse applies Berry–Esseen to lower-bound the excess-distortion probability, while achievability applies it to upper-bound that probability.
  • Proof of Theorem 12: A nonasymptotic refinement of the lossy AEP supplies the auxiliary estimate needed to analyze the achievability bound.Lemma 2 provides constants n0, c, and K under restrictions (i)–(iv).
  • Proof of Theorem 12: The converse requires only that d-tilted information have a finite absolute third moment, a weaker condition than restriction (iv).The proof explicitly replaces restriction (iv) with condition (iv′) for the converse.
  • Proof of Theorem 12: When V(d) = 0, d-tilted information equals R(d) almost surely, allowing direct choices of γ and log M to establish the required probability bound.The zero-dispersion case is handled separately in both the converse and achievability arguments.
  • Distortion-dispersion consequences: The distortion-dispersion function follows by inverting the finite-blocklength rate-distortion relation when R(d) is twice differentiable and R′(d) ≠ 0.For Gaussian memoryless sources with mean-square error distortion, the required blocklength is essentially independent of the target distortion.

VI. BINARY MEMORYLESS SOURCE

For binary memoryless sources, the paper develops specialized achievability and converse bounds and evaluates their Gaussian approximations at finite blocklength. The equiprobable case has zero rate dispersion, while the new bounds tightly bracket the fundamental limit in numerical examples.

  • Equiprobable BMS: Theorem 15 gives a converse bound for every (n, M, d, ε) code in the equiprobable binary memoryless setting.
  • Equiprobable BMS: Theorem 16 identifies the exact minimum averaged excess-distortion probability achieved by random coding and shows it is attained by an equiprobable reproduction distribution.
  • Equiprobable BMS: The equiprobable binary memoryless source with bit-error distortion has zero rate dispersion for every distortion level d.Its finite-blocklength rate therefore admits a specialized Gaussian approximation.
  • Equiprobable BMS: Theorem 18 gives a Gaussian approximation for the minimum achievable equiprobable-BMS rate at blocklength n.
  • Equiprobable BMS: The new converse and achievability bounds tightly sandwich the finite-blocklength fundamental limit, while the Gaussian approximation is accurate except at very small blocklengths.The approximation is described as somewhat optimistic in the displayed region.
  • Non-equiprobable BMS: With more stringent ε, the Gaussian approximation lies essentially halfway between the converse and achievability bounds, while the new bounds remain fairly tight except at very small blocklengths.

VII. DISCRETE MEMORYLESS SOURCE

For discrete memoryless sources under symbol-error distortion, the paper specializes finite-blocklength converse and achievability bounds and derives Gaussian approximations. The analysis includes fixed-composition codes, parametric rate dispersion, and a blocklength consequence near maximum distortion.

  • Equiprobable DMS: Theorem 24 provides a converse bound for any discrete-memoryless-source code under symbol-error distortion.
  • Equiprobable DMS: Theorem 25 gives the exact minimum averaged excess-distortion probability for random coding with M codewords in the equiprobable discrete-memoryless setting.The result is attained by an equiprobable reproduction distribution on A^n.
  • Equiprobable DMS: Theorem 26 converts the random-coding result into an achievability bound for equiprobable discrete memoryless sources.
  • Equiprobable DMS: Theorem 27 gives a Gaussian approximation for the minimum achievable equiprobable-DMS rate at blocklength n.
  • Nonequiprobable DMS: For nonequiprobable discrete memoryless sources, Theorems 29 and 30 provide converse and fixed-composition achievability bounds.The fixed-composition code uses codewords of a specified type t⋆.
  • Nonequiprobable DMS: Theorem 31 characterizes the Gaussian approximation through the rate-distortion function R(d) and a parametric rate-dispersion function V(d).The theorem also strengthens the remainder-term characterization under stated distortion conditions.
  • Nonequiprobable DMS: As d approaches dmax, the blocklength required to approach 1.1R(d) with a specified excess-distortion probability grows rapidly.

VIII. ERASED BINARY MEMORYLESS SOURCE

The erased binary memoryless source is analyzed through new converse and achievability bounds, yielding a Gaussian approximation and explicit rate-dispersion behavior. The bounds are extremely tight in the numerical example, with a 9% penalty over rate-distortion at blocklength 1000.

  • Bounds: Theorems 32 and 33 provide converse and achievability bounds for binary erasure-source compression under bit-error distortion.The analysis accounts separately for erased and nonerased symbols when bounding excess-distortion probability.
  • Gaussian approximation: Theorem 34 gives a Gaussian approximation for the minimum achievable rate at blocklength n.The approximation uses the rate-dispersion function associated with the erased binary memoryless source.
  • Numerical evaluation: Fig. 5 plots the rate-dispersion function and the blocklength required to sustain R = 1.1R(d) under an excess-distortion constraint.The setting is a binary erasure source with erasure rate δ = 0.1.
  • Rate dispersion: The rate-dispersion function grows without limit as d approaches δ.At d = δ/2, vanishingly small excess-distortion probability cannot be sustained because about half of erased bits remain incorrectly reconstructed.
  • Numerical evaluation: The achievability and converse bounds are extremely tight, and at blocklength 1000 the penalty over the rate-distortion function is 9%.The bounds and Gaussian approximation are compared numerically in Fig. 6.

IX. GAUSSIAN MEMORYLESS SOURCE

The Gaussian memoryless source is treated with geometric converse and achievability arguments based on high-dimensional balls and spheres. These bounds lead to a Gaussian approximation whose rate-dispersion term is correct, while one achievability construction has a weaker remainder term.

  • Converse: Theorem 36 gives a converse for Gaussian memoryless compression with mean-square error distortion.The converse lower-bounds the number of radius-√(nd) balls needed to cover a set of Gaussian probability at least 1 − ǫ.
  • Achievability: Theorems 37 and 39 provide achievability bounds using representation points on or inside high-dimensional spheres.Theorem 37 uses codewords on a sphere, while Theorem 39 uses a covering result for balls.
  • Gaussian approximation: Theorem 40 gives a Gaussian approximation for the minimum achievable rate at blocklength n.Its proof combines the converse and achievability analyses with Gaussian approximation tools.
  • Gaussian approximation: Theorem 39 has the correct rate-dispersion term but a weaker remainder term.Theorem 37 underlies the achievability part of the approximation in Theorem 40.
  • Numerical evaluation: At shorter blocklengths, the achievability bound in (233) is tighter than the one in (221), while the converse in (218) is tighter than the one in (216).These comparisons are reported from the numerical evaluations shown in Figures 8 and 9.

X. CONCLUSION

The paper develops general fixed-blocklength achievability and converse bounds for lossy compression and uses their tightness for stationary memoryless sources to derive a compact approximation. The rate dispersion, together with the rate-distortion function, approximates the fidelity-rate tradeoff except at small blocklengths.

  • Conclusion: New achievability and converse bounds apply in full generality and are tighter than existing bounds.They estimate the minimum rate needed for a given fidelity at a given blocklength.
  • Conclusion: For stationary memoryless sources, bound tightness yields a compact closed-form expression for the excess rate over the rate-distortion function.The expression applies in the nonasymptotic regime.

APPENDIX A HYPOTHESIS TESTING

The appendix develops hypothesis-testing representations and auxiliary probabilistic results used to extend finite-blocklength converse and Gaussian-approximation arguments. It also supports the treatment of cases where the rate-distortion function is not attained by an output distribution.

  • Hypothesis testing: The appendix represents finite-blocklength quantities through ordered source probabilities and randomized tests between PX and the counting measure U.The minimum code size at excess-distortion probability ǫ is connected to these testing quantities.
  • d-tilted information: The definition of d-tilted information is extended so Theorem 7 and the converse part of Theorem 12 remain valid even without an achieving output distribution.The extension uses an alternative representation of the rate-distortion function.
  • d-tilted information: For memoryless sources, the appendix shows that the extended d-tilted information still single-letterizes under the stated restrictions.Lemma 3 establishes the relevant identity.
  • Gaussian approximation: The Gaussian approximation proof controls empirical fluctuations and remainder terms using Taylor expansions, moment bounds, Berry–Esseen inequalities, and union bounds.These steps are organized through Lemmas 4 and 5.

APPENDIX E PROOF OF THEOREM 14

The appendix derives the approximation for the distortion difference d_n − d_∞ by combining convexity, uniform remainder control, Taylor expansions, and Stirling-based bounds.

  • Geometric reduction: Convexity of R(d) and the tangent relation tan α_n = |R′(d_n)| connect the rate gap to d_n − d_∞.The construction sets R(n, d_n, ε) = R_∞ and uses the tangent angle at d_n.
  • Uniform approximation: Uniform remainder bounds permit applying the fixed-distortion approximation to sequences d_n in a neighborhood of d_∞.The neighborhood is a compact set B_δ(d_∞), over which the relevant constants and remainders are uniformly bounded.
  • Refinement: Taylor’s theorem refines the intermediate bound using finite V′(d) and R′′(d) throughout B_δ(d_∞).These regularity conditions control the local expansions needed for the final approximation.
  • Conclusion: Rearranging the derived relation yields the desired approximation for d_n − d_∞.The appendix explicitly identifies this rearrangement as the final step to equation (117).
  • Boundary case: The argument also treats the d = 0 case directly from equation (89), or by substituting the corresponding parameter value into the preceding analysis.Both routes are stated as valid in the appendix.

APPENDIX G GAUSSIAN APPROXIMATION

The appendix establishes Gaussian approximations for binary and nonbinary settings by analyzing achievability and converse bounds with Stirling expansions, Taylor expansions, and Berry–Esseen estimates.

  • Binary case: A constant-composition code attaining the rate-dispersion function exists asymptotically in the binary setting.The argument uses the asymptotic behavior of the relevant bound and identifies V(d) as the rate-dispersion term.
  • Proof strategy: For both settings, achievability follows by converting code-existence bounds with (1 − x)^M ≤ e^(−Mx) and controlling probabilities through Berry–Esseen estimates.The nonbinary proof applies the same general strategy to its corresponding bounds.
  • Binary achievability: The binary achievability analysis chooses a rate satisfying the Gaussian-approximation expression so the excess-distortion probability is at most ε for sufficiently large n.The proof splits the probability into three terms and bounds them using Berry–Esseen and monotonicity arguments.
  • Nonbinary case: The nonbinary analysis similarly derives Gaussian approximations involving V(d), with rate expressions rewritten using the rate-distortion function.The proof uses local expansions of a twice-differentiable function g(∆) and constants independent of n.

APPENDIX J PROOF OF THEOREM 34

The appendix proves Theorem 34 by separately analyzing converse and achievability bounds, representing probabilities with i.i.d. variables and applying Berry–Esseen and Taylor-expansion arguments.

  • Converse: The converse lower-bounds the excess-distortion probability after expressing the relevant probability through random variables Z_1, …, Z_n.The resulting steps use previously established relations together with Berry–Esseen bounds.
  • Regularity condition: The proof assumes finite third central moment for Z, ensuring that the Berry–Esseen constant B_n is finite.This condition is used in the Gaussian approximation analysis.
  • Achievability: The achievability proof converts the bound into probabilities of i.i.d. variables Z_1, …, Z_n and upper-bounds the resulting terms.The proof uses (1 − x)^M ≤ e^(−Mx) and Berry–Esseen estimates for selected terms.
  • Rate expansion: Taylor expansion of Q^−1(·) rewrites the chosen rate in the target Gaussian-approximation form.This rewriting is stated for the rate expressions used in the proof.
  • Integral bounds: Monotonicity of g(z) identifies its global minimum at z = [1 − 2d]^+ and supports bounding the integral regions.The achievability argument splits the integral into three parts and handles the first and third with Berry–Esseen bounds.
Loading 1102.3944v3…