![]() |
![]() |
![]() |
![]() | 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
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
![]() ![]() |
(34) |
![]() ![]() |
(36) |
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
4. Recursion. The rest of the recursion is analogous to Step 2. For
, we have
![]() ![]() |
(44) |
![]() |
(46) |
5. Termination. Finally we reach the level
, and
is the entire domain
. For every box
in
and every
,
![]() |
(48) |
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
Figure A-1. The butterfly structure for the special case of ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() ![]() |
![]() |
![]() |
![]() |
![]() | A fast butterfly algorithm for generalized Radon transforms | ![]() |
![]() |