Fast Computation of Fourier Integral Operators

DOI10.1137/060671139MaRDI QIDQ3545254zbMATH OpenOpenAlexFDO

Authors Emmanuel J. Candès, Laurent Demanet, Lexing Ying

Publication date 10 December 2008

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0610051, https://resolver.caltech.edu/CaltechAUTHORS:CANsiamjsc07

zbMATH Keywords

computational complexitycurvilinear tomographyFourier integral operatorsgeneralized Radon transformmatrix approximationnonuniform fast Fourier transformnumerical examplesoperator compressionoscillatory integralsrandomized algorithmsreflection seismologyseparated representationwave propagation

Mathematics Subject Classification ID

Radon transform (44A12) Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20) Seismology (including tsunami modeling), earthquakes (86A15) Biomedical imaging and signal processing (92C55)

Abstract: We introduce a general purpose algorithm for rapidly computing certain types of oscillatory integrals which frequently arise in problems connected to wave propagation and general hyperbolic equations. The problem is to evaluate numerically a so-called Fourier integral operator (FIO) of the form $int{e}^{2piiPhi(x,xi)}a(x,xi)hatf(xi)mathrmdxi$ at points given on a Cartesian grid. Here, $xi$ is a frequency variable, $hatf(xi)$ is the Fourier transform of the input $f$, $a(x,xi)$ is an amplitude and $Phi(x,xi)$ is a phase function, which is typically as large as $|xi|$; hence the integral is highly oscillatory at high frequencies. Because an FIO is a dense matrix, a naive matrix vector product with an input given on a Cartesian grid of size $N$ by $N$ would require $O(N^4)$ operations. This paper develops a new numerical algorithm which requires $O(N^{2.5}logN)$ operations, and as low as $O(sqrtN)$ in storage space. It operates by localizing the integral over polar wedges with small angular aperture in the frequency plane. On each wedge, the algorithm factorizes the kernel $e^{2piiPhi(x,xi)}a(x,xi)$ into two components: 1) a diffeomorphism which is handled by means of a nonuniform FFT and 2) a residual factor which is handled by numerical separation of the spatial and frequency variables. The key to the complexity and accuracy estimates is that the separation rank of the residual kernel is emph{provably independent of the problem size}. Several numerical examples demonstrate the efficiency and accuracy of the proposed methodology. We also discuss the potential of our ideas for various applications such as reflection seismology.

Recommendations

• A fast butterfly algorithm for the computation of Fourier integral operators
• scientific article; zbMATH DE number 1877173
• Computing Fourier integral operators with caustics
• Multiscale discrete approximation of Fourier integral operators
• A multiscale butterfly algorithm for multidimensional Fourier integral operators

Cited in

(45)

• Sparsity of Gabor representation of Schrödinger propagators
• Krylov subspace spectral methods for the time-dependent Schrödinger equation with non-smooth potentials
• Methods for fast computation of integral transforms
• Multidimensional butterfly factorization
• Deep learning for inverse problems. Abstracts from the workshop held March 7--13, 2021 (hybrid meeting)
• Approximate inversion of discrete Fourier integral operators
• A unified framework for oscillatory integral transforms: when to use NUFFT or butterfly factorization?
• Efficient representation and accurate evaluation of oscillatory integrals and functions
• An algorithm for the rapid numerical evaluation of Bessel functions of real orders and arguments
• Fast algorithms for the multi-dimensional Jacobi polynomial transform
• Quasi-Banach algebras and Wiener properties for pseudodifferential and generalized metaplectic operators
• Resolution analysis of inverting the generalized \(N\)-dimensional Radon transform in \(\mathbb{R}^n\) from discrete data
• Wave Phenomena
• Fast and approximate computation of Laplace and Fourier transforms
• Fast and accurate propagation of coherent light
• Fast wave computation via Fourier integral operators
• Multiscale discrete approximation of Fourier integral operators
• Computing Fourier integral operators with caustics
• Discrete symbol calculus
• Synthetic Aperture Inversion for Statistically Nonstationary Target and Clutter Scenes
• A fast butterfly algorithm for the computation of Fourier integral operators
• Numerical Simulation of Scattering Problems with Fourier-Integral Operators
• Regularity and multi-scale discretization of the solution construction of hyperbolic evolution equations with limited smoothness
• Optimization methods for synthetic aperture radar imaging
• scientific article; zbMATH DE number 953394 (Why is no real title available?)
• Fast Computation of Multidimensional Fourier Integrals
• scientific article; zbMATH DE number 1877173 (Why is no real title available?)
• How exponentially ill-conditioned are contiguous submatrices of the Fourier matrix?
• Extraction of digital wavefront sets using applied harmonic analysis and deep neural networks
• Resolution analysis of inverting the generalized Radon transform from discrete data in \(\mathbb{R}^3\)
• Fast Multiscale Gaussian Beam Method for Three-Dimensional Elastic Wave Equations in Bounded Domains
• Butterfly-net: optimal function representation based on convolutional neural networks
• Solving inverse problems using data-driven models
• A randomized method for one-step extrapolation in reverse time migration
• A multiscale butterfly algorithm for multidimensional Fourier integral operators
• Multiscale discrete approximations of Fourier integral operators associated with canonical transformations and caustics
• Fast computation of Toeplitz forms and some multidimensional integrals
• Interpolative butterfly factorization
• On the approximation of functions by tanh neural networks
• Simultaneous approximation of a smooth function and its derivatives by deep neural networks with piecewise-polynomial activations
• Wigner analysis of Fourier integral operators with symbols in the Shubin classes
• Composition and differentiation operators and fast approximation
• A linear-complexity tensor butterfly algorithm for compressing high-dimensional oscillatory integral operators
• Approximate method for computing hypersingular integrals with oscillatory kernels
• Nonlinear approximation of functions in two dimensions by sums of wave packets

This page was built for publication: Fast Computation of Fourier Integral Operators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3545254)