A fast butterfly algorithm for generalized Radon transforms |

With the previously introduced low-rank approximations and the butterfly structure, we are ready to describe the fast algorithm. Our goal is to approximate , definition 21, so as to get , definition 19, by traversing the tree structure (Figure 2) from top to bottom on the side, and from bottom to top on the side. This can be done in five major steps. To avoid too much technical detail, we deliberately defer the complete derivation of the algorithm until the appendix, and only summarize here the final updating formulas for each step.

1. *Initialization.* At level
, let
be the root box of
. For each leaf box
, construct the coefficients
by

2. *Recursion.* At
, for each pair
, let
be
's parent and
be
's children from the previous level. Update
from
by

3. *Switch.* At middle level
, for each
compute the new set of coefficients
from the old set
by

4. *Recursion.* At
, for each pair
, update
from
of the previous level by

5. *Termination.* Finally at level
,
is the entire domain
. For every box
in
and every
, compute
by

A fast butterfly algorithm for generalized Radon transforms |

2013-07-26