![]() |
![]() |
![]() |
![]() | 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 | ![]() |
![]() |