New tight frames of curvelets and optimal representations of objects with piecewise C 2 singularities

This paper introduces new tight frames of curvelets to address the problem of finding optimally sparse representations of objects with discontinuities along piecewise C 2 edges. Conceptually, the curvelet transform is a multiscale pyramid with many directions and positions at each length scale, and needle‐shaped elements at fine scales. These elements have many useful geometric multiscale features that set them apart from classical multiscale representations such as wavelets. For instance, curvelets obey a parabolic scaling relation which says that at scale 2 − j , each element has an envelope that is aligned along a “ridge” of length 2 − j /2 and width 2 − j . We prove that curvelets provide an essentially optimal representation of typical objects f that are C 2 except for discontinuities along piecewise C 2 curves. Such representations are nearly as sparse as if f were not singular and turn out to be far more sparse than the wavelet decomposition of the object. For instance, the n ‐term partial reconstruction f   n Cobtained by selecting the n largest terms in the curvelet series obeys$$\|f - f_n^C\|_{L_2}^2 \leq C \cdot n^{-2} \cdot (\log n)^3, \,\, n \rightarrow \infty\,.$$ This rate of convergence holds uniformly over a class of functions that are C 2 except for discontinuities along piecewise C 2 curves and is essentially optimal. In comparison, the squared error of n ‐term wavelet approximations only converges as n −1 as n → ∞, which is considerably worse than the optimal behavior. © 2003 Wiley Periodicals, Inc.