A fast butterfly algorithm for generalized Radon transforms

Conclusions

We constructed a fast butterfly algorithm for the hyperbolic Radon transform, a type of generalized Radon transforms. Compared with expensive integration in the time domain, the new method runs in only $O(N^2\log N)$ operations, where $N$ depends on the range of frequency and offset in the dataset and the range of intercept time and slowness in the model space, and can often be chosen smaller than the grid size. In practice, this may lead to speedup of several orders of magnitude. Our ongoing work is studying the performance of this fast solver on the sparse iterative inversion of the hyperbolic Radon transform applied to multiple attenuation.

Due to the generality of the butterfly algorithm, its application is not limited to the hyperbolic transform considered here. Using a different phase function, one can easily extend the algorithm to higher-order transforms. If the slowness or velocity range is not constant but a corridor around a central function, then a sparse butterfly algorithm can be designed to save the cost by building the quad tree adaptively. Furthermore, many of the Radon-like integral operators, such as Kirchhoff migration, the apex-shifted Radon transform, the anisotropic multiparameter velocity scan, etc., can be reformulated in a similar fashion as we did in this paper. To address these extensions, a 3D version of the butterfly algorithm might be more appropriate.

A fast butterfly algorithm for generalized Radon transforms