0.5 Beyond lossless compression  (Page 3/7)

Lossy compression of an analog input

So far, we have described the approach by Jalali and Weissman to compress $x^n\in {\alpha }^n$ . Suppose instead that $x\in {\mathbb{R}}^n$ is analog. Seeing that MCMC optimizes $w^n$ over a discrete alphabet, it would be convenient to keep doing so. However, because $\hat{\alpha }$ is finite, and assuming that square distortion is used, i.i., $d(x_i,w_i)={(x_i-w_i)}^2$ , we see that the distortion could be large.

Fortunately, Baron and Weissman showed  [link] that the following quantizer has favorable properties,

where $\gamma$ is an integer that grows with $n$ . That is, as $\gamma$ grows the set $\widehat{\alpha }$ of reproduction levels quantizers a wider internal more finely. Therefore, we have that the probability that some $x_i$ is an outlier, i.e., $|x_i|<\gamma$ , vanishes with $n$ , and the effect of outliers on $\overline{d}(x,\overline{x})$ vanishes. Moreover, because the internal is sampled more finely as $\gamma$ increases with $n$ , this quantizer can emulate any codebook with continuous levels, and so in the limit its RD performance converges to the RD function.

Rate distortion performance

To evaluate the RD performance, we must first define the RD function. Consider a source $X$ that generates a sequence $x^n\in {\mathbb{R}}^n$ . A lossy encoder is a mapping $e:{\mathbb{R}}^n\to \mathcal{C}$ , where $\mathcal{C}\subset {\mathbb{R}}^n$ is a codebook that contains a set of codewords in ${\mathbb{R}}^n$ . Let ${\mathcal{C}}^n(x,D)$ be the smallest cardinality codebook for inputs of length $n$ generated by $X$ such that the expected per-symbol distortion between the input $x^n$ and the codeword $e\left(x\right)\in {\mathcal{C}}^n(x,D)$ is at most $D$ . The rate $R^n(x,D)$ is the per-symbol log-cardinality of the codebook,

This is an operational definition of the RD function in terms of the best block code. In contrast, it can be shown that the RD function is equalto a minimization over mutual information, yielding a different flavor of definition  [link] , [link] .

Having defined the RD function, we can describe the RD performance of the compression algorithm by Baron and Weissman for continuous valued inputs.

Theorem 8 Consider square error distortion, $d(x_i,{\hat{x}}_i)={(x_i-{\hat{x}}_i)}^2$ , let $X$ be a finite variance stationary and ergodic source with RD function $R(X,D)$ , and use the MCMC algorithm with data independent reproduction alphabet $\hat{\alpha }$ and temperature that decays sufficiently slowly. Let $w_r^n$ be the approximation to $x^n$ after $r$ super-iterations. Then the length of context tree weighting (CTW) applied to $w_r^n$ converges as follows,

Remark 1 Let us make some comments.

• This result implies that CTW is used to compress $w_r^n$ after it has been generated by MCMC. Instead of CTW, other universal compression approaches can be used.
• The same result can be proved for $l_p$ distortion metrics, and not just $l_2$ .
• A result with similar flavor was proved by Jalali and Weissman for discrete alphabets  [link] .

Adaptive reproduction levels : The above algorithm is promising from a theoretical perspective, but is of limited practical interest. In order to approach the RD function closely, $\hat{\alpha }$ may need to be large, which slows down the algorithm.

Our approach to overcome the large alphabet is inspired by the work by Rose  [link] , who showed that in many cases the optimal RD codebook uses a small discrete-valuedreproduction alphabet. This runs counter to our intuition that a continuous reproduction alphabet is needed to compress a continuous valued source. Therefore, we propose analgorithm that allows for reduction of the alphabet size while supporting adaptive reproduction levels.