betaFeedback

WorksComputer Science

Polarization on Bounded Euclidean Spaces and More General Compact Groups

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)O((\log N)^{-1/12}) fraction of the conditional differential entropies in successive cancellation order lie within any fixed positive distance of zero, where NN 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.

Introduction

Given a source string YN=(Y1,…,YN)Y^N = (Y_1,\ldots,Y_N) consisting of nn independent and identically distributed (i.i.d.) source symbols YiY_i taking values in some finite alphabet Y\mathcal{Y}, a polarizing transform is a bijection that maps YNY^N to a sequence UNU^N whose conditional entropies,

H(Ui∣U1,…,Ui−1),H(U_i|U_1,\ldots,U_{i-1}),

approach either 0 or the logarithm of the alphabet size for all but a vanishing fraction of indices as NN grows. Arıkan [1, 2] identified a rich class of polarizing transforms for Bernoulli sources and introduced a linear construction with a recursive structure that admits a low-complexity implementation.

Polarization has since been studied for sources over larger discrete alphabets. The linear transform proposed by Arıkan, with addition defined modulo the alphabet size, has been shown [18] to be polarizing for prime alphabet sizes, and other polarizing transforms have also been identified [15, 17] for non-prime alphabet sizes. Further analysis on the speed of polarization for prime alphabet sizes has shown that the fraction of indices whose conditional entropies remain a fixed distance away from both extreme values decays at least polynomially fast in the block length NN [7].

In the case of continuous sources, the polarization phenomenon remains poorly understood. Distributions over the real numbers do not lend themselves to an unambiguous definition of polarization analogous to the discrete case, as the conditional differential entropies h(Ui∣U1,…,Ui−1)h(U_i|U_1,\ldots,U_{i-1}) are unbounded in both directions; see [3] for a discussion on generalizing the notion of polarization to various continuous settings and the challenges involved.

We study polarization for sources taking values in bounded continuous spaces such as the circle T=R/Z\mathbb{T} = \mathbb{R}/\mathbb{Z}, which we identify with the interval [0,1][0,1]; cf. [3 Example 5]. This is motivated in part by recent work that constructs lossy compression schemes by combining channel simulation [13] with nonlinear transform coding [5], with the channel simulation being performed using polar codes [19]. Nonlinear transform coding and related autoencoding-type architectures are known to struggle with compressing sources with 1-D group structure [6] when the latent variables are real-valued. One potential remedy is to use latent variables that themselves have a 1-D group structure. Doing so would require a channel simulator, say using polar codes, that simulates channels with this structure (cf. [19]).

Our main theoretical result here (Theorem 1 in § 2) establishes polarization for sources taking values in the circle T\mathbb{T} or in more general compact groups. Specifically, we show that under the standard polar transform proposed by Arıkan, the fraction of transformed variables whose conditional differential entropy is bounded away from zero vanishes as the block length NN grows. Thus, most of the indices become nearly uninformative, with most of the information in the source concentrated in the remaining vanishing fraction of variables (cf. [3 Example 5]).

Moreover, we provide an explicit bound on the speed of polarization, showing that the vanishing fraction of informative indices is

O(1(log⁡N)1/12),(1)O\left(\frac{1}{(\log N)^{1/12}}\right), \tag*{(1)}

where, throughout, log⁡\log denotes the natural logarithm and all familiar information-theoretic functionals are expressed in nats. While we certainly do not claim (or believe) that this bound is optimal, empirical evidence discussed in § 1 and § 4 suggests that the actual rate of polarization is indeed extremely slow, being comparable to 1/(log⁡N)1/(\log N).

Our analysis relies on a recent “entropy-jump” inequality for random variables on compact groups [10], which can be viewed as a stability result for an underlying entropy power inequality (EPI). The EPI-polarization connection is described in the following section; see also [9, 14] for related recent entropy lower bounds.

Entropy Inequalities on Compact Groups

For binary random variables, a particularly strong entropy-jump inequality follows from Mrs. Gerber’s lemma [20]. From Şaşoğlu [17, Lemma 2.2]} and Guruswami and Xia [12 (11)-(12)] we have that for i.i.d. X1,X2X_1,X_2 on F2\mathbb{F}_2,

H(X1+X2)−H(X1)≥θ^H(X1)(1−H(X1)log⁡2),(2)H(X_1+X_2)-H(X_1)\geq\widehat{\theta} H(X_1)\left(1-\frac{H(X_1)}{\log2}\right), \tag*{(2)}

with

θ^=inf⁡0<x<1/2h(2x(1−x))−h(x)h(x)(1−h(x))>0.799,(3)\widehat{\theta}=\inf_{0<x<1/2}\frac{h(2x(1-x))-h(x)}{h(x)(1-h(x))}>0.799, \tag*{(3)}

