Matrix probing: a randomized preconditioner for the wave-equation Hessian

DOI10.1016/J.ACHA.2011.03.006MaRDI QIDQ412395zbMATH OpenOpenAlexFDO

Authors Laurent Demanet, Pierre-David Létourneau, Nicolas Boumal, Henri Calandra, Jiawei Chiu, Stanley Snelson

Publication date 4 May 2012

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.3615

zbMATH Keywords

numerical experimentsrandomized algorithmsseismologypreconditionerseismic imagingnormal operatorcurveletsdiscrete symbol calculusleast-squares fittinglinearized seismic inversion problemwave-equation Hessian

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Preconditioners for iterative methods (65F08) Seismology (including tsunami modeling), earthquakes (86A15) Inverse problems in geophysics (86A22) Existence theories for optimal control problems involving partial differential equations (49J20) Discrete approximations in optimal control (49M25)

Abstract: This paper considers the problem of approximating the inverse of the wave-equation Hessian, also called normal operator, in seismology and other types of wave-based imaging. An expansion scheme for the pseudodifferential symbol of the inverse Hessian is set up. The coefficients in this expansion are found via least-squares fitting from a certain number of applications of the normal operator on adequate randomized trial functions built in curvelet space. It is found that the number of parameters that can be fitted increases with the amount of information present in the trial functions, with high probability. Once an approximate inverse Hessian is available, application to an image of the model can be done in very low complexity. Numerical experiments show that randomized operator fitting offers a compelling preconditioner for the linearized seismic inversion problem.

Recommendations

• Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation
• A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity
• Efficient preconditionings for matrix problems resulting from high order methods for partial differential equations
• A preconditioned iterative method for H-matrices systems
• H-matrix Preconditioners in Convection-Dominated Problems
• Matrix-free preconditioning using partial matrix estimation
• scientific article; zbMATH DE number 4080825
• \(H\)-preconditioner for \(H\)-matrices
• On the spectral equivalence of hierarchical matrix preconditioners for elliptic problems

Cites work

• scientific article; zbMATH DE number 4191031 (Why is no real title available?)
• scientific article; zbMATH DE number 3709066 (Why is no real title available?)
• scientific article; zbMATH DE number 218269 (Why is no real title available?)
• A Linearised inverse problem for the wave equation
• A fast randomized algorithm for the approximation of matrices
• A microlocal analysis of migration.
• ALMOST PERIODIC FUNCTIONS AND PARTIAL DIFFERENTIAL OPERATORS
• Computation of Pseudo-Differential Operators
• Discrete symbol calculus
• Fast Discrete Curvelet Transforms
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Microlocal analysis of a seismic linearized inverse problem.
• Randomized algorithms for the low-rank approximation of matrices
• Sparsity- and continuity-promoting seismic image recovery with curvelet frames
• The curvelet representation of wave propagators is optimally sparse
• The phase flow method
• Wave atoms and sparsity of oscillatory patterns

Cited in

(9)

• Enabling numerically exact local solver for waveform inversion -- a low-rank approach
• Randomized recompression of \(\mathcal {H}\)-matrices for BEM
• Compressed absorbing boundary conditions via matrix probing
• Matrix probing and its conditioning
• Learning physics-based models from data: perspectives from inverse problems and model reduction
• A data scalable augmented Lagrangian KKT preconditioner for large-scale inverse problems
• Full waveform inversion through double-sweeping solver
• Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs
• Point spread function approximation of high-rank Hessians with locally supported nonnegative integral kernels

This page was built for publication: Matrix probing: a randomized preconditioner for the wave-equation Hessian

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