A fast butterfly algorithm for generalized Radon transforms |

To analyze the algorithm's numerical complexity, let us assume the numbers of Chebyshev points in every box and every dimension of and are all equal to a small constant , i.e., and . The main workload of the fast butterfly algorithm is in Steps 2 and 4. For each level, there are pairs of boxes , and the operations between each and is , which can be further reduced to by performing Chebyshev interpolation one dimension at a time. Since there are levels, the total cost is . It is not difficult to see that Step 3 takes , and Steps 1 and 5 take and operations. Considering the initial Fourier transform of preparing data in the domain, we conclude that the overall complexity of the algorithm is . The analysis in Candès et al. (2009) shows that the relation between and error is . We would like to mention that this is only the worst case estimate. Numerical results in the same paper demonstrate that the dependence of on is rather moderate in practice.

In comparison, the conventional *velocity scan* requires at least
computations, which quickly becomes a burden as the problem size increases. Yet the efficiency of our algorithm is mainly controlled by
with a constant polylogarithmic in
, where
depends neither on data size nor on data content (here we mean the data after the Fourier transform). Since the Chebyshev interpolation is only performed on the kernel, our choice of parameters (
and number of Chebyshev points) relies on the preknowledge about the range of
,
,
, and
. In other words, we need a general idea about how oscillate the kernel is. Recall that everything is mapped to a unit square, so the larger the range of
is, the more oscillations occur in the unit square. If the original data (data before the Fourier transform) contain high frequency information, the accuracy will be affected as the frequency bandwidth is now larger. A possible way to get around it is to divide the Fourier domain into two or three smaller subdomains (so the range of
in each subdomain is smaller than the original problem), and apply the fast algorithm to each part separately, finally add the results back together. This only increases the cost by a small factor, but presumably offers better accuracy.

A fast butterfly algorithm for generalized Radon transforms |

2013-07-26