Fixed-length lossy compression in the finite blocklength regime

Abstract

This paper studies the minimum achievable source coding rate as a function of blocklength $n$ and probability $\epsilon$ 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}(\epsilon )$, 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}(\epsilon )$ is the inverse of the standard Gaussian complementary cdf.

Cited by in corpus (25)

• On the Dispersions of Three Network Information Theory Problems
• Semidefinite Programming Approach to Gaussian Sequential Rate-Distortion Trade-offs
• Hardware-Limited Task-Based Quantization
• Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and Decoding
• One-shot lossy quantum data compression
• A Unified Framework for One-shot Achievability via the Poisson Matching Lemma
• Second-Order Region for Gray-Wyner Network
• On Finite Blocklength Lossy Source Coding
• Lossless Source Coding in the Point-to-Point, Multiple Access, and Random Access Scenarios
• Discrete Lossy Gray-Wyner Revisited: Second-Order Asymptotics, Large and Moderate Deviations
• Resolution Limits for the Noisy Non-Adaptive 20 Questions Problem
• Distributed Quantization Networks
• On privacy amplification, lossy compression, and their duality to channel coding
• Neural Distributed Compressor Discovers Binning
• Lossy Compression via Sparse Linear Regression: Performance under Minimum-distance Encoding
• Finite-Block-Length Analysis in Classical and Quantum Information Theory
• The Dispersion of the Gauss-Markov Source
• Cumulant Generating Function of Codeword Lengths in Variable-Length Lossy Compression Allowing Positive Excess Distortion Probability
• The Rate-Distortion Function and Excess-Distortion Exponent of Sparse Regression Codes with Optimal Encoding
• Nonstationary Gauss-Markov Processes: Parameter Estimation and Dispersion
• Non-Asymptotic Bounds and a General Formula for the Rate-Distortion Region of the Successive Refinement Problem
• On the compression of messages in the multi-party setting
• Exponential Strong Converse for Successive Refinement with Causal Decoder Side Information
• Information-Theoretic Limits of Quantum Learning via Data Compression
• The Mutual Information In The Vicinity of Capacity-Achieving Input Distributions