where h(x):=−xlog⁡x−(1−x)log⁡(1−x)h(x):=-x\log x-(1-x)\log(1-x) is the binary entropy function. This quantitative entropy jump is a key ingredient in the latter’s analysis of the speed of polarization. By a bootstrapping method similar to [4], it yields that for n=O(log⁡1ϵ)n=O(\log\frac{1}{\epsilon}),

P(Zn(Wn(I))≤2−βn)≥I(X;Y)−ϵ,(4)\mathbb{P}\left(Z_n(W_n^{(I)})\leq2^{-\beta n}\right)\geq I(X;Y)-\epsilon, \tag*{(4)}

where Zn(Wn(I))Z_n(W_n^{(I)}) is the Bhattacharyya parameter of the II-th sub-channel, I(X;Y)I(X;Y) is the mutual information of the channel, and the probability is over the uniformly selected index II.

Interestingly, the later qq-ary analogue of Guruswami and Velingker [11] yields, for prime qq,

H(X1+X2)−H(X1)≥α(q)H(X1)(1−H(X1)log⁡q),(5)\begin{aligned} H(X_1+X_2)-H(X_1)&\\ &\geq\alpha(q)H(X_1)\left(1-\frac{H(X_1)}{\log q}\right), \tag*{(5)} \end{aligned}

but the quantitative value of α(q)\alpha(q) furnished by their proof is extremely weak. In fact, already for q=2q=2, the quantitative estimate resulting from their general argument is vastly weaker than the sharp binary estimate based on Mrs. Gerber’s lemma. In the present work we use the entropy-jump inequality of [10 Theorem 2.10]. That estimate is significantly weaker but much more general than the entropy jump of the binary case (2). In addition, the related entropy-jump obtained in [10 Theorem 1.4] involves an extremely weak constant, with a value no greater than 3×10−53\times10^{-5}. Although we do not know whether sharper estimates exist, it is worth noting that the actual speed of polarization in the continuous setting seems to be quite slow as we discuss in § 4.

Main Result

Let X\mathcal{X} be a standard Borel space, and let Y\mathcal{Y} be a connected, compact, metrizable abelian topological group, equipped with its Borel σ\sigma-algebra. Let μ\mu denote the normalized Haar measure on Y\mathcal{Y}, so that μ(Y)=1\mu(\mathcal{Y})=1. All familiar information-theoretic functionals are defined in terms of μ\mu. For example, suppose XX takes values in Y\mathcal{Y} and has law PP. If PP has a density f=dPdμf=\frac{dP}{d\mu} with respect to μ\mu, then the (differential) entropy is defined as h(X)=−∫flog⁡f dμh(X)=-\int f\log f\,d\mu; otherwise, we set h(X)=−∞h(X)=-\infty. In particular, the uniform distribution on Y\mathcal{Y} has zero entropy and all entropies are nonpositive.

Let PXYP_{XY} be a joint distribution on X×Y\mathcal{X}\times\mathcal{Y}. We will refer to the corresponding marginal PXP_X as the source distribution and the induced kernel PY∣XP_{Y|X} as the channel. For any such joint distribution, we will assume throughout that the mutual information I(X;Y)I(X;Y) associated with the channel is finite and in fact that

−∞<h(Y∣X)≤0.(6)-\infty<h(Y|X)\leq0. \tag*{(6)}

Given N=2nN=2^n i.i.d. pairs (XN,YN)∼PXY⊗N(X^N,Y^N)\sim P_{XY}^{\otimes N}, we define the polar domain representation [2] as

UN=YNBN[1011]⊗n,(7)U^N=Y^N B_N\begin{bmatrix}1&0\\1&1\end{bmatrix}^{\otimes n}, \tag*{(7)}

where BNB_N is the bit-reversal permutation. Our main contribution is the following finite-nn result.

Theorem 1. For all n>1n>1 and 0<ϵ<min⁡{−h(Y∣X),18}0<\epsilon<\min\{-h(Y|X),\frac{1}{8}\},

∣{i:−h(Ui∣Ui−1,XN)≥ϵ}∣2n≤4(−h(Y∣X))1/6(nϵ10)1/12.(8)\frac{\left|\{i:-h(U_i|U^{i-1},X^N)\geq\epsilon\}\right|}{2^n}\leq\frac{4(-h(Y|X))^{1/6}}{(n\epsilon^{10})^{1/12}}. \tag*{(8)}

where N=2nN=2^n.

Proof

We begin by examining a single recursive step of the polar transform.

Definition 2 (Pairwise polarizing transform). Let Z1Z_1 and Z2Z_2 be independent random variables with distribution PZP_Z on some standard Borel space Z\mathcal{Z}. Given an arbitrary channel W:Z→YW:\mathcal{Z}\to\mathcal{Y} and conditionally independent channel outputs Y1∼W(⋅∣Z1)Y_1\sim W(\cdot|Z_1) and Y2∼W(⋅∣Z2)Y_2\sim W(\cdot|Z_2), define their polar domain representations

