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:
- Any element with 0 occurrences must have 0 occurrences after quantization.
- Any element with > 0 occurrences must have > 0 occurrences after quantization.
- 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].