Fast Discrete Curvelet Transforms
The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Abstract
This paper describes two digital implementations of a new mathematical transform, namely, the second generation curvelet transform in two and three dimensions. The first digital transformation is based on unequally spaced fast Fourier transforms, while the second is based on the wrapping of specially selected Fourier samples. The two implementations essentially differ by the choice of spatial grid used to translate curvelets at each scale and angle. Both digital transformations return a table of digital curvelet coefficients indexed by a scale parameter, an orientation parameter, and a spatial location parameter. And both implementations are fast in the sense that they run in O(n^2 \log n) flops for n by n Cartesian arrays; in addition, they are also invertible, with rapid inversion algorithms of about the same complexity. Our digital transformations improve upon earlier implementations—based upon the first generation of curvelets—in the sense that they are conceptually simpler, faster, and far less redundant. The software CurveLab, which implements both transforms presented in this paper, is available at http://www.curvelet.org.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The contourlet transform: an efficient directional multiresolution image representation
Do, M. N., & Vetterli, M. (2005) · IEEE Transactions on Image Processing · doi:10.1109/tip.2005.859376 · Cited by 3,952
The Mathematics of Computerized Tomography
Natterer, F., & Wang, G. (2002) · Medical Physics · doi:10.1118/1.1429631 · Cited by 2,524 · cited 1×
“For example, in many important medical applications, one wishes to reconstruct an object f(x1, x2) from noisy and incomplete tomographic data [33], i.”
BackgroundThe curvelet transform for image denoising
Starck, J.-L., Candes, E. J., & Donoho, D. L. (2002) · IEEE Transactions on Image Processing · doi:10.1109/tip.2002.1014998 · Cited by 2,253 · cited 1×
“Soon after their introduction, researchers developed numerical algorithms for their implementation [37, 18], and scientists have started to report on a series of practical successes; see [39, 38, 27, 26, 20], for example.”
BackgroundSelf-citationFast wavelet transforms and numerical algorithms I
Beylkin, G., Coifman, R., & Rokhlin, V. (1991) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.3160440202 · Cited by 1,770 · cited 1×
“In the field of scientific computing, wavelets and related multiscale methods sometimes allow for the speeding up of fundamental scientific computations such as in the numerical evaluation of the solution of partial differential equations [2].”
New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities
Candès, E. J., & Donoho, D. L. (2004) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.10116 · Cited by 1,545 · cited 2×
“On the theoretical side and to the best of our knowledge, contourlets do not allow us to formulate theorems which are as strong as in approximation and operator theory, as in [5, 10].”
BackgroundSelf-citationShiftable multiscale transforms
Simoncelli, E. P., Freeman, W. T., Adelson, E. H., & Heeger, D. J. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.119725 · Cited by 1,333
Curvelets: A Surprisingly Effective Nonadaptive Representation for Objects with Edges
Candès, E. J., & Donoho, D. L. (2000) · Cited by 1,330
Self-citationThe steerable pyramid: a flexible architecture for multi-scale derivative computation
Simoncelli, E. P., & Freeman, W. T. (2002) · Proceedings., International Conference on Image Processing · doi:10.1109/icip.1995.537667 · Cited by 1,070 · cited 1×
“Without the claim of being exhaustive, let us mention only continuous wavelet theory [32] and steerable pyramids in the field of computer vision [35, 34].”
BackgroundFast Fourier Transforms for Nonequispaced Data
Dutt, A., & Rokhlin, V. (1993) · SIAM Journal on Scientific Computing · doi:10.1137/0914081 · Cited by 918
Ridgelets: a key to higher-dimensional intermittency?
Candès, E. J., & Donoho, D. L. (1999) · Philosophical Transactions of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.1999.0444 · Cited by 893 · cited 1×
“Now these implementations are based on the original construction [8] which uses a preprocessing step involving a special partitioning of phase-space followed by the ridgelet transform [4, 7] which is applied to blocks of data that are well localized in space and frequency.”
MethodSelf-citationSparse geometric image representations with bandelets
Le Pennec, E., & Mallat, S. (2005) · IEEE Transactions on Image Processing · doi:10.1109/tip.2005.843753 · Cited by 860 · cited 1×
“Given the significance of such intermediate dimensional phenomena, there has been a vigorous research effort to provide better adapted alternatives by combining ideas from geometry with ideas from traditional multiscale analysis [17, 19, 4, 31, 14, 16].”
Conjugate Gradient Methods for Toeplitz Systems
Chan, R. H., & Ng, M. K. (1996) · SIAM Review · doi:10.1137/s0036144594276474 · Cited by 801 · cited 1×
“The idea is to embed the Toeplitz in a larger circulant matrix of size 2n−1 which can then be applied efficiently by means of the FFT [40, 13].”
MethodWedgelets: nearly minimax estimation of edges
Donoho, D. L. (1999) · The Annals of Statistics · doi:10.1214/aos/1018031261 · Cited by 638 · cited 1×
“Given the significance of such intermediate dimensional phenomena, there has been a vigorous research effort to provide better adapted alternatives by combining ideas from geometry with ideas from traditional multiscale analysis [17, 19, 4, 31, 14, 16].”
Self-citationSparse multidimensional representation using shearlets
Labate, D., Lim, W.-Q., Kutyniok, G., & Weiss, G. (2005) · SPIE Proceedings · doi:10.1117/12.613494 · Cited by 455 · cited 1×
“The idea of using concentric squares and shears is also central to the construction of tight frames of “shearlets” by Guo, Kutyniok, Labate, Lim, Weiss, and Wilson in a recent series of papers [28, 29, 30] starting with [28].”
BackgroundRedundant Multiscale Transforms and Their Application for Morphological Component Separation
Starck, J.-L., Elad, M., & Donoho, D. (2004) · Advances in Imaging and Electron Physics · doi:10.1016/s1076-5670(04)32006-9 · Cited by 443 · cited 1×
“Soon after their introduction, researchers developed numerical algorithms for their implementation [37, 18], and scientists have started to report on a series of practical successes, see [ 39 , 38, 27, 26, 20] for example.”
BackgroundSelf-citationA Proposal for Toeplitz Matrix Calculations
Strang, G. (1986) · Studies in Applied Mathematics · doi:10.1002/sapm1986742171 · Cited by 428 · cited 1×
“The idea is to embed the Toeplitz in a larger circulant matrix of size 2n−1 which can then be applied efficiently by means of the FFT [40, 13].”
MethodOn the Fast Fourier Transform of Functions with Singularities
Beylkin, G. (1995) · Applied and Computational Harmonic Analysis · doi:10.1006/acha.1995.1026 · Cited by 334 · cited 2×
“Perhaps the most important references on this subject date back to the work of Dutt and Rokhlin [22] and Beylkin [3].”
BackgroundRecovering edges in ill-posed inverse problems: optimality of curvelet frames
Candès, E. J., & Donoho, D. L. (2002) · The Annals of Statistics · doi:10.1214/aos/1028674842 · Cited by 322 · cited 1×
“The statistical optimality of the curvelet shrinkage extends to other situations involving indirect measurements as in a large class of ill-posed inverse problems [9].”
BackgroundSelf-citationDirectional multiresolution image representations
Do, M. N. (2002) · doi:10.5075/epfl-thesis-2500 · Cited by 312 · cited 1×
“Given the significance of such intermediate dimensional phenomena, there has been a vigorous research effort to provide better adapted alternatives by combining ideas from geometry with ideas from traditional multiscale analysis [17, 19, 4, 31, 14, 16].”
Candès, E. J., & Guo, F. (2002) · Signal Processing · doi:10.1016/s0165-1684(02)00300-6 · Cited by 290
Self-citationThe curvelet representation of wave propagators is optimally sparse
Candès, E. J., & Demanet, L. (2005) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20078 · Cited by 272 · cited 4×
“4 Higher Dimensions Curvelets exist in any dimension [5].”
BackgroundInfluentialSelf-citationHarmonic Analysis of Neural Networks
Candès, E. J. (1999) · Applied and Computational Harmonic Analysis · doi:10.1006/acha.1998.0248 · Cited by 235 · cited 2×
“Now these implementations are based on the original construction [8] which uses a preprocessing step involving a special partitioning of phase-space followed by the ridgelet transform [4, 7] which is applied to blocks of data that are well localized in space and frequency.”
MethodSelf-citationBeamlets and Multiscale Image Analysis
Donoho, D. L., & Huo, X. (2002) · Lecture Notes in Computational Science and Engineering · doi:10.1007/978-3-642-56205-1_3 · Cited by 229 · cited 1×
“Given the significance of such intermediate dimensional phenomena, there has been a vigorous research effort to provide better adapted alternatives by combining ideas from geometry with ideas from traditional multiscale analysis [17, 19, 4, 31, 14, 16].”
Self-citationWavelets with composite dilations and their MRA properties
Guo, K., Labate, D., Lim, W.-Q., Weiss, G., & Wilson, E. (2006) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2005.07.002 · Cited by 210 · cited 1×
“The idea of using concentric squares and shears is also central to the construction of tight frames of “shearlets” by Guo, Kutyniok, Labate, Lim, Weiss, and Wilson in a recent series of papers [28, 29, 30] starting with [28].”
BackgroundFast Fourier Transforms for Nonequispaced Data, II
Dutt, A., & Rokhlin, V. (1995) · Applied and Computational Harmonic Analysis · doi:10.1006/acha.1995.1007 · Cited by 193
A parametrix construction for wave equations with C 1 , 1 coefficients
Smith, H. F. (1998) · Annales de l'Institut Fourier · doi:10.5802/aif.1640 · Cited by 192 · cited 1×
“A physical interpretation of this result is that curvelets may be viewed as coherent waveforms with enough frequency localization so that they behave like waves but at the same time, with enough spatial localization so that they simultaneously behave like particles [5] [36].”
BackgroundNonuniform fast Fourier transform
Duijndam, A. J. W., & Schonewille, M. A. (1999) · Geophysics · doi:10.1190/1.1444560 · Cited by 151 · cited 1×
“This idea is further refined in [21], where the authors also report on error estimates.”
BackgroundSparsity- and continuity-promoting seismic image recovery with curvelet frames
Herrmann, F. J., Moghaddam, P. P., & Stolk, C. C. (2007) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2007.06.007 · Cited by 132 · cited 1×
“Section 3 introduces the main ideas underlying the USFFT-based and the wrapping-based digital implementations which are then detailed in sections 4 and 6, respectively.”
BackgroundWavelets with composite dilations
Guo, K., Demetrio Labate, A., Lim, W., Weiss, G., & Wilson, E. (2004) · Electronic Research Announcements of the American Mathematical Society · doi:10.1090/s1079-6762-04-00132-5 · Cited by 114 · cited 1×
“The idea of using concentric squares and shears is also central to the construction of tight frames of “shearlets” by Guo, Kutyniok, Labate, Lim, Weiss, and Wilson in a recent series of papers [28, 29, 30] starting with [28].”
BackgroundCurvelets and Fourier Integral Operators
Candès, E. J., & Demanet, L. (2003) · Comptes Rendus Mathématique · doi:10.1016/s1631-073x(03)00095-5 · Cited by 108
Self-citationRapid Computation of the Discrete Fourier Transform
Anderson, C., & Dahleh, M. D. (1996) · SIAM Journal on Scientific Computing · doi:10.1137/0917059 · Cited by 61 · cited 1×
“Our approach is essentially the same as that of Anderson and Dahleh [1].”
ResultDetection and discrimination of cosmological non-Gaussian signatures by multi-scale methods
Starck, J., Aghanim, N., & Forni, O. (2004) · Astronomy and Astrophysics · doi:10.1051/0004-6361:20040067 · Cited by 61
Directional dyadic wavelet transforms: design and algorithms
Vandergheynst, P., & Gobbers, J.-F. (2002) · IEEE Transactions on Image Processing · doi:10.1109/tip.2002.999670 · Cited by 44 · cited 1×
“This is close in spirit to the discretization of the continuous directional wavelet transform proposed by Vandergheynst and Gobbers in [41].”
MethodDigital Implementation of Ridgelet Packets
Flesia, A. G., Hel-Or, H. Z., Averbuch, A. Z., Candès, E. J., Coifman, R. R., & Donoho, D. L. (2003) · Studies in computational mathematics · doi:10.1016/s1570-579x(03)80030-7 · Cited by 38 · cited 2×
“On the other hand, ridgelet packets [24] are defined directly in the frequency plane via interpolation onto a pseudopolar grid aligned with the trapezoids.”
MethodSelf-citationShiftable multi-scale transforms [or "What's wrong with orthonormal wavelets"]
Simoncelli, E. P. (1992) · Medical Entomology and Zoology · Cited by 23
Separation of primaries and multiples by non-linear estimation in the curvelet domain
Herrmann, F. J., & Verschuur, D. J. (2008) · cIRcle (University of British Columbia) · doi:10.14288/1.0107382 · Cited by 6 · cited 1×
“Soon after their introduction, researchers developed numerical algorithms for their implementation [37, 18], and scientists have started to report on a series of practical successes; see [39, 38, 27, 26, 20], for example.”
Background
Research works printed but not linked: 4
- L. Demanet, Curvelets, Wave Atoms, and Wave Equations , Ph.D. thesis, California Institute of Technology, Pasadena, CA, 2006.
- Candès E. J., 2002, Ann. Statist., 30, 784 ‐842
- M. N. Do and M. Vetterli, Contourlets , in Beyond Wavelets, G. V. Welland, ed., Academic Press, San Diego, CA, 2003.
- A. Zygmund, Trigonometric Series , Cambridge University Press, Cambridge, UK, 1964.
Cited by
A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging
Chambolle, A., & Pock, T. (2011) · Journal of Mathematical Imaging and Vision · doi:10.1007/s10851-010-0251-1 · Cited by 4,336
“Figure 10 (d) shows the result but now using to be the fast discrete curvelet transform [5].”
Infrared and visible image fusion methods and applications: A survey
Ma, J., Ma, Y., & Li, C. (2019) · Information Fusion · doi:10.1016/j.inffus.2018.02.004 · Cited by 1,732
Dictionaries for Sparse Representation Modeling
Rubinstein, R., Bruckstein, A. M., & Elad, M. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2040551 · Cited by 1,306
“In higher dimensions, the curvelet atoms become flattened ellipsoids, oscillatory along their short direction and smooth along the other directions [ 53 ], [54], [56].”
BackgroundMethodResultInfluentialFast Image Recovery Using Variable Splitting and Constrained Optimization
Afonso, M. V., Bioucas-Dias, J. M., & Figueiredo, M. A. T. (2010) · IEEE Transactions on Image Processing · doi:10.1109/tip.2010.2047910 · Cited by 1,223
“The goal of our splitting is not to address the difficulty raised by a non-separable and non-quadratic regularizer, but to exploit second order (Hessian) information of the function f 1 , as will be shown below.”
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
Becker, S., Bobin, J., & Candès, E. J. (2011) · SIAM Journal on Imaging Sciences · doi:10.1137/090756855 · Cited by 848
“, a fast wavelet transform [43], a fast curvelet transform [11], or a fast short-time Fourier transform [43], which makes this a low-cost extra step.”
BackgroundSelf-citation
Metadata
- Authors
- Candès, E., Demanet, L., Donoho, D., & Ying, L.
- Affiliations
- California Institute of Technology (US)
- Stanford University (US)
- Venue
- Multiscale Modeling & Simulation
- Published
- 2006-01
- Volume
- 5
- Issue
- 3
- Pages
- 861-899
- ISSN
- 1540-3459 (ISSN-L)
- 1540-3467
- OpenAlex
- W2115528090
- Semantic Scholar
- 376d81bd72028b827a2e538967907cac9fbf2890
- Cited by
- 2,573
- References
- 36
- Citations by year
- 2026: 48 · 2025: 48 · 2024: 70 · 2023: 74 · 2022: 96 · 2021: 127 · 2020: 117 · 2019: 152 · 2018: 147 · 2017: 169 · 2016: 167 · 2015: 199 · 2014: 179 · 2013: 156 · 2012: 162
- FWCI
- 179.02
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Multiscale Modeling and Simulation (publishedVersion)
- CaltechAUTHORS (California Institute of Technology) (submittedVersion)
- Funders
- National Science Foundation
- U.S. Department of Energy (FG0302ER25529)
- Topics
- Physical Sciences › Mathematics › Applied Mathematics › Mathematical Analysis and Transform Methods
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Image and Signal Denoising Methods
- Physical Sciences › Computer Science › Signal Processing › Digital Filter Design and Implementation
- Keywords
- curvelet transform, discrete curvelet transform
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.