U1=Y1+Y2,(9)U_1=Y_1+Y_2, \tag*{(9)}
U2=Y2.(10)U_2=Y_2. \tag*{(10)}

For an arbitrary measurable subset AA of Y\mathcal{Y}, define the transformed channels

W0(U1∈A∣z1,z2)=Pr⁡(Y1+Y2∈A∣Z1=z1,Z2=z2),(11)\begin{aligned} W_0(U_1\in A|z_1,z_2) &=\Pr(Y_1+Y_2\in A|Z_1=z_1,Z_2=z_2), \tag*{(11)} \end{aligned}

and

W1(U2∈A∣z1,z2,u1)=Pr⁡(Y2∈A∣Z1=z1,Z2=z2,U1=u1).(12)\begin{aligned} W_1(U_2\in A|z_1,z_2,u_1) &=\Pr(Y_2\in A|Z_1=z_1,Z_2=z_2,U_1=u_1). \tag*{(12)} \end{aligned}

We will denote this transform by

(W0,W1)←W.(13)(W_0,W_1)\leftarrow W. \tag*{(13)}

For a channel W^\widehat{W} together with its induced input-output pair (Z^,Y^)(\widehat{Z},\widehat{Y}), we use the abbreviation

h(W^)=h(Y^∣Z^).(14)h(\widehat{W})=h(\widehat{Y}|\widehat{Z}). \tag*{(14)}

In particular,

h(W)=h(Y1∣Z1)=h(Y2∣Z2),(15)h(W)=h(Y_1|Z_1)=h(Y_2|Z_2), \tag*{(15)}
h(W0)=h(U1∣Z1,Z2)=h(Y1+Y2∣Z1,Z2),(16)h(W_0)=h(U_1|Z_1,Z_2)=h(Y_1+Y_2|Z_1,Z_2), \tag*{(16)}
h(W1)=h(U2∣Z1,Z2,U1)=h(Y2∣Z1,Z2,Y1+Y2).(17)h(W_1)=h(U_2|Z_1,Z_2,U_1)=h(Y_2|Z_1,Z_2,Y_1+Y_2). \tag*{(17)}

We further write

h(W^∣z)=h(Y^∣Z^=z)(18)h(\widehat{W}|z)=h(\widehat{Y}|\widehat{Z}=z) \tag*{(18)}

for the pointwise output entropy corresponding to the input Z^=z\widehat{Z}=z.

Starting from the channel PY∣XP_{Y|X}, we define a binary tree in the usual fashion:

W=PY∣X,(19)W=P_{Y|X}, \tag*{(19)}
(W0,W1)←W,(20)(W_0,W_1)\leftarrow W, \tag*{(20)}
(Wb1,…,bK,0,Wb1,…,bK,1)←Wb1,…,bK,(21)(W_{b_1,\ldots,b_K,0},W_{b_1,\ldots,b_K,1})\leftarrow W_{b_1,\ldots,b_K}, \tag*{(21)}

where K≥1K\ge1 and each bi∈{0,1}b_i\in\{0,1\}. We then draw i.i.d. uniform Bernoulli samples B1,B2,…B_1,B_2,\ldots to construct a random walk on the tree, with respect to which we can define the stochastic process

I0=−h(W),(22)I_0=-h(W), \tag*{(22)}
IK=−h(WBK),K≥1.(23)I_K=-h(W_{B^K}),\quad K\ge1. \tag*{(23)}

We can express our objective in terms of IkI_k:

Pr⁡(In≥ϵ)=∣{i:−h(Ui∣U1i−1,Xn)≥ϵ}∣2n.(24)\Pr(I_n\ge\epsilon)=\frac{\left|\left\{i:-h(U_i|U_1^{i-1},X^n)\ge\epsilon\right\}\right|}{2^n}. \tag*{(24)}

Lemma 3. The process (Ik)k≥0(I_k)_{k\ge0} is a martingale that converges almost surely.

Proof. The martingale property of IkI_k follows from the fact that every pairwise polarizing transform is a entropy-preserving transform. Since the uniform distribution over Y\mathcal{Y} is the maximum entropy distribution, it follows that Ik≥0I_k\ge0. Convergence then follows from Doob’s supermartingale convergence theorem.

We consider the case where

nϵ10>(4I01/6)12,(25)n\epsilon^{10}>(4I_0^{1/6})^{12}, \tag*{(25)}

since the bound in (8) holds trivially otherwise. We begin by defining two thresholds MM and ϵ~\widetilde{\epsilon},

M=(1010I0nϵ102312)1/12,(26)M=\left(\frac{10^{10}I_0n\epsilon^{10}}{2312}\right)^{1/12}, \tag*{(26)}
ϵ~=(231200I02ϵ2n)1/12.(27)\widetilde{\epsilon}=\left(\frac{231200I_0^2\epsilon^2}{n}\right)^{1/12}. \tag*{(27)}

