A fast butterfly algorithm for generalized Radon transforms |

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

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,

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

(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

(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.

- Low-rank approximations
- Butterfly structure
- Fast butterfly algorithm
- Numerical complexity and accuracy

A fast butterfly algorithm for generalized Radon transforms |

2013-07-26