Motivated by the Markov Chain Monte Carlo (MCMC) approach to the compression of discrete sources developed by Jalali and Weissman, we propose a lossy compression algorithm for analog sources that relies on a finite reproduction alphabet, which grows with the input length. The algorithm achieves, in an appropriate asymptotic sense, the optimum Shannon theoretic tradeoff between rate and distortion, universally for stationary ergodic continuous amplitude sources. We further propose an MCMC-based algorithm that resorts to a reduced reproduction alphabet when such reduction does not prevent achieving the Shannon limit. The latter algorithm is advantageous due to its reduced complexity and improved rates of convergence when employed on sources with a finite and small optimum reproduction alphabet.
For analog sources , less progress has been made in developing theoretically-justified compression algorithms. Some results have been derived specifically for the high-rate regime, where the Shannon lower bound is asymptotically tight @cite_9 . In particular, in the limit of low distortions the RD limit has been characterized for mixtures of probability distribution functions (pdf's) where one distribution is discrete and the other continuous @cite_28 @cite_21 . For example, the sparse Gaussian source is a mixture pdf; bounds on its RD function have been provided @cite_26 @cite_6 @cite_30 @cite_24 .
@cite_30 @cite_26 @cite_28 @cite_9 @cite_21 @cite_6 @cite_24
2165434382 2134568086 2144797521 2157962569 2114361399 2164187391 2138420014
Modern image coders balance bitrate used for encoding the location of significant transform coefficients, and bitrate used for coding their values. The importance of balancing location and value information in practical coders raises fundamental open questions about how to code even simple processes with joint uncertainty in coefficient location and magnitude. The most basic example of such a process is studied: a 2-D process studied earlier by Weidmann and Vetterli that combines Gaussian magnitude information with Bernoulli location uncertainty. An insight into the coding of this process by investigating several new coding strategies based on more general approaches to lossy compression of location is presented. Extending these ideas to practical coding, a trellis-coded quantization algorithm with performance matching the published theoretical bounds is developed. Finally, the quality of the strategies is evaluated by deriving a rate-distortion bound using Blahut's algorithm for discrete sources. The rate distortion behavior of sparse memoryless sources is studied. These serve as models of sparse signal representations and facilitate the performance analysis of “sparsifying” transforms like the wavelet transform and nonlinear approximation schemes. For strictly sparse binary sources with Hamming distortion, R(D) is shown to be almost linear. For nonstrictly sparse continuous-valued sources, termed compressible, two measures of compressibility are introduced: incomplete moments and geometric mean. The former lead to low- and high-rate upper bounds on mean squared error D(R), while the latter yields lower and upper bounds on source entropy, thereby characterizing asymptotic R(D) behavior. Thus, the notion of compressibility is quantitatively connected with actual lossy compression. These bounding techniques are applied to two source models: Gaussian mixtures and power laws matching the approximately scale-invariant decay of wavelet coefficients. The former are versatile models for sparse data, which in particular allow to bound high-rate compression performance of a scalar mixture compared to a corresponding unmixed transform coding system. Such a comparison is interesting for transforms with known coefficient decay, but unknown coefficient ordering, e.g., when positions of highest-variance coefficients are unknown. The use of these models and results in distributed coding and compressed sensing scenarios are also discussed. The asymptotic (small distortion) behavior of the rate-distortion function of an n-dimensional source vector with mixed distribution is derived. The source distribution is a finite mixture of components such that under each component distribution a certain subset of the coordinates have a discrete distribution while the remaining coordinates have a joint density. The expected number of coordinates with a joint density is shown to equal the rate-distortion dimension of the source vector. Also, the exact small distortion asymptotic behavior of the rate-distortion function of a special but interesting class of stationary information sources is determined. New results are proved on the convergence of the Shannon (1959) lower bound to the rate distortion function as the distortion decreases to zero. The key convergence result is proved using a fundamental property of informational divergence. As a corollary, it is shown that the Shannon lower bound is asymptotically tight for norm-based distortions, when the source vector has a finite differential entropy and a finite spl alpha th moment for some spl alpha >0, with respect to the given norm. Moreover, we derive a theorem of Linkov (1965) on the asymptotic tightness of the Shannon lower bound for general difference distortion measures with more relaxed conditions on the source density. We also show that the Shannon lower bound relative to a stationary source and single-letter difference distortion is asymptotically tight under very weak assumptions on the source distribution. > The asymptotic behavior as epsilon approaches 0 of the epsilon -entropy of a mixed random variable and a finite-dimensional mixed random vector is explicitly investigated. It is shown that the asymptotic behavior of this epsilon -entropy resembles that of a continuous random variable multiplied by the relative weight of the continuous part. > Recent rate-distortion analyses of image transform coders are based on a trade-off between the lossless coding of coefficient positions versus the lossy coding of the coefficient values. We propose spike processes as a tool that allows a more fundamental trade-off, namely between lossy position coding and lossy value coding. We investigate the Hamming distortion case and give analytic results for single and multiple spikes. We then consider upper bounds for a single Gaussian spike with squared error distortion. The obtained results show a rate distortion behavior which switches from linear at low rates to exponential at high rates. We study the rate distortion function of the Bernoulli-Gaussian random variable which can be used to model sparse signals. Both lower and upper bounds on the rate distortion function are given.We show that the bounds are almost tight in the low distortion regime for sparse signals. Interestingly, a naive coding scheme is near-optimal in this scenario.