In Nonlinear Approximation from Approximation, we measured the quality of a dictionary in terms of its KK-term approximations to signals drawn from some class. One reason that such approximations are desirable is that they provide concise descriptions of the signal that can be easily stored, processed, etc. There is even speculation and evidence that neurons in the human visual system may use sparse coding to represent a scene [13].

For data compression, conciseness is often exploited in a popular technique known as transform coding. Given a signal ff (for which a concise description may not be readily apparent in its native domain), the idea is simply to use the dictionary ΨΨ to transform ff to its coefficients αα, which can then be efficiently and easily described. As discussed above, perhaps the simplest strategy for summarizing a sparse αα is simply to threshold, keeping the KK largest coefficients and discarding the rest. A simple encoder would then just encode the positions and quantized values of these KK coefficients.

Suppose ff is a function and let fR^fR^ be an approximation to ff encoded using RR bits. To evaluate the quality of a coding strategy, it is common to consider the asymptotic rate-distortion (R-D) performance, which measures the decay rate of ∥f-fR^∥Lp∥f-fR^∥Lp as R→∞R→∞. The metric entropy [9] for a class FF gives the best decay rate that can be achieved uniformly over all functions f∈Ff∈F. We note that this is a true measure for the complexity of a class and is tied to no particular dictionary or encoding strategy. The metric entropy also has a very geometric interpretation, as it relates to the smallest radius possible for a covering of 2R2R balls over the set FF.

Metric entropies are known for certain signal classes. For example, the results of Clements [7] (extending those of Kolmogorov and Tihomirov [9]) regarding metric entropy give bounds on the optimal achievable asymptotic rate-distortion performance for DD-dimensional CHCH-smooth functions ff (see also [5]):

In some cases, however, the sparsity of the wavelet transform may not reflect the true underlying structure of a signal. Examples are 2-D piecewise smooth signals with a smooth edge discontinuity separating the smooth regions. As we discussed in Nonlinear Approximation from Approximation, wavelets fail to sparsely represent these functions, and so the R-D performance for simple thresholding-based coders will suffer as well. In spite of all of the benefits of wavelet representations for signal processing (low computational complexity, tree structure, sparse approximations for smooth signals), this failure to efficiently represent edges is a significant drawback. In many images, edges carry some of the most prominent and important information [12], and so it is desirable to have a representation well-suited to compressing edges in images.

To address this concern, recent work in harmonic analysis has focused on developing representations that provide sparse decompositions for certain geometric image classes. Examples include curvelets [4], [3] and contourlets [8], slightly redundant tight frames consisting of anisotropic, “needle-like” atoms. In [11], bandelets are formed by warping an orthonormal wavelet basis to conform to the geometrical structure in the image. A nonlinear multiscale transform that adapts to discontinuities (and can represent a “clean” edge using very few coarse scale coefficients) is proposed in [2]. Each of these new representations has been shown to achieve near-optimal asymptotic approximation and R-D performance for piecewise smooth images consisting of CHCH regions separated by discontinuities along CHCH curves, with H=2H=2 (H≥2H≥2 for bandelets). Some have also found use in specialized compression applications such as identification photos [10].

In [1], we have presented a scheme that is based on the simple yet powerful observation that geometric features can be efficiently approximated using local, geometric atoms in the spatial domain, and that the projection of these geometric primitives onto wavelet subspaces can therefore approximate the corresponding wavelet coefficients. We prove that the resulting dictionary achieves the optimal nonlinear approximation rates for piecewise smooth signal classes. To account for the added complexity of this encoding strategy, we also consider R-D results and prove that this scheme comes within a logarithmic factor of the optimal performance rate. Unlike the techniques mentioned above, our method also generalizes to arbitrary orders of smoothness and arbitrary signal dimension.