Time-average code-length conjecture for zero-delay LQG quantizer coding

About 19 years old · traced to

Let gg be a bijection as described in the cited power-law or exponential-envelope theorem. At time t\mathsf{t}, the lossless encoder computes

q‾t=g(\MakeLowercaseqt)\overline{\boldsymbol{\mathbf{\mathsf{q}}}}_{\mathsf{t}}=g({\boldsymbol{\mathbf{\MakeLowercase{q}}}}_{\mathsf{t}})

and encodes it using

\MakeLowercaseat=Ct,q‾t−1(q‾t),{\boldsymbol{\mathbf{\MakeLowercase{a}}}}_{\mathsf{t}}=C_{\mathsf{t},\overline{{\boldsymbol{\mathbf{\mathsf{{q}}}}}}^{\mathsf{t}-1}}(\overline{{\boldsymbol{\mathbf{\mathsf{{q}}}}}}_{\mathsf{t}}),

where the encoding function is constructed via the cited exponential-envelope scheme when m≤2\mathsf{m}\leq 2, or via the cited scheme with the zero-delay modification using Shannon–Fano–Elias coding otherwise. The encoding is prefix-free, depends at time t\mathsf{t} only on the previous transformed outputs, and the decoder reconstructs the quantizer output exactly.

Time-average code-length conjecture. The time-average expected codeword lengths should satisfy

lim⁡T→∞1T∑i=0T−1E[ℓ(MakeLowercaseat)]=H(MakeLowercaseq)+2.\lim_{\mathsf{T}\rightarrow\infty}\frac{1}{\mathsf{T}}\sum_{\mathsf{i}=0}^{\mathsf{T}-1}\mathbb{E}[\ell({\boldsymbol{\mathbf{MakeLowercase{a}}}}_{\mathsf{t}})]=H({\boldsymbol{\mathbf{MakeLowercase{q}}}})+2.

This would extend stationary-source coding guarantees to the asymptotically stationary quantizer outputs while preserving the LQG control-performance constraint. The source explicitly says that proving or disproving the conjecture is future work, so it remains open.

References

Primary source

Travis C. Cuvelier, Takashi Tanaka and Robert W. Heath, “Online variable-length source coding for minimum bitrate LQG control”, arXiv:2304.00593 (2023).

Additional references

2 papers in this index state this conjecture (2007–2023). The statement above is taken from the most recent of them; the others are arXiv:0711.4835.

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.