×

zbMATH — the first resource for mathematics

New tight frames of curvelets and optimal representations of objects with piecewise \(C ^{2}\) singularities. (English) Zbl 1038.94502
Summary: 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^C\) obtained 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,\quad n\to \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\to \infty\), which is considerably worse than the optimal behavior.

MSC:
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68U10 Computing methodologies for image processing
92C55 Biomedical imaging and signal processing
42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems
41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Antoine, Two-dimensional directional wavelets and the scale-angle representation, IEEE Signal Processing 52 pp 259– (1996) · Zbl 0875.94074 · doi:10.1016/0165-1684(96)00065-5
[2] Candès, Harmonic analysis of neural networks, Appl Comput Harmon Anal 6 pp 197– (1999) · Zbl 0931.68104 · doi:10.1006/acha.1998.0248
[3] Candès, Ridgelets and the representation of mutilated Sobolev functions, SIAM J Math Anal 33 pp 347– (2001) · Zbl 0989.42019 · doi:10.1137/S003614109936364X
[4] Candès , E. J. Demanet , L. 2002 http://www.acm.caltech.edu/demanet/
[5] Candès, Curvelets and Fourier integral operators, C R Acad Sci Paris Sér I Math 336 pp 395– (2003)
[6] Candès, Ridgelets: a key to higher-dimensional intermittency?, R Soc Lond Philos Trans Ser A Math Phys Eng Sci 357 (1760) pp 2495– (1999)
[7] Candès, Curves and surfaces pp 105– (2000)
[8] Candès, Recovering edges in ill-posed inverse problems: optimality of curvelet frames, Ann Statist 30 (3) pp 784– (2002) · Zbl 1101.62335 · doi:10.1214/aos/1028674842
[9] Candès, Directional wavelet transform via parabolic scaling I (2003)
[10] Candès, New multiscale transforms, minimum total variation synthesis: applications to edge-preserving image reconstruction, IEEE Signal Processing 82 pp 1519– (2002) · Zbl 1009.94510 · doi:10.1016/S0165-1684(02)00300-6
[11] Daubechies, CBMS-NSF Regional Conference Series in Applied Mathematics 61, in: Ten lectures on wavelets (1992)
[12] Daubechies, Painless nonorthogonal expansions, J Math Phys 27 (5) pp 1271– (1986) · Zbl 0608.46014 · doi:10.1063/1.527388
[13] Do , M. N. Directional multiresolution image representations 2001
[14] Do, Beyond wavelets (2002)
[15] Donoho, Unconditional bases are optimal bases for data compression and for statistical estimation, Appl Comput Harmon Anal 1 (1) pp 100– (1993) · Zbl 0796.62083 · doi:10.1006/acha.1993.1008
[16] Donoho, De-noising by soft-thresholding, IEEE Trans Inform Theory 41 (3) pp 613– (1995) · Zbl 0820.62002 · doi:10.1109/18.382009
[17] Donoho, Unconditional bases and bit-level compression, Appl Comput Harmon Anal 3 (4) pp 388– (1996) · Zbl 0936.62004 · doi:10.1006/acha.1996.0032
[18] Donoho, Wedgelets: nearly-minimax estimation of edges, Ann Statist 27 (3) pp 859– (1999) · Zbl 0957.62029 · doi:10.1214/aos/1018031261
[19] Donoho, Sparse components of images and optimal atomic decompositions, Constr Approx 17 (3) pp 353– (2001) · Zbl 0995.65150 · doi:10.1007/s003650010032
[20] Donoho, Digital curvelet transform: strategy, implementation, experiments (1999)
[21] Donoho , D. L. Johnstone , I. M. Empirical atomic decomposition 1995
[22] Donoho, Data compression and harmonic analysis, IEEE Trans Inform Theory 44 (6) pp 2435– (1998) · Zbl 1125.94311 · doi:10.1109/18.720544
[23] Fefferman, A note on spherical summation multipliers, Israel J Math 15 pp 44– (1973) · Zbl 0262.42007
[24] Flesia, Beyond wavelets (2002)
[25] Frazier, CBMS Regional Conference Series in Mathematics 79, in: Littlewood-Paley theory and the study of function spaces (1991) · Zbl 0757.42006
[26] Gressman, Beyond wavelets (2002)
[27] Kashin, Approximation properties of complete orthonormal systems, Trudy Mat Inst Steklov 172 pp 187– (1985) · Zbl 0581.42018
[28] Lemarié, Ondelettes et bases Hilbertiennes, Rev Mat Iberoamericana 2 pp 1– (1986) · Zbl 0657.42028
[29] Mallat, A wavelet tour of signal processing (1998) · Zbl 0937.94001
[30] Meyer, Wavelets: algorithms and applications (1993)
[31] Simoncelli, Shiftable multi-scale transforms, IEEE Trans Inform Theory 38 (2) pp 587– (1992) · doi:10.1109/18.119725
[32] Smith, A parametrix construction for wave equations with C1,1 coefficients, Ann Inst Fourier (Grenoble) 48 (3) pp 797– (1998)
[33] Starck , J.-L. Candès , E. J. Donoho , D. L. Very high quality image restoration by combining wavelets and curvelets Wavelets: applications in signal and image processing IX 9 19 M. A. Unser A. Aldroubi A. F. Laine The International Society for Optical Engineering Bellingham, Wash. 2001
[34] Starck, The curvelet transform for image denoising, IEEE Trans Image Process 11 pp 670– (2002) · Zbl 1288.94011 · doi:10.1109/TIP.2002.1014998
[35] Stein, Princeton Mathematical Series 43, in: Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals (1993)
[36] Taubman, High performance scalable image compression with EBCOT, IEEE Trans Image Process 9 (7) pp 1151– (2000) · doi:10.1109/83.847830
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.