A fast butterfly algorithm for generalized Radon transforms

Next: Butterfly structure Up: Algorithm Previous: Algorithm

## Low-rank approximations

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

 for (8)

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

 (9) (10)

and when , and are given by
 (11) (12)

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
Figure 1.
A 2D, ( , ) Chebyshev grid in box . is the center of the box. is a point on the grid.

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

 for (17)

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 (18)

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

 (19)

generated by points inside a box becomes

 for (20)

where

 (21)

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

Next: Butterfly structure Up: Algorithm Previous: Algorithm

2013-07-26