This is a cross-post from cstheory after a week with no answers/comments; I'm hoping someone here may have some thoughts.
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)?
