Optimal quantization of histogram

Question

I have a histogram of occurrences, as a list of counts (non-negative integers). For the purposes of a compression algorithm (specifically arithmetic coding) I must quantize these occurrences into a histogram whose entries sum to $2^n-1$.

To maintain sanity, I require some properties of the quantization algorithm:

1. Any element with 0 occurrences must have 0 occurrences after quantization.
2. Any element with > 0 occurrences must have > 0 occurrences after quantization.
3. The sum of the quantized histogram must add up to $2^n-1$.

To guarantee that there is a satisfiable solution there will be no more than $2^n-1$ elements.

Given those constraints the values of the quantized histogram $Q$ must proportionally be as close as possible as the values of the original histogram $H$.

Or more formally:
$$\forall i: H_i > 0 \rightarrow Q_i > 0$$ $$\forall i: H_i = 0 \rightarrow Q_i = 0$$ $$\Sigma Q = 2^n-1$$ $$\min \sum_i (H_i/\Sigma H - Q_i/\Sigma Q)^2$$

Is there a direct algorithm that gives an optimal result? Or perhaps a fast near-optimal approximation?

---

Without requirement #2 there is a solution by choosing $Q_i = \lfloor H_i/\Sigma H \cdot (2^n-1) \rfloor + a_i$. Where $a_i$ is initially 0 for all $i$. It's easy to see that $\Sigma Q \leq 2^n-1$, and setting $a_i$ = 1 for the $2^n-1 - \Sigma Q$ elements that have the biggest undershoot error solves the problem optimally.

The difficulty lies in the requirement that no element with nonzero occurrences may be floored to zero occurrences in the quantized histogram. Consider [1, 1, 1, 1000]. Without this requirement the most accurate quantization to $n = 3$ is [0, 0, 0, 7]. However the requirement gives us [1, 1, 1, 4].

Answer 1

This can be reduced to the following problem.

APPROXIMATE ROUNDING:
Input: real numbers $c_1,\dots,c_m \in \mathbb{R}$, an integer $d \in \mathbb{N}$
Goal: find non-negative integers $x_1,\dots,x_m \in \mathbb{N}$ that minimize $\sum_i (x_i - c_i)^2$, subject to the requirement $\sum_i x_i = d$.

The reduction: define $S = \{i : H_i > 0\}$, $x_i = Q_i - 1$ for $i \in S$, $d=2^n-1-|S|$, and

$$c_i = -1 + (2^n-1) H_i / \sum_j H_j.$$

Now the optimal solution to APPROXIMATE ROUNDING immediately yields the optimal solution to your problem, by setting $Q_i = x_i + 1$ for each $i \in S$ and $Q_i=0$ for each $i \notin S$.

---

Can we solve APPROXIMATE ROUNDING efficiently? I don't know. I conjecture there exists $t \in \mathbb{R}$ such that the optimal solution is $x_i = \lfloor t c_i \rceil$ for all $i$ (i.e., $x_i$ is $tc_i$ rounded to the nearest integer). If this is true, we can use binary search to find $t$ such that $\sum_{i \in S} \lfloor t c_i \rceil = d$, and thereby solve APPROXIMATE ROUNDING efficiently. However, I have no proof that this works.

Erwin Kalvelagen over on Math.SE has suggested that APPROXIMATE ROUNDING can be solved using a MIQP solver.