CS Paper Radar

Exact Second-Order Asymptotics for the Gaussian Gray--Wyner Problem

Lin Zhou, Lei Yu

cs.IT ·submitted 2026-10-28 05:44 UTC · v1
theory

Abstract

We revisit the Gray-Wyner problem of lossy compression of bivariate Gaussian sources under the quadratic distortion measure and derive the exact second-order asymptotics. Specifically, we first identify the boundary rate tuples using the explicit first-order asymptotics by Yu (TIT 2023) and then characterize the tradeoff among three second-order coding rates subject to a constraint on the joint excess-distortion probability. Our main contribution is the achievability proof, where we derive a covariance shell covering lemma that is analogous to the type covering lemma for the discrete case. In particular, our covering lemma classifies the source sequences into power shell types via their empirical covariance matrix. For each such power shell type, we derive sufficient conditions on the compression rates so that covering within distortion levels are achievable. Finally, asymptotical analysis via the Berry-Esseen theorem yields the desired result.

Closest papers

Nearest neighbours by meaning across the whole index.

Third-Order Asymptotics for Fixed-Length Lossy Compression of Discrete Memoryless Sources

cs.IT ·2026-11-10 ·Vincent Y. F. Tan
hot direction similarity 0.68
Abstract · 16 pages, 2 figures

This paper determines the third-order asymptotics of the logarithm of the minimum codebook size for fixed-length lossy compression of discrete memoryless sources. For an excess-distortion probability constraint $\varepsilon\in(0,1)$ and every interior distortion level, we establish a third-order correction of $\frac12\log n+O(1)$, where $n$ is the blocklength. This sharpens the general bounds of Kostina and Verdú [IEEE Trans. Inf. Theory, 2012]. The main technical innovation lies in the converse for positive dispersion. Under a reverse change of measure, we retain the exponential weights associated with tilted information and distortion slack and control them jointly using the multivariate weighted-strip estimate of Scarlett, Martinez, and Guillén i Fàbregas [Proc. IEEE ISIT, 2015]. A pairing argument verifies the required covariance nondegeneracy uniformly over all reconstruction words whose distortion balls meet a typical set, yielding the matching converse.

0.31

Exact Second-Order Asymptotics for the Discrete Wyner--Ziv Problem

cs.IT ·2026-10-08 ·Lin Zhou
similarity 0.65
Abstract

We revisit the discrete Wyner--Ziv problem and establish exact second-order asymptotics. Our main contribution is a second-order converse bound, which is derived using posterior decomposition, concentration inequalities, and a conditional Gaussian approximation for martingales. Furthermore, we extend the previous best known achievability result of Li and Li (arXiv 2025) by allowing the test channel to depend on the type of the observed source sequence. Exact second-order asymptotics are established by combining our achievability and converse bounds. In particular, we show that the achievability bound of Li and Li (arXiv 2025) is not optimal in general. Specifically, we provide two numerical examples to illustrate our results: a binary asymmetric source and a quaternary source. For the first example, the achievability bound of Li and Li (arXiv 2025) achieves the optimal second-order asymptotics. However, in the second example, we show that our achievability result is optimal, which reduces the second-order coding rate of Li and Li (arXiv 2025) by $10.77\%$ at the excess-distortion probability of $0.1$ and by $21.35\%$ at the excess-distortion probability of $0.2$.

0.43

Second-Order Asymptotics for the Gaussian Multiple-Access Channel at Corner Points

cs.IT ·2026-08-18 ·Vincent Y. F. Tan
theory similarity 0.64
Abstract · 28 pages, 4 figures

We establish exact second-order coding rate regions at the two corner points of the capacity region of the two-user Gaussian multiple-access channel. For any average error probability $\varepsilon\in(0,1)$, we characterize the $n^{-1/2}$-scale fluctuations of achievable rates around each corner point, proving a converse that matches the previously known achievability bound. The proof first extracts a rectangular subcode that preserves the independence of the two transmitted codewords. The Polyanskiy--Verdú good-code output distribution theorem then yields log-determinant constraints that induce a spectral decomposition of a trimmed codebook into diffuse and exceptional subspaces. An entropic Brascamp--Lieb projection inequality controls the codeword inner product on the diffuse subspace, while variance-inflated Gaussian output distributions handle the low-dimensional exceptional subspace. Combining these two treatments yields the joint Gaussian limit required for the matching second-order converse.

0.47

Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation

cs.LG ·2026-08-20 ·Tao Jiang, Minbo Gao, Shaowei Cai
theoryhot direction similarity 0.63
Abstract

