A fast butterfly algorithm for generalized Radon transforms |

Clearly the range and possibly other factors such as gradient of phase determine the degree of oscillations in the kernel . Let be an integer power of two, which is on the order of the maximum value of for and (the exact choice of depends on the desired efficiency and accuracy of the algorithm, which will be made specific in numerical examples). The design of the fast algorithm relies on the key observation that the kernel , when properly restricted to subsets of and , admits accurate and low-rank separated approximations. More precisely, if and are two square boxes in and , with sidelengths , obeying -- in which case the pair is called admissible -- then

where is independent of for a fixed error . Here and below the subscript is slightly abused: should be understood as multi-indices , and accordingly is the total number of terms in a double sum. Furthermore, Candès et al. (2009) showed that this low-rank approximation can be constructed via a tensor-product Chebyshev interpolation of in the variable when , and in the variable when .

Specifically, when
,
and
are given by

and when , and are given by

Boldface letters , denote 2D vectors. is a point on the 2D, Chebyshev grid in box centered at , i.e., let , , then

(13) | |||

(14) |

where

(15) |

is the 1D Chebyshev grid of order on . See Figure 1 for an illustration. is the 2D Lagrange interpolation defined on the Chebyshev grid:

(16) |

Analogously, is a point on the 2D, Chebyshev grid in box centered at , and is the 2D Lagrange interpolation defined on this grid. Based on the discussion above, the number in low-rank approximation 8 is equal to when , and when .

grid
A 2D,
(
,
) Chebyshev grid in box
.
is the center of the box.
is a point on the grid.
Figure 1. |
---|

A simple way of viewing expressions 9 - 12 is: when , plugging expression 9 into approximation 8 (leaving as it is) yields

For fixed , the right hand side of equation 17 is just a special interpolation of function in variable , where are the interpolation points, are the basis functions. Likewise, when , plugging expression 12 into approximation 8, we get

For fixed , the right hand side of equation 18 is a special interpolation of in variable : are the interpolation points, are the basis functions.

Once the low-rank approximation 8 is known, computing the partial sum

generated by points inside a box becomes

where

The case that the box represents the whole domain is of particular interest, since it corresponds to the original problem. Therefore, if we can find the set of interaction coefficients relative to all admissible couples of boxes with , our problem will be solved.

A fast butterfly algorithm for generalized Radon transforms |

2013-07-26