A fast butterfly algorithm for generalized Radon transforms |

We are grateful to Tariq Alkhalifah, Anatoly Baumstein, Ian Moore, Daniel Trad, and the anonymous reviewer for their valuable comments and suggestions. We thank Dr. Alexander Klokov for preprocessing the field data. We thank KAUST and sponsors of the Texas Consortium for Computational Seismology (TCCS) for financial support.

This appendix gives a complete derivation and description of the butterfly algorithm, which combines the low-rank approximations and the butterfly structure introduced in the main text. For more mathematical exposition, the reader is referred to Candès et al. (2009).

To facilitate the presentation, we add a new figure (Figure A-1) to illustrate the notations.

1. *Initialization.* At level
, let
be the root box of
. For each leaf box
, expressions 9 and 10 are valid as
. Substituting
(in equation 10) into the definition of
, equation 21, we get

i.e. the equation 23 in the main text. In addition, for , the partial sum in equation 20 is given by (with (in equation 9) plugged in)

Comparing the right hand sides of equations 19 and A-2, if we call the sources at , then coefficients are just like the

2. *Recursion.* At
, for each pair
, let
be
's parent and
be
's children from the previous level (see Figure A-1). For each child
, we have available from the previous level an approximation of the form

for | (34) |

Summing over all children gives

Since , this is of course true for any . Also we know that equation 17 holds for , i.e.,

for | (36) |

Inserting it into expression A-4 yields

On the other hand, admits a low-rank approximation of equivalent sources at the current level,

Equating expressions A-6 and A-7 suggests that we can take

Substituting (in equation 10), we get

i.e. the equation 24 in the main text.

3. *Switch.* A switch of the representation to expressions 11 and 12 is needed at the middle level
since expressions 9 and 10 are no longer valid as soon as
(boxes
are getting bigger and bigger so that
is no longer satisfied). Plugging
(in equation 12) into the definition of
, equation 21, one has

from expression A-7,

where we use to denote the new set of coefficients and the old set. Equating expressions A-10 and A-11, we can set as

i.e. the equation 25 in the main text. This middle step is to switch from equivalent sources located at Chebyshev grid on the side to equivalent sources located at Chebyshev grid on the side.

4. *Recursion.* The rest of the recursion is analogous to Step 2. For
, we have

for | (44) |

thus

recalling expression A-10, one can simply set

(46) |

Inserting (in equation 11) gives the update

i.e. the equation 26 in the main text.

5. *Termination.* Finally we reach the level
, and
is the entire domain
. For every box
in
and every
,

(48) |

Plugging in (in equation 11), we get

i.e. the equation 27 in the main text. This final step is to transform the equivalent sources located at Chebyshev grid back to the targets located at (denoted by red dots in Figure A-1).

In the above algorithm, is assumed to be an even number. If is odd, one can either switch at level or . Everything else remains unchanged.

illus
The butterfly structure for the special case of
. The top right panel represents the input domain
with sources
located at
(blue dots). The bottom left panel represents the output domain
with targets
located at
(red dots). For the pair of boxes
at level
, box
is called
's parent at the previous level; four small boxes
are called
's children at the previous level.
Figure A-1. |
---|

A fast butterfly algorithm for generalized Radon transforms |

2013-07-26