Information-distillation lower-bound tightness conjecture

Let X\mathcal{X} be a finite alphabet with X>2|\mathcal{X}|>2. For an information-distillation function IDM(X,β)\mathrm{ID}_M(|\mathcal{X}|,\beta), where MM is the number of quantization levels and β\beta is the mutual-information scale, the conjecture concerns maintaining a fraction η(X)\eta(|\mathcal{X}|) of that scale as β\beta tends to zero. Information-distillation lower-bound tightness conjecture. For any X>2|\mathcal{X}|>2, there exist η(X)\eta(|\mathcal{X}|), β(X)>0\beta(|\mathcal{X}|)>0, and c(X)>0c(|\mathcal{X}|)>0 such that

X2X1<η(X)<1,\frac{|\mathcal{X}|-2}{|\mathcal{X}|-1}<\eta(|\mathcal{X}|)<1,

and, for all 0<β<β(X)0<\beta<\beta(|\mathcal{X}|) and M<c(X)(log(1/β))X1M<c(|\mathcal{X}|)(\log(1/\beta))^{|\mathcal{X}|-1},

IDM(X,β)<η(X)β.\mathrm{ID}_M(|\mathcal{X}|,\beta)<\eta(|\mathcal{X}|)\cdot\beta.

The preceding bounds establish tight quantization-level growth for fractions below 1/(X1)1/(|\mathcal{X}|-1), while the conjecture would extend a matching lower-bound characterization to a fraction strictly larger than (X2)/(X1)(|\mathcal{X}|-2)/(|\mathcal{X}|-1) and arbitrarily close to 11. The statement remains unproved in the source.

Sources & referencesView supporting material

Primary source

Alankrita Bhatt, Bobak Nazer, Or Ordentlich and Yury Polyanskiy, “Information-Distilling Quantizers”, arXiv:1812.03031 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.