A fast butterfly algorithm for generalized Radon transforms |

The coefficients for are however not readily available. The so-called butterfly algorithm turns out to be an appropriate tool. The butterfly algorithm was introduced by Michielssen and Boag (1996), and generalized by O'Neil et al. (2010) and Candès et al. (2009). Different applications include sparse Fourier transform (Ying, 2009), and radar imaging (Demanet et al., 2012). Demanet et al. (2012) also provide a complete error analysis of the method introduced by Candès et al. (2009).

The idea of the butterfly algorithm is to obtain
for
at the last step of a hierarchical construction of *all* the coefficients
for *all* pairs of admissible boxes
belonging to a quad tree structure. The algorithm starts with very small boxes
, where
are easily computed by direct summation, and gradually increases the sizes of the boxes
in a multiscale fashion. In tandem, the sizes of the boxes
where
is evaluated must decrease to respect the admissibility of each couple
. The computation then mostly consists in updating coefficients
from one scale to the next -- from finer to coarser
boxes, and from coarser to finer
boxes.

The main data structure underlying the algorithm is a pair of quad trees and . The tree has as its root box (level 0 ) and is built by recursive, dyadic partitioning until level , where the finest boxes are of sidelength . The tree is built similarly but in the opposite direction. Figure 2 shows such a partition for . A crucial property of this structure is that at arbitrary level , the sidelengths of a box in and a box in always satisfy

(22) |

thus a low-rank approximation of the kernel is available at every level of the tree, for every couple of admissible boxes .

tree
The butterfly quad tree structure for the special case of
.
Figure 2. |
---|

A fast butterfly algorithm for generalized Radon transforms |

2013-07-26