CS Paper Radar

Polarization on Bounded Euclidean Spaces and More General Compact Groups

Sharang M. Sriramu, Lampros Gavalakis, Ioannis Kontoyiannis, Aaron B. Wagner

cs.IT ·submitted 2026-10-23 15:03 UTC · v1
unusual

Abstract

We establish polarization for memoryless sources taking values on the unit-perimeter circle, or on more general compact groups, under Arıkan's polar transform. For sources with finite differential entropy, all but an $O((\log N)^{-1/12})$ fraction of the conditional differential entropies in successive cancellation order lie within any fixed positive distance of zero, where $N$ is the block length. Examples indicate that the true polarization rate is indeed very slow: an inverse-logarithmic rate does not underestimate the polarization speed at moderate block lengths.

Closest papers

Nearest neighbours by meaning across the whole index.

Neural Polar Codes for Source Coding

cs.IT ·2026-10-09 ·Bashar Huleihel, Ziv Aharoni, Haim H. Permuter
similarity 0.51
Abstract

This paper presents a data-driven approach to lossless and lossy source compression using polar codes. Classical polar source coding achieves fundamental limits with low complexity for binary memoryless sources. However, for unknown q-ary sources with memory, successive-cancellation (SC) decoding requires an explicit source model and can be computationally prohibitive. We present analytical SC recursions and show that exact implementations scale quadratically with alphabet size and cubically with state-space size. To overcome these limitations, we develop neural polar decoders trained directly from data to approximate conditional distributions of synthetic polar coordinates without requiring an explicit source model. These learned distributions enable estimation of entropy rates, mutual information, and rate-distortion functions, and support explicit polar compression schemes. For lossless compression, we identify high-entropy polarized coordinates and reconstruct the remaining coordinates using the learned SC recursion. For lossy compression, we combine neural polar decoders with a neural test channel to estimate and optimize the mutual information-distortion tradeoff and construct an explicit lossy polar code. We also extend the framework to Wyner-Ziv compression with decoder side information by learning conditional polarized distributions and a reconstruction mapping. Experiments on memoryless sources, sources with memory, and real genomic data show that the learned decoders closely match analytical SC decoders when available and remain applicable when conventional methods are computationally infeasible or the source model is unavailable.

0.15

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

cs.IT ·2026-08-24 ·Yihong Wu
similarity 0.48
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

MacKay-Neal Codes Achieve Capacity under MAP Decoding

cs.IT ·2026-10-07 ·Kenta Kasai
theory similarity 0.47
Abstract · 22 pages

Statistical-mechanical analyses predict that MacKay-Neal codes can achieve channel capacity at fixed degrees. We prove this prediction for the uncoupled $(\ell,3,3)$ MN socket ensemble for every fixed integer $\ell\ge4$. For each binary-input memoryless symmetric channel of capacity strictly greater than $3/\ell$, the ensemble-average block error probability under maximum a posteriori (MAP) decoding is $O(\log N/N)$, where $N$ is the transmitted blocklength. The actual transmitted rate converges to $3/\ell$. The result includes both punctured and transmitted variables and does not condition the sparse square matrix on invertibility. The proof establishes an entropy inequality for six bits subject to even parity by an analytic argument that reduces the domain by symmetry, restricts its interior stationary points, where both partial derivatives vanish, to the diagonal, and controls the resulting scalar functions by explicit polynomial bounds. Exact configuration counts then bound the conditional entropy on the binary symmetric channel. A standard comparison by mutual information extends the entropy bound to general symmetric channels; independent output erasures and a minimum-distance estimate for the transmitted code yield the bit and block error bounds.

0.43

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.47
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

Compression of Sources with Memory and Private Random Access

cs.IT ·2026-11-08 ·Venkat Chandar, Aslan Tchamkerten, Shashank Vatedka
similarity 0.46
Abstract · 22 pages, 2 figures

Private local decoding imposes a stringent constraint on compression: the codeword bits used to recover a source symbol must reveal nothing about the remaining symbols beyond what the recovered symbol itself reveals. For memoryless sources, this constraint is known to be compatible with entropy-rate compression. We show that the same holds for any stationary ergodic source over a finite alphabet. Specifically, every rate above the entropy rate is achievable with exact privacy and error-free local decoding on a set of source sequences whose probability tends to one. In contrast, we exhibit non-ergodic sources for which private local decoding incurs a strictly positive rate penalty.

0.29

Learning Finite-Memory Binary Sources

cs.IT math.PR ·2026-10-29 ·Maciej Skorski
similarity 0.45
Abstract

Estimating biased finite-memory sources from a single trajectory is a fundamental problem with practical impact, for example in estimating entropy for cryptography. We study order-$d$ binary sources whose conditional probabilities have bias at most $ε$, and establish *sharp* sample complexity bounds: relative accuracy $γ$ with confidence $1-δ$ needs $γ^{-2}\,(\tfrac12-ε)^{-d}\,(\log d+\log\tfrac1δ)$ samples up to constants depending on $ε$, with matching upper and lower bounds and no dependence on mixing time or spectral gap. The proof rests on a sharp bound on expected hitting times of the sliding-window (de Bruijn) chain, which stay of order $1/π(w)$ uniformly in $d$ exactly when $ε<\tfrac3{10}$, and on majorization of the window masses by those of independent biased coins. Applied to published entropy-source validations, the bounds show that their trace lengths may be underpowered: $10^6$ bits cannot resolve all transitions of an $8$-bit model to better than about $4.5\%$ relative error.

0.17

A simple proof of the group-theoretic Zhang-Yeung inequality

cs.IT ·2026-09-28 ·Harold Nieuwboer, Lubashan Pathirana
similarity 0.45
Abstract · 7 pages

Zhang and Yeung (IEEE Trans. Inf. Theory, 1998) established the first non-Shannon-type inequality that holds for all entropic vectors. Chan and Yeung (IEEE Trans. Inf. Theory, 2002) showed that there is a one-to-one relation between linear entropy inequalities and multiplicative inequalities involving cardinalities of subgroups of a finite group. The Shannon inequality admits a simple proof in the group theoretic setting, but a direct proof of the translation of Zhang--Yeung's inequality to the group-theoretic setting remained elusive. We resolve this open problem, giving a direct proof of the group-theoretic Zhang--Yeung inequality for cardinalities of subgroups of finite groups, using elementary group-theoretic and counting arguments.

0.18

Continuity of Regularized Channel Rényi Divergences

cs.IT quant-phmath-ph ·2026-09-23 ·Jinzhao Wang, Yuxiang Yang
theorycode/data similarity 0.45
Abstract · 12 pages; comments are welcome; v2: updated references for concurrent works, add a Lean certificate for our proof: https://github.com/JWang2…

We prove that the regularized, stabilized sandwiched Rényi divergence of finite-dimensional quantum channels converges to their regularized relative entropy as the Rényi order tends to one. The key tool is the channel hockey-stick divergence: Gour's Stinespring approximation bound and a Schatten norm estimate amplify an asymptotic bound below one into exponential decay at higher threshold rates. For channel pairs with finite max-relative entropy, known operational connections then give exponential strong converses for parallel and adaptive discrimination, a sharp zero--one testing law, and the subchannel asymptotic equipartition property.

0.49