New tight frames of curvelets and optimal representations of objects with C² singularities
Emmanuel J. Candès · 2002
This paper introduces new tight frames of curvelets to address the problem of finding optimally sparse representations of objects with discontinuities along C 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 which 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 which are C except for discontinuities along C 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 obtained by selecting the n largest terms in the curvelet series obeys ‖f − f n ‖2L2 ≤ C · n −2 · (log n), n→∞. This rate of convergence holds uniformly over a class of functions which are C except for discontinuities along C 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 worst than the optimal behavior.