A Caltech Library Service

Fast Discrete Curvelet Transforms

Candès, Emmanuel and Demanet, Laurent and Donoho, David and Ying, Lexing (2006) Fast Discrete Curvelet Transforms. Multiscale Modeling and Simulation, 5 (3). pp. 861-899. ISSN 1540-3459. doi:10.1137/05064182X.

See Usage Policy.

PDF (Author preprint)
See Usage Policy.


Use this Persistent URL to link to this item:


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

Item Type:Article
Related URLs:
URLURL TypeDescription
Candès, Emmanuel0000-0001-9234-924X
Donoho, David0000-0003-1830-710X
Additional Information:©2006 Society for Industrial and Applied Mathematics (Received October 3, 2005; accepted May 16, 2006; published September 26, 2006) We would like to thank Eric Verschuur and Felix Herrmann for providing seismic image data. The first author was partially supported by National Science Foundation grant DMS 01-40698 (FRG) and by Department of Energy grant DE-FG03-02ER25529. The last author was supported by Department of Energy grant DEFG03-02ER25529. Author preprint available online:
Subject Keywords:two-dimensional and three-dimensional curvelet transforms, fast Fourier transforms, unequally spaced fast Fourier transforms, smooth partitioning, interpolation, digital shear, filtering, wrapping
Issue or Number:3
Record Number:CaltechAUTHORS:CANmms06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6810
Deposited By: Archive Administrator
Deposited On:23 Dec 2006
Last Modified:08 Nov 2021 20:37

Repository Staff Only: item control page