![]() |
![]() |
![]() |
![]() | 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) |
![]() |
---|
tree
Figure 2. The butterfly quad tree structure for the special case of ![]() |
![]() ![]() |
![]() |
![]() |
![]() |
![]() | A fast butterfly algorithm for generalized Radon transforms | ![]() |
![]() |