4
$\begingroup$

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].

$\endgroup$
  • $\begingroup$ @D.W. Yes, I mean the sum of the counts in each bin. The histograms I refer to in my question do not actually contain the elements they count to, they are simply arrays of occurrence counts, e.g. [2, 2, 8, 0, 3]. The sum of that histogram would be 2 + 2 + 8 + 0 + 3 = 15. $\endgroup$ – orlp Feb 27 '16 at 7:31
  • $\begingroup$ @D.W. I never intended it to be that way, although I have to admit that I was exceptionally unclear. For arithmetic coding the quantized histogram gets converted into cumulative probabilities (so [2, 2, 8, 0, 3] would become [0, 2, 4, 12, 12, 15]), and the point is that these represent breakpoints in a discrete $n$-bit probability. $\endgroup$ – orlp Feb 27 '16 at 23:56
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @orlp, yes, thank you! That was a stupid typo. Fixed -- I appreciate it. $\endgroup$ – D.W. Feb 28 '16 at 0:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.