A fast butterfly algorithm for generalized Radon transforms

Next: Low-rank approximations Up: A fast butterfly algorithm Previous: Introduction

# Algorithm

Assume is a function in the data space. The hyperbolic Radon transform maps to a function in the model space (Thorson and Claerbout, 1985) through

 (1)

where is time, is offset, is intercept time, and is slowness. Fixing , hyperbola describes the traveltime for the event; hence integration along these curves can be used to identify different reflections.

Instead of approximating the integral in equation 1 directly, we reformulate it as a double integral,

 (2)

Here is the frequency, is the Fourier transform of in . A simple discretization of equation 2 yields

 (3)

(the area element is omitted; the same symbols , , , and are used for both continuous and discrete variables). The reason that hyperbolic RT is harder to compute than linear RT ( ) or parabolic RT ( ) should be clear from equation 3: product in the phase cannot be decoupled from other terms.

To construct the fast algorithm, we first perform a linear transformation to map all discrete points in and domains to points in the unit square ( represents a 2D rectangular domain in the -plane with and ), i.e., a point minmaxminmax is mapped to via

 maxminminmaxminmin (4)

a point minmaxminmax is mapped to via

 maxminminmaxminmin (5)

If we define input , output , and phase function , then equation 3 can be written as

 (6)

(throughout the paper, and will either be used for sets of discrete points or square domains containing them; the meaning should be clear from the context). This form is the discrete version of an oscillatory integral of the type

 (7)

whose fast evaluation has been considered in Candès et al. (2009). Our method for computing the summation in equation 6 follows the FIO butterfly algorithm introduced there.

Subsections
 A fast butterfly algorithm for generalized Radon transforms

Next: Low-rank approximations Up: A fast butterfly algorithm Previous: Introduction

2013-07-26