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

DOI10.1016/J.ACHA.2011.03.006zbMATH Open1241.65062arXiv1101.3615OpenAlexW2264971801MaRDI QIDQ412395FDOQ412395

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)

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.

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

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

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)

Cites Work

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

Cited In (9)

• Enabling numerically exact local solver for waveform inversion -- a low-rank approach
• Compressed absorbing boundary conditions via matrix probing
• Randomized recompression of \(\mathcal {H}\)-matrices for BEM
• 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)