0.5 Beyond lossless compression

Universal lossy compression

Consider $x\in {\alpha }^n$ . The goal of lossy compression  [link] is to describe $\hat{x}$ , also of length $n$ but possibly defined over another reconstruction alphabet $\hat{\alpha }\ne \alpha$ , such that the description requires few bits and the distortion

is small, where $d(·,·)$ is some distortion metric. It is well known that for every $d(·,·)$ and distortion level $D$ there is a minimum rate $R\left(D\right)$ , such that $\hat{x}$ can be described at rate $R\left(D\right)$ . The rate $R\left(D\right)$ is known as the rate distortion (RD) function, it is the fundamental information theoretic limit of lossycompression  [link] , [link] .

The invention of lossy compression algorithms has been a challenging problem for decades. Despite numerous applicationssuch as image compression  [link] , [link] , video compression  [link] , and speech coding  [link] , [link] , [link] , there is a significant gap between theory and practice, and these practical lossy compressorsdo not achieve the RD function. On the other hand, theoretical constructions that achieve the RD function are impractical.

A promising recent algorithm by Jalali and Weissman  [link] is universal in the limit of infinite runtime. Its RD performance is reasonable even with modest runtime.The main idea is that the distortion version $\hat{x}$ of the input $x$ can be computed as follows,

where $\beta <0$ is the slope at the particular point of interest in the RD function, and $H_k\left(w^n\right)$ is the empirical conditional entropy of order $k$ ,

where $u^k$ is a context of order $k$ , and as before $n_w(u^k,a)$ is the number of times that the symbol $a$ appears following a context $u^k$ in $w^n$ . Jalali and Weissman proved  [link] that when $k=o(log(n\left)\right)$ , the RD pair $(H_k\left({\hat{x}}^n\right),\overline{d}(x^n,{\hat{x}}^n))$ converges to the RD function asymptotically in $n$ . Therefore, an excellent lossy compression technique is to compute $\hat{x}$ and then compress it. Moreover, this compression can be universal. In particular, the choice of context order $k=o(log(n\left)\right)$ ensures that universal compressors for context tress sources can emulate the coding length of the empirical conditional entropy ${\hat{H}}_k\left({\hat{x}}^n\right)$ .

Despite this excellent potential performance, there is still a tremendous challenge. Brute force computation of the globally minimum energysolution $\widehat{x^n}$ involves an exhaustive search over exponentially many sequences and is thus infeasible.Therefore, Jalali and Weissman rely on Markov chain Monte Carlo (MCMC)  [link] , which is a stochastic relaxation approach to optimization. The crux of the matter is to definean energy function,

The Boltzmann probability mass function (pmf) is

where $t>0$ is related to temperature in simulated annealing, and $Z_t$ is the normalization constant, which does not need to be computed.

Because it is difficult to sample from the Boltzmann pmf [link] directly, we instead use a Gibbs sampler , which computes the marginal distributions at all $n$ locations conditioned on the rest of $w^n$ being kept fixed. For each location, the Gibbs sampler resamples from the distribution of $w_i$ conditioned on $w^{n\setminus i}\triangleq \{w_n:n\ne i\}$ as induced by the joint pmf in [link] , which is computed as follows,