![next](icons/next.png) |
![up](icons/up.png) |
![previous](icons/previous.png) |
![](icons/left.png) | A fast butterfly algorithm for generalized Radon transforms | ![](icons/right.png) |
![[pdf]](icons/pdf.png) |
Next: Low-rank approximations
Up: A fast butterfly algorithm
Previous: Introduction
Assume
is a function in the data space. The hyperbolic Radon transform
maps
to a function
in the model space (Thorson and Claerbout, 1985) through
![$\displaystyle (Rd)(\tau,p)=\int d(\sqrt{\tau^2+p^2h^2},h)\,dh,$](img54.png) |
(1) |
where
is time,
is offset,
is intercept time, and
is slowness. Fixing
, hyperbola
describes the traveltime for the event; hence integration along these curves can be used to identify different reflections.
Instead of approximating the integral in equation 1 directly, we reformulate it as a double integral,
![$\displaystyle (Rd)(\tau,p)=\iint\hat{d}(f,h) e^{ 2\pi i f\sqrt{\tau^2+p^2h^2} } \,df\,dh.$](img61.png) |
(2) |
Here
is the frequency,
is the Fourier transform of
in
. A simple discretization of equation 2 yields
![$\displaystyle (Rd)(\tau,p)=\sum_{f,h} e^{ 2\pi i f\sqrt{\tau^2+p^2h^2} }\hat{d}(f,h)$](img64.png) |
(3) |
(the area element is omitted; the same symbols
,
,
, and
are used for both continuous and discrete variables). The reason that hyperbolic RT is harder to compute than linear RT (
) or parabolic RT (
) should be clear from equation 3: product
in the phase cannot be decoupled from other terms.
To construct the fast algorithm, we first perform a linear transformation to map all discrete points in
and
domains to points in the unit square
(
represents a 2D rectangular domain in the
-plane with
and
), i.e., a point
min
max
min
max
is mapped to
via
a point
min
max
min
max
is mapped to
via
If we define input
, output
, and phase function
, then equation 3 can be written as
![$\displaystyle u(\mathbf{x})=\sum_{\mathbf{k}\in K} e^{ 2\pi i \Phi(\mathbf{x},\mathbf{k})}g(\mathbf{k}), \quad \mathbf{x}\in X$](img102.png) |
(6) |
(throughout the paper,
and
will either be used for sets of discrete points or square domains containing them; the meaning should be clear from the context). This form is the discrete version of an oscillatory integral of the type
![$\displaystyle u(\mathbf{x})=\int_K e^{ 2\pi i \Phi(\mathbf{x},\mathbf{k})}g(\mathbf{k}) \,d\mathbf{k},\quad \mathbf{x}\in X,$](img103.png) |
(7) |
whose fast evaluation has been considered in Candès et al. (2009). Our method for computing the summation in equation 6 follows the FIO butterfly algorithm introduced there.
Subsections
![next](icons/next.png) |
![up](icons/up.png) |
![previous](icons/previous.png) |
![](icons/left.png) | A fast butterfly algorithm for generalized Radon transforms | ![](icons/right.png) |
![[pdf]](icons/pdf.png) |
Next: Low-rank approximations
Up: A fast butterfly algorithm
Previous: Introduction
2013-07-26