A fast butterfly algorithm for generalized Radon transforms

Butterfly structure

The coefficients $\delta_t^{AB}$ for $B=K$ 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 $\delta_t^{AB}$ for $B=K$ at the last step of a hierarchical construction of all the coefficients $\delta_t^{AB}$ for all pairs of admissible boxes $(A,B)$ belonging to a quad tree structure. The algorithm starts with very small boxes $B$ , where $\delta_t^{AB}$ are easily computed by direct summation, and gradually increases the sizes of the boxes $B$ in a multiscale fashion. In tandem, the sizes of the boxes $A$ where $u^B$ is evaluated must decrease to respect the admissibility of each couple $(A,B)$ . The computation then mostly consists in updating coefficients $\delta_t^{AB}$ from one scale to the next -- from finer to coarser $B$ boxes, and from coarser to finer $A$ boxes.

The main data structure underlying the algorithm is a pair of quad trees $T_X$ and $T_K$ . The tree $T_X$ has $[0,1]\times[0,1]$ as its root box (level 0 ) and is built by recursive, dyadic partitioning until level $L=\log N$ , where the finest boxes are of sidelength $1/N$ . The tree $T_K$ is built similarly but in the opposite direction. Figure 2 shows such a partition for $N=4$ . A crucial property of this structure is that at arbitrary level $l$ , the sidelengths of a box $A$ in $T_X$ and a box $B$ in $T_K$ always satisfy

$$w(A)w(B)=\frac{1}{2^l}\frac{1}{2^{L-l}}=\frac{1}{N};$$ (22)

thus a low-rank approximation of the kernel $e^{ 2\pi i\Phi(\mathbf{x},\mathbf{k})}$ is available at every level of the tree, for every couple of admissible boxes $(A,B)$ .

tree
Figure 2. The butterfly quad tree structure for the special case of $N=4$ .

A fast butterfly algorithm for generalized Radon transforms