Probabilistic interpretation of linear solvers

DOI10.1137/140955501MaRDI QIDQ2954384zbMATH OpenOpenAlexFDO

Authors Philipp Hennig

Publication date 13 January 2017

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

conjugate gradient methodGaussian inferencelinear programmingquasi-Newton methods

Mathematics Subject Classification ID

Newton-type methods (49M15) Gaussian processes (60G15) Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Linear programming (90C05) Nonlinear programming (90C30)

Abstract: This manuscript proposes a probabilistic framework for algorithms that iteratively solve unconstrained linear problems $Bx=b$ with positive definite $B$ for $x$. The goal is to replace the point estimates returned by existing methods with a Gaussian posterior belief over the elements of the inverse of $B$, which can be used to estimate errors. Recent probabilistic interpretations of the secant family of quasi-Newton optimization algorithms are extended. Combined with properties of the conjugate gradient algorithm, this leads to uncertainty-calibrated methods with very limited cost overhead over conjugate gradients, a self-contained novel interpretation of the quasi-Newton and conjugate gradient algorithms, and a foundation for new nonlinear optimization methods.

Recommendations

• Probabilistic linear solvers: a unifying view
• Uncertainty calibration for probabilistic projection methods
• Probabilistic numerics and uncertainty in computations
• Bayesian Probabilistic Numerical Methods
• Quasi-Newton method: a new direction

Cited in

(22)

• Uncertainty calibration for probabilistic projection methods
• Probabilistic linear solvers: a unifying view
• Strong convergence rates of probabilistic integrators for ordinary differential equations
• A modern retrospective on probabilistic numerics
• A Bayesian conjugate gradient method (with discussion)
• Stochastic quasi-Newton with line-search regularisation
• Maximum entropy derivation of quasi-Newton methods
• Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games
• Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
• Conjugate gradients for kernel machines
• Gaussian belief propagation solvers for nonsymmetric systems of linear equations
• scientific article; zbMATH DE number 7626747 (Why is no real title available?)
• Bayesian Probabilistic Numerical Methods
• Subset simulation for probabilistic computer models
• An overview of stochastic quasi-Newton methods for large-scale machine learning
• Preconditioners for Krylov subspace methods: An overview
• Statistical properties of BayesCG under the Krylov prior
• A Bayesian approach to modeling finite element discretization error
• Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients
• The Taylor measure and its applications
• The multivariate Taylor measure function space and a generalization of Taylor's theorem
• The solvability of probabilistic regresses. A reply to Frederik Herzberg

This page was built for publication: Probabilistic interpretation of linear solvers

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