The condition from (25) ensures that

M>I0andϵ~<ϵ.(28)M>I_0\quad\text{and}\quad\widetilde{\epsilon}<\epsilon. \tag*{(28)}

We also define the stopping times

τ=inf⁡{K:IK≤ϵ~ or IK>M},(29)\tau=\inf\{K:I_K\le\widetilde{\epsilon}\text{ or }I_K>M\}, \tag*{(29)}
σ=inf⁡{K:IK>M},(30)\sigma=\inf\{K:I_K>M\}, \tag*{(30)}
ω=inf⁡{K:IK≤ϵ~}.(31)\omega=\inf\{K:I_K\le\widetilde{\epsilon}\}. \tag*{(31)}

and the stopped martingales JK=IK∧τJ_K=I_{K\wedge\tau} and θK=IK∧σ\theta_K=I_{K\wedge\sigma}. We then have

Pr⁡(In≥ϵ)≤Pr⁡(In≥ϵ,σ>n)+Pr⁡(σ≤n)≤Pr⁡(In≥ϵ,σ>n,τ<n)+Pr⁡(τ≥n)+Pr⁡(σ≤n)≤Pr⁡(In1{ω<n}≥ϵ)+Pr⁡(τ≥n)+Pr⁡(σ≤n).(32)\begin{aligned} \Pr(I_n\ge\epsilon) &\le\Pr(I_n\ge\epsilon,\sigma>n)+\Pr(\sigma\le n)\\ &\le\Pr(I_n\ge\epsilon,\sigma>n,\tau<n)+\Pr(\tau\ge n)+\Pr(\sigma\le n)\\ &\le\Pr(I_n\mathbb{1}_{\{\omega<n\}}\ge\epsilon)+\Pr(\tau\ge n)+\Pr(\sigma\le n). \tag*{(32)} \end{aligned}

Next, we derive upper bounds for each of the quantities in (32).

a) Upper bound on Pr⁡(τ≥n)\Pr(\tau\ge n): For all K>1K>1, using the orthogonality of martingale increments,

E[JK+12]≥E[∑i=0K(Ji+1−Ji)2]=E[∑i=0K∧(τ−1)(Ii+1−Ii)2].(33)\begin{aligned} E[J_{K+1}^2]&\ge E\left[\sum_{i=0}^{K}(J_{i+1}-J_i)^2\right]\\ &=E\left[\sum_{i=0}^{K\wedge(\tau-1)}(I_{i+1}-I_i)^2\right]. \tag*{(33)} \end{aligned}

The lower bound from Lemma 5 below gives

E[K∧τ]≤1156E[I(K+1)∧τ2]ϵ~10.(34)E[K\wedge\tau]\le\frac{1156E\left[I_{(K+1)\wedge\tau}^2\right]}{\widetilde{\epsilon}^{10}}. \tag*{(34)}

From the definition of the stopping time, it follows that I(K+1)∧τ≤2MI_{(K+1)\wedge\tau}\le2M. Therefore,

E[I(K+1)∧τ2]≤2ME[∣I(K+1)∧τ∣]=2MI0,(35)E\left[I_{(K+1)\wedge\tau}^2\right]\le2ME\left[|I_{(K+1)\wedge\tau}|\right]=2MI_0, \tag*{(35)}

and hence,

E[K∧τ]≤2312MI0ϵ~10.(36)E[K\wedge\tau]\le\frac{2312MI_0}{\widetilde{\epsilon}^{10}}. \tag*{(36)}

Now, observe that

Pr⁡(τ≥K)=Pr⁡(τ∧K=K)≤Pr⁡(τ∧K≥K).(37)\Pr(\tau\ge K)=\Pr(\tau\wedge K=K)\le\Pr(\tau\wedge K\ge K). \tag*{(37)}

Applying Markov’s inequality with K=nK=n, we obtain

Pr⁡(τ≥n)≤E[τ∧n]n≤2312MI0nϵ~10,(38)\Pr(\tau\ge n)\le\frac{E[\tau\wedge n]}{n}\le\frac{2312MI_0}{n\widetilde{\epsilon}^{10}}, \tag*{(38)}

where the second step follows from (36).

b) Upper bound on Pr⁡(σ≤n)\Pr(\sigma\le n): For all KK, we have

θK≥M1{σ≤K}.(39)\theta_K\ge M\mathbb{1}_{\{\sigma\le K\}}. \tag*{(39)}

Taking expectations and rearranging, we obtain

Pr⁡(σ≤K)≤E[θK]M=I0M,(40)\Pr(\sigma\le K)\le\frac{E[\theta_K]}{M}=\frac{I_0}{M}, \tag*{(40)}

for all KK, and hence,

Pr⁡(σ≤n)≤I0M.(41)\Pr(\sigma\le n)\le\frac{I_0}{M}. \tag*{(41)}