A pointwise-unbiased one-bit compressor reconstructs every real input in expectation while transmitting one bit. For a scalar source $P$ with CDF $F$, mean $m$, and $\mathcal J(P)=\int_{\mathbb R}\sqrt{F(r)(1-F(r))}\,dr$, we prove that the infimum of the source-averaged reconstruction second moment over all public-coin one-bit codes unbiased on $\mathbb R$ is $m^2+\mathcal J(P)^2$. For regular full-support sources, a distribution-centered random-threshold code attains this value; a converse over arbitrary randomized binary encoders and an equality analysis characterize every attaining code up to null sets, bit relabeling, and public-seed refinement. For the Gaussian location family $\mathcal N(μ,σ^2)$ with $|μ|\le cσ$, the equal prior on the endpoint means is least favorable and the minimax value is $σ^2Λ_c^2$. Exact Gaussian minimax optimality forces a critical heavy tail: at the endpoint means, absolute moments are finite exactly for $p<3$, and $\Pr(W>t)=Θ(t^{-3}/\sqrt{\log t})$. A Cauchy-mixture robustification inflates the second moment by at most $1/(1-η)$ while making every positive-order absolute moment finite. Finite-support public randomness with finite decoder means cannot achieve exact unbiasedness on $\mathbb R$, but a bounded-output approximation using exactly $R$ shared random bits has explicit bias and second-moment bounds converging to the minimax constant. Finally, coordinate allocation communicates exactly $B$ bits per Gaussian-gradient query. On Kim's continuous quadratic hard family, the expected optimization guarantee matches the lower bound in its dependence on $(σ,d,B,\varepsilon)$, and a finite-variance high-probability bound incurs only a logarithmic confidence factor.

0.24

Joint Source-Channel Coding of Gaussian Sources over Block Erasure Channels: Nonasymptotic Bounds and Channel-Uniform Normal Approximations

cs.IT ·2026-09-30 ·Adeel Mahmood
benchmark similarity 0.61
Abstract · Added an SSCC achievability benchmark and expanded numerical results

We study finite-blocklength lossy transmission of a Gaussian memoryless source over memoryless, possibly nonstationary block erasure channels under an excess mean-squared distortion criterion. We derive computable nonasymptotic achievability and converse bounds and establish matching third-order, channel-uniform normal approximations. Our achievability bound exactly evaluates the ensemble-average excess-distortion probability of a specified random coding scheme and improves corresponding specializations of known general one-shot bounds. Our converse conditions on the erasure pattern and source energy and combines spherical-cap and volume bounds, with the spherical-cap term providing the geometric prefactor needed for the matching third-order term. In our channel-uniform normal approximation, we show that for fixed distortion ratio, target excess-distortion probability, and block size, the sufficient and necessary information-balance conditions have the same dispersion and $\frac{1}{2}\log k$ terms, where $k$ is the source blocklength, and differ only by bounded remainders that are uniform over the channel blocklength and erasure-probability profile. Numerical evaluations compare the nonasymptotic JSCC bounds and their common third-order normal approximation with an optimized symmetrized SSCC achievability benchmark.

0.12

Entropy of Bernoulli Measures Conditioned on Affine Subspaces and a Problem of Ancheta--Massey

cs.IT ·2026-08-24 ·Yihong Wu
similarity 0.60
Abstract

A textbook result in information theory is that linear encoders achieve the entropy for lossless compression of Bernoulli source with parameter $p$. For lossy compression, however, linearity is known to incur strict suboptimality compared to the rate-distortion function. Massey asked whether the optimal rate for linear encoding is achieved simply by compressing a fraction of the bits linearly and losslessly and estimating the rest by zero \cite{Massey1978}. For $p=\frac12$, Ancheta answered this question affirmatively \cite{Ancheta1978}. This note extends Ancheta's result to all $p<\frac12$. The key argument is to bound the entropy of the posterior distribution conditioned on an affine subspace in terms of its marginals. The proof was discovered by GPT-5.6 Sol in an interactive process guided by the author. The purpose of the present note is to communicate a simplified version of this proof and to make connections with the existing literature on coding theory and spin glass theory.

0.41

Rate-Distortion-Perception Tradeoff for Vector Gaussian Sources with Limited Common Randomness: Exact Characterization and Approximate Universality

cs.IT ·2026-11-03 ·Wentao Wang, Shuo Shao, Ruibin Li, Jingjing Qian, Jun Chen +1 more
theory similarity 0.58
Abstract

The distortion-rate-common randomness-perception (DRCP) theory characterizes how limited common randomness (CR) improves reconstruction fidelity under perceptual constraints, thereby providing an information-theoretic foundation for generative compression. In this paper, we characterize the DRCP tradeoff for vector Gaussian sources with limited CR under the squared-error distortion measure and the squared Wasserstein-2 perception measure. Specifically, we first establish a generalized reverse waterfilling characterization of globally optimal allocations. Second, we derive an analytical upper bound on the DRCP function through sequential greedy allocation of rate and CR. For fixed rate and CR budgets, the resulting representation is independent of the perception threshold. Finally, we establish its approximate universality through uniform performance guarantees: the achievable distortion exceeds the optimal distortion by at most $2ρ^*\approx0.2897$ times the total source variance, whereas the optimal-to-greedy distortion ratio is at least $η^*\approx0.7517$.

0.32

On the Information Bottleneck for Stable Variables

cs.IT ·2026-10-06 ·Dongmin Park, Jihad Fahs, Mohamad Assaad
similarity 0.58
Abstract · 13 pages, 3 figures

We consider a generalization of the Gaussian information bottleneck problem to jointly stable variables $X$ and $Y$. Specifically, for $X = Y + A$, where $A$ is stable and independent of $Y$, we find optimal stable linear encoders of the form $T = kX + N$, with $N$ stable and independent of $X$. We characterize the linear stable information bottleneck in closed-form and its critical value. Furthermore, we show that, except for the Gaussian case, such stochastic linear encoders are strictly suboptimal, while becoming asymptotically optimal at large compression rates. Our linear solution recovers the Gaussian information bottleneck for jointly Gaussian variables as a special case.

0.45