Fastdiscretecurvelettransforms

  This paper describes two digital implementations of a new mathematical transform, namely, the second generation curvelet transform [12, 10] in two and three dimensions. The first digital transformation is based on unequally-spaced fast Fourier transforms (USFFT) 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 digitaltransformations return a table of digital curvelet coefficients indexed by a scale parameter, anorientation parameter, and a spatial location parameter. And both implementations are fast in the sense that they run in O(n2 log n) flops for n by n Cartesian arrays in addition, they are also invertible, with rapid inversion algorithms of about the same complexity.