Upper bound on Pr⁡(In1{ω<n}≥ϵ)\Pr(I_n\mathbb{1}\{\omega<n\}\ge\epsilon)

Markov’s inequality gives

Pr⁡(In1{ω<n}≥ϵ)≤E[In1{ω<n}]ϵ.(42)\Pr(I_n\mathbb{1}\{\omega<n\}\ge\epsilon)\le\frac{E[I_n\mathbb{1}\{\omega<n\}]}{\epsilon}. \tag*{(42)}

Since we have that E[IK−IK∧ω]=0E[I_K-I_{K\wedge\omega}]=0 for all KK, it follows that E[In−In∧ω]=0E[I_n-I_{n\wedge\omega}]=0, which in turn implies that E[(In−In∧ω)1{ω<n}]=0E[(I_n-I_{n\wedge\omega})\mathbb{1}\{\omega<n\}]=0, and therefore,

E[In1{ω<n}]=E[In∧ω1{ω<n}]≤ϵ~.(43)E[I_n\mathbb{1}\{\omega<n\}]=E[I_{n\wedge\omega}\mathbb{1}\{\omega<n\}]\le\tilde{\epsilon}. \tag*{(43)}

Substituting this in (42), we obtain

Pr⁡(In1{ω<n}≥ϵ)≤ϵ~ϵ.(44)\Pr(I_n\mathbb{1}\{\omega<n\}\ge\epsilon)\le\frac{\tilde{\epsilon}}{\epsilon}. \tag*{(44)}

Using the above upper bounds in (32), gives

Pr⁡(In≥ϵ)≤2312MI0nϵ~10+I0M+ϵ~ϵ.(45)\Pr(I_n\ge\epsilon)\le\frac{2312MI_0}{n\tilde{\epsilon}^{10}}+\frac{I_0}{M}+\frac{\tilde{\epsilon}}{\epsilon}. \tag*{(45)}

And substituting the definitions from (26) and (27) yields

Pr⁡(In≥ϵ)≤4I01/6⋅(nϵ10)−1/12,(46)\Pr(I_n\ge\epsilon)\le4I_0^{1/6}\cdot(n\epsilon^{10})^{-1/12}, \tag*{(46)}

completing the proof of the theorem. □

Remark 4. The results of Lemma 3 and Theorem 1 imply that the martingale (Ik)k≥0(I_k)_{k\ge0} converges to 0 almost surely:

I∞:=lim⁡n→∞In=0a.s.(47)I_\infty:=\lim_{n\to\infty}I_n=0\quad\text{a.s.} \tag*{(47)}

On the other hand, whenever I0>0I_0>0,

lim⁡n→∞E[∣In−I∞∣]=lim⁡n→∞E[In]=I0,(48)\lim_{n\to\infty}E[|I_n-I_\infty|]=\lim_{n\to\infty}E[I_n]=I_0, \tag*{(48)}

therefore (Ik)k≥0(I_k)_{k\ge0} is not uniformly integrable and does not converge in L1L_1. See the discussion and conjecture in [3 Example 5].

Lemma 5. Given 0<ϵ<180<\epsilon<\frac{1}{8}, let bK∈{0,1}Kb^K\in\{0,1\}^K be a binary string such that

−h(WbK)≥ϵ.(49)-h(W_{b^K})\ge\epsilon. \tag*{(49)}

Then, the transformed channels

(WbK,0,WbK,1)←WbK,(50)(W_{b^K,0},W_{b^K,1})\leftarrow W_{b^K}, \tag*{(50)}

satisfy

h(WbK,0)−h(WbK)=h(WbK)−h(WbK,1)≥ϵ534.(51)h(W_{b^K,0})-h(W_{b^K})=h(W_{b^K})-h(W_{b^K,1})\ge\frac{\epsilon^5}{34}. \tag*{(51)}

Proof. For almost surely-any pair of inputs z1z_1 and z2z_2 to the channels WbKW_{b^K}, applying the entropy-jump inequality in [10 Theorem 2.10] yields

h(WbK,0∣z1,z2)−h(WbK∣z2)+h(WbK∣z1)2≥max⁡{f(h(WbK∣z1)),f(h(WbK∣z2))},(52)h(W_{b^K,0}\mid z_1,z_2)-\frac{h(W_{b^K}\mid z_2)+h(W_{b^K}\mid z_1)}{2}\ge\max\{f(h(W_{b^K}\mid z_1)),f(h(W_{b^K}\mid z_2))\}, \tag*{(52)}

where

