0.5 Beyond lossless compression  (Page 2/7)

We can now write,

where $\Delta H_k(y^{i-1}b{y}_{i+1}^n,a)$ is the change in $H_k\left(w^n\right)$ when $y_i=a$ is replaced by $b$ , and $\Delta d(b,a,x_i)=d(b,x_i)-d(a,x_i)={(b-x_i)}^2-{(a-x_i)}^2$ is the change in distortion. Combining [link] and [link] ,

The maximum change in the energy within an iteration of MCMC algorithm is then bounded by

We refer to the resampling from a single location as an iteration, and group the $n$ possible locations into super-iterations. Baron and Weissman  [link] recommend an ordering where each super-iteration scans a permutation of all $n$ locations of the input, because in this manner each location is scanned fairly often. Other orderingsare possible, including a completely random order.

During the simulated annealing, the temperature $t$ is gradually increased, where in super-iteration $i$ we use $t=O(1/log(i\left)\right)$   [link] , [link] . In each iteration, the Gibbs sampler modifies $w^n$ in a random manner that resembles heat bath concepts in statistical physics. AlthoughMCMC could sink into a local minimum, we decrease the temperature slowly enough that the randomness of Gibbs sampling eventually drives MCMC out of the localminimum toward the set of minimal energy solutions, which includes $\widehat{x^n}$ , because low temperature $t$ favors low-energy $w^n$ . Pseudo-code for our encoder appears in Algorithm 1 below.

Algorithm 1 : Lossy encoder with fixed reproduction alphabet Input: $x^n\in {\alpha }^n$ , $\hat{\alpha }$ , $\beta$ , $c$ , $r$ Output: bit-stream Procedure:

1. Initialize $w$ by quantizing $x$ with $\hat{\alpha }$
2. Initialize $n_w(·,·)$ using $w$
3. for $r=1$ to $R$ do // super-iteration
4.      $t_r\leftarrow \frac{cn{\Delta }_k}{log\left(r\right)}$ // temperature
5.      Draw permutation of numbers $\{1,...,n\}$ at random
6.      for $r^{\text{'}}=1$ to $n$ do
7.         Let  $j$ be component $t^{\text{'}}$ in permutation
8.         Generate new $w_j$ using $f_s(w_j=·|w^{n\setminus j})$
9.         Update $n_w(·,·)[·]$
10. Apply CTW to $w^n$ // compress outcome

Computational issues

Looking at the pseudo-code, it is clear that the following could be computational bottlenecks:

1. Initializing $n_w(·,·)$ - a naive implementation needs to scan the sequence $w^n$ (complexity $O\left(n\right)$ ) and initialize a data structure with $|\hat{\alpha }{|}^{K+1}$ elements. Unless $K\lesssim {log}_{|\hat{\alpha }|}\left(n\right)$ , this is super linear in $n$ . Therefore, we recall that $K=o(log(n\left)\right)$ , and initializing $n_w(·,·)$ requires linear complexity $O\left(n\right)$ .
2. The inner loop is run $rn$ times, and each time computing $Pr(w_j=b|w^{n\setminus j})$ for all possible $b\in \hat{\alpha }$ might be challenging. In particular, let us consider computation of $\Delta d$ and $\Delta H$ .
   1. Computation of $\Delta d$ requires constant time, and is not burdensome.
   2. Computation of $\Delta H$ requires to modify the symbol counts for each context that was modified. A key contribution by Jalali and Weissman was to recognize that the array of symbol counts, $n_w(·,·)$ , would change in $O\left(k\right)$ locations, where $k$ is the context order. Therefore, each computation of $\Delta H$ requires $O\left(k\right)$ time. Seeing that $|\hat{\alpha }|$ such computations per iteration are needed, and there are $rn$ iterations, this is $O\left(krn\right|\hat{\alpha }\left|\right)$ .
   3. Updating $n_w(·,·)$ after $w_j$ is re-sampled from the Boltzmann distribution also requires $O\left(k\right)$ time. However, this step is performed only once per iteration, and not $|\hat{\alpha }|$ times. Therefore, this step requires less computation than step (b).