Fast Computation of Fourier Integral Operators

DOI10.1137/060671139zbMATH Open1157.65522OpenAlexW2063399239MaRDI QIDQ3545254FDOQ3545254

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

zbMATH Keywords

computational complexitymatrix approximationnumerical examplesrandomized algorithmsFourier integral operatorsoscillatory integralswave propagationnonuniform fast Fourier transformseparated representationgeneralized Radon transformreflection seismologyoperator compressioncurvilinear tomography

Mathematics Subject Classification ID

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

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

(42)

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

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)