Consider a distribution $\mathcal D$ over the reals, a real parameter $H\in\mathbb R^+$, and an integer parameter $k\in\mathbb N$. The Entropy-Constrained Quantization problem asks what is the best set of quantization levels $Q\subset \mathbb R$, with $|Q|\le k$, that minimizes the expected squared distance to the closest level, under an entropy constraint $H$.

That is, if for all $q\in Q$ we denote the probability mass closest to it by $p_q$, then the entropy of the quantization levels set $H_Q=-\sum_{q\in Q}p_q\log_2 p_q$ must satisfy $H_Q\le H$, and the goal is to find $$ \arg\min_{|Q|\le k\\H_Q\le H} \mathbb E_{X\sim \mathcal D}[\min\{(X-q)^2\mid q\in Q\}]. $$

The motivation comes from encoding long vectors whose entries are i.i.d. from $\mathcal D$ and compressing them before sending (or storing) them. The above paper gives an algorithm for approximating the optimal quantization level set.

For example, if $\mathcal D=\mathcal N(0,1)$ is the normal distribution and $k=2, H= 1$, the optimal solution is $Q=\{-\sqrt{2/\pi},\sqrt{2/\pi}\}$ (as the mean of the half normal distribution is $\sqrt{2/\pi}$).

The expected squared error, in this case, is the variance of the half-normal, i.e.,

$$ \min_{|Q|\le 2\\H_Q\le 1} \mathbb E_{X\sim \mathcal N(0,1)}[\min\{(X-q)^2\mid q\in Q\}] = \mathbb E_{X\sim \mathcal N(0,1)}\left[\min\left\{(X-q)^2\mid q\in \left\{-\sqrt{2/\pi},\sqrt{2/\pi}\right\}\right\}\right] = 1-2/\pi . $$

I am interested in distributions that are not "well compressible".

Specifically, suppose that we know that $\mathcal D$ has a variance of $1$.

What is $\arg\max_{\mathcal D\in\Delta(\mathbb R)}\min_{|Q|\le k\\H_Q\le H} \mathbb E_{X\sim\mathcal D}[\min\{(X-q)^2\mid q\in Q\}]$ as a function of $k$ and $H$?

If it makes things simpler, we can remove the cardinality constraint (and the parameter $k$).

Alternatively, assume that we have $k=2, H=1$. What would be the least compressible distribution with two quantization levels (and no non-trivial entropy constraint)?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.