f(x)={−x5−4x616+8x4,−18≤x≤0,f(−18),x<−18.(53)f(x)= \begin{cases} \dfrac{-x^5-4x^6}{16+8x^4}, & -\dfrac{1}{8}\le x\le0,\\ f\left(-\dfrac{1}{8}\right), & x<-\dfrac{1}{8}. \end{cases} \tag*{(53)}

Averaging over independent realizations of z1z_1 and z2z_2 and observing that, for −18≤x≤0-\frac{1}{8}\le x\le0,

−x5−4x616+8x4≥−x5(1+4x)16+12≥−x533,(54)\frac{-x^5-4x^6}{16+8x^4}\ge\frac{-x^5(1+4x)}{16+\frac{1}{2}}\ge-\frac{x^5}{33}, \tag*{(54)}

we obtain, using Jensen’s inequality,

h(WbK,0)−h(WbK)≥EZ1[min⁡{−h(WbK∣Z1)533,(1/8)533}]≥(EZ1[min⁡{−h(WbK∣Z1),18}])533.(55)\begin{aligned} h(W_{b^K,0})-h(W_{b^K})\ge E_{Z_1}\left[\min\left\{\frac{-h(W_{b^K}\mid Z_1)^5}{33},\frac{(1/8)^5}{33}\right\}\right] \\ &\ge\frac{\left(E_{Z_1}\left[\min\left\{-h(W_{b^K}\mid Z_1),\frac{1}{8}\right\}\right]\right)^5}{33}. \tag*{(55)} \end{aligned}

Now, we can further bound,

EZ1[min⁡{−h(WbK∣Z1),18}]=EZ1[max⁡{−h(WbK∣Z1),18}−∣h(WbK∣Z1)+18∣]≥max⁡{−h(WbK),18}−EZ1[∣h(WbK∣Z1)+18−h(WbK)+h(WbK)∣]≥max⁡{−h(WbK),18}−∣18+h(WbK)∣−EZ1[∣h(WbK∣Z1)−h(WbK)∣]=min⁡{−h(WbK),18}−EZ1[∣h(WbK∣Z1)−h(WbK)∣]≥ϵ−EZ1[∣h(WbK∣Z1)−h(WbK)∣]≥ϵ−EZ1,Z2[∣h(WbK∣Z1)−h(WbK∣Z2)∣]=ϵ−2EZ1,Z2[max⁡{h(WbK∣Z1),h(WbK∣Z2)}−h(WbK∣Z1)+h(WbK∣Z2)2].(56)\begin{aligned} E_{Z_1}\left[\min\left\{-h(W_{b^K}\mid Z_1),\frac{1}{8}\right\}\right] =E_{Z_1}\left[\max\left\{-h(W_{b^K}\mid Z_1),\frac{1}{8}\right\}-\left|h(W_{b^K}\mid Z_1)+\frac{1}{8}\right|\right] \\ &\ge\max\left\{-h(W_{b^K}),\frac{1}{8}\right\}-E_{Z_1}\left[\left|h(W_{b^K}\mid Z_1)+\frac{1}{8}-h(W_{b^K})+h(W_{b^K})\right|\right] \\ &\ge\max\left\{-h(W_{b^K}),\frac{1}{8}\right\}-\left|\frac{1}{8}+h(W_{b^K})\right|-E_{Z_1}[|h(W_{b^K}\mid Z_1)-h(W_{b^K})|] \\ &=\min\left\{-h(W_{b^K}),\frac{1}{8}\right\}-E_{Z_1}[|h(W_{b^K}\mid Z_1)-h(W_{b^K})|] \\ &\ge\epsilon-E_{Z_1}[|h(W_{b^K}\mid Z_1)-h(W_{b^K})|] \\ &\ge\epsilon-E_{Z_1,Z_2}[|h(W_{b^K}\mid Z_1)-h(W_{b^K}\mid Z_2)|] \\ &=\epsilon-2E_{Z_1,Z_2}\left[\max\{h(W_{b^K}\mid Z_1),h(W_{b^K}\mid Z_2)\}-\frac{h(W_{b^K}\mid Z_1)+h(W_{b^K}\mid Z_2)}{2}\right]. \tag*{(56)} \end{aligned}

From Jensen’s inequality we have that the entropy jump is nonnegative:

max⁡{h(WbK∣Z1),h(WbK∣Z2)}≤h(WbK,0∣Z1,Z2).(57)\max\{h(W_{b^K}\mid Z_1),h(W_{b^K}\mid Z_2)\}\le h(W_{b^K,0}\mid Z_1,Z_2). \tag*{(57)}

Using this and the identity

E[h(WbK∣Z1)]=E[h(WbK∣Z2)],(58)E[h(W_{b^K}\mid Z_1)]=E[h(W_{b^K}\mid Z_2)], \tag*{(58)}

gives

EZ1[min⁡{−h(WbK∣Z1),18}]≥ϵ−2(h(WbK,0)−h(WbK)).(59)E_{Z_1}\left[\min\left\{-h(W_{b^K}\mid Z_1),\frac{1}{8}\right\}\right]\ge\epsilon-2\left(h(W_{b^K,0})-h(W_{b^K})\right). \tag*{(59)}

Substituting (59) in (55), we obtain

h(WbK,0)−h(WbK)≥(ϵ−2(h(WbK,0)−h(WbK)))+533.(60)h(W_{b^K,0})-h(W_{b^K})\ge\frac{\left(\epsilon-2\left(h(W_{b^K,0})-h(W_{b^K})\right)\right)_+^5}{33}. \tag*{(60)}

The function t↦(t)+5t \mapsto(t)_+^5 is convex on the whole real line. Its supporting-line inequality at t=ϵt = \epsilon therefore gives

(ϵ−2(h(WbK,0)−h(WbK)))+5≥ϵ5−10ϵ4(h(WbK,0)−h(WbK)).(61)\left(\epsilon- 2\left(h(W_{b_K,0}) - h(W_{b_K})\right)\right)_+^5 \ge\epsilon^5 - 10\epsilon^4\left(h(W_{b_K,0}) - h(W_{b_K})\right). \tag*{(61)}

Rearranging terms,

h(WbK,0)−h(WbK)≥ϵ533+10ϵ4≥ϵ5345,(62)h(W_{b_K,0}) - h(W_{b_K}) \ge\frac{\epsilon^5}{33 + 10\epsilon^4} \ge\frac{\epsilon^5}{34^5}, \tag*{(62)}

which is the required result. □

Examples

Given a uniform source X∼Unif⁡[0,1]X \sim\operatorname{Unif}[0,1] on the circle T\mathbb{T} identified as the interval [0,1][0,1] with modulo-1 addition, consider the additive cosine channel

Y=X+Z(mod1),(63)Y = X + Z \pmod1, \tag*{(63)}

where the noise ZZ is independent of XX and has density

pZ(θ)=1+αcos⁡(2πθ),(64)p_Z(\theta) = 1 + \alpha\cos(2\pi\theta), \tag*{(64)}

for some ∣α∣≤1|\alpha| \le1. Under the polar transform in (7) applied to NN independent copies of XX and YY, we compute the subchannel densities using their Fourier parameterization [8] as

P(Ui∣U1i−1,XN)=1+2ℜ(∑k=1Nck(XN,U1i−1)exp⁡(j2πkUi)).(65)P(U_i \mid U_1^{i-1}, X^N) = 1 + 2\Re\left(\sum_{k=1}^{N} c_k(X^N,U_1^{i-1})\exp(j2\pi kU_i)\right). \tag*{(65)}

This representation includes the original channel density and is preserved under every recursive update in (9)-(10).

For several values of NN and α=0.98\alpha= 0.98, Figure 1 shows Monte Carlo estimates of the subchannel mutual informations

Image not extracted

Figure 1. Mutual information per subchannel, as defined in (66), for the example in § 4. For any ϵ>0\epsilon> 0, the fraction of subchannels for which the mutual information exceeds ϵ\epsilon tends to zero slowly with NN. The dotted line shows the mutual information of the unpolarized channel in (63). Note that the mutual information of the best subchannel increases without bound.

MI⁡i=h(Ui)−h(Ui∣U1i−1,XN)=−h(Ui∣U1i−1,XN).(66)\operatorname{MI}_i = h(U_i)-h(U_i \mid U_1^{i-1},X^N) = -h(U_i \mid U_1^{i-1},X^N). \tag*{(66)}

Each estimate is averaged over 100 independent trials, and the NN subchannels are ordered by their estimated mutual information. Figure 2 plots the fraction of the unpolarized channels, defined here as the fraction of indices ii for which MI⁡i>0.05\operatorname{MI}_i > 0.05 nats, for increasing values of NN. The upper bound on the polarization rate from Theorem 1 is vacuous for the small values of NN considered here and is thus omitted from the plot. The reference curve in the figure suggests that the actual rate of polarization in this example is closer to 1log⁡N\frac{1}{\log N}.

Image not extracted

Figure 2. The fraction of subchannels whose mutual information exceeds ϵ=0.05\epsilon= 0.05 nats plotted against the function 1/ln⁡N1/\ln N.

It is easy to see that the rate of polarization can be no faster than 1/log⁡N1/\log N in the worst case. Suppose X=0X = 0 and YY is uniformly distributed over [0,1/2][0,1/2]. Then for i<Ni < N, the component with the smallest conditional entropy, UNU_N, has a conditional distribution given UiU_i that is uniformly distributed over an interval of approximate width 1/N1/N with high probability. Thus we have

−h(UN∣U1,…,UN−1)=Θ(log⁡N),(67)-h(U_N \mid U_1,\ldots,U_{N-1}) = \Theta(\log N), \tag*{(67)}

and

−h(Ui∣U1,…,Ui−1)=O(log⁡N)for all i.-h(U_i \mid U_1,\ldots,U_{i-1}) = O(\log N) \quad\text{for all } i.

Since the average conditional entropy satisfies

1N∑i=1Nh(Ui∣U1,…,Ui−1)=−log⁡2(68)\frac{1}{N}\sum_{i=1}^{N} h(U_i \mid U_1,\ldots,U_{i-1}) = -\log2 \tag*{(68)}

it follows a fraction Ω(1/log⁡N)\Omega(1/\log N) of the subchannels must have entropy bounded away from zero.

Thus one cannot hope to achieve fast polarization in general using Arıkan’s polar transform. Whether the polarization can be accelerated using other transforms, at least in examples of interest in applications, is a subject of ongoing work.

AI Statement

OpenAI’s ChatGPT 6.0 [16] was used to assist with editing the manuscript, exploring proof techniques, and developing the code for the simulations in § 4. In particular, the argument for the lower bound in equations (56)–(59) was suggested by ChatGPT. The authors take full responsibility for the contents in this manuscript.

References

  1. [1]Erdal Arıkan. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 55(7):3051–3073, 2009.DOI
  2. [2]Erdal Arıkan. Source polarization. In 2010 IEEE International Symposium on Information Theory, pages 899–903. IEEE, 2010.DOI
  3. [3]Erdal Arıkan. Entropy polarization in butterfly transforms. Digital Signal Processing, 119:103207, 2021.DOI
  4. [4]Erdal Arıkan and Emre Telatar. On the rate of channel polarization. In 2009 IEEE International Symposium on Information Theory, pages 1493–1495. IEEE, 2009.
  5. [5]Jona Ballé, Philip A Chou, David Minnen, Saurabh Singh, Nick Johnston, Eirikur Agustsson, Sung Jin Hwang, and George Toderici. Universal transform coding. IEEE Journal of Selected Topics in Signal Processing, 15(2):339–353, 2020.
  6. [6]Sourbh Bhadane, Aaron B. Wagner, and Jona Ballé. Do neural networks compress manifolds optimally? In 2022 IEEE Information Theory Workshop (ITW), pages 582–587, 2022.arxiv.org/abs/2205.08518
  7. [7]Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan. General strong polarization. ACM Journal of the ACM (JACM), 69(2):1–67, 2022.
  8. [8]Alfredo De la Fuente, Saurabh Singh, and Jona Ballé. Fourier basis density model. In 2024 Picture Coding Symposium (PCS), pages 1–5. IEEE, 2024.
  9. [9]Lampros Gavalakis, Marcel K. Goh, and Ioannis Kontoyiannis. Entropy lower bounds and sum-product phenomena. arXiv e-prints, 2604.02333 [math.CO], April 2026.
  10. [10]Lampros Gavalakis, Ioannis Kontoyiannis, Sharang M. Sriramu, and Aaron Wagner. Entropy power inequalities in compact groups. arXiv preprint arXiv:2608.22534, 2026.arxiv.org/abs/2608.22534
  11. [11]Venkatesan Guruswami and Ameya Velingker. An entropy sunset inequality and polynomially fast convergence to shannon capacity over all alphabets. In 30th Conference on Computational Complexity (CCC 2015), volume 33 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42–57. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015.
  12. [12]Venkatesan Guruswami and Patrick Xia. Polar codes: Speed of polarization and polynomial gap to capacity. IEEE Transactions on Information Theory, 61(1):3–16, January 2015.
  13. [13]Cheuk Ting Li. Channel simulation: Theory and applications to lossy compression and differential privacy. Foundations and Trends® in Communications and Information Theory, 21(6):847–1106, 2024.DOI
  14. [14]Rupert Li, Lampros Gavalakis, and Ioannis Kontoyiannis. Entropic additive energy and entropy inequalities for sums and products. IEEE Transactions on Information Theory, 72(3):1553–1568, March 2026.
  15. [15]Ryuhei Mori and Toshiyuki Tanaka. Source and channel polarization over finite fields and reed–solomon matrices. IEEE Transactions on Information Theory, 60(5):2720–2736, 2014.
  16. [16]OpenAI. ChatGPT. https://chatgpt.com/, 2026.
  17. [17]Eren Şaşoğlu. Polarization and polar codes. Foundations and Trends in Communications and Information Theory, 8(4):259–381, 2012.DOI
  18. [18]Eren Şaşoğlu, Emre Telatar, and Erdal Arıkan. Polarization for arbitrary discrete memoryless channels. In 2009 IEEE Information Theory Workshop, pages 144–148. IEEE, 2009.arxiv.org/abs/0908.0302
  19. [19]Sharang M. Sriramu, Rochelle Barsz, Elizabeth Polito, and Aaron B. Wagner. Fast channel simulation via error-correcting codes. Advances in Neural Information Processing Systems, 37:107932–107959, 2024.DOI
  20. [20]Aaron D. Wyner and Jacob Ziv. A theorem on the entropy of certain binary sequences and applications: Part I. IEEE Transactions on Information Theory, 19(6):769–772, November 1973.DOI

Paper details

vlnc:W_mwrdqkkg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT 6.0

View statement
Looking for related papers…
Contents