Bayesian Inference for Iterative Linear Solvers

25 concepts13 papers1 proposal

In classical numerical analysis, solving a large linear system $Ax = b$ is treated as a deterministic task. An iterative solver, such as the Conjugate Gradient (CG) method, generates a sequence of increasingly accurate point estimates for $x$. However, in large-scale applications, these solvers are frequently terminated early due to computational constraints. This leaves us with an approximation and an unquantified "numerical error."

Probabilistic numerical linear algebra reframes this entire paradigm. Instead of viewing computation as a purely deterministic execution of an algebraic recipe, it treats computation as an information-gathering process. Every step of an iterative solver provides new data about the unknown system, which can be used to update a statistical belief state.

Computation as Data Acquisition

The core insight behind this direction, as articulated by Philipp Hennig in Probabilistic Interpretation of Linear Solvers, is that standard numerical operations provide linear observations of a latent operator.

Consider what happens during a single iteration of a solver. The algorithm selects a search direction $d_k$ and computes a matrix-vector multiplication:

$$s_k = A d_k$$

In a classical framework, $s_k$ is simply an intermediate vector used to update the current guess. In a probabilistic framework, $s_k$ is a noise-free, linear observation of the unknown matrix $A$.

By placing a Gaussian prior distribution over the elements of the matrix $A$, its inverse $A^{-1}$, or the solution vector $x$ itself, each matrix-vector multiplication acts exactly like a data point in a Bayesian linear regression problem. As computation progresses, the solver updates its Gaussian prior into a posterior distribution. The mean of this posterior represents the current best estimate of the solution, while the covariance matrix explicitly quantifies the remaining uncertainty due to incomplete computation.

The Equivalence to Classical Solvers

Why does this probabilistic interpretation actually work? It works because classical projection methods are not separate from Bayesian inference; they are mathematically equivalent to it.

As shown by Simon Bartels et al., classical projection methods that constrain solutions to specific subspaces (such as Krylov subspaces) can be reconstructed exactly as the posterior mean of a Gaussian distribution. For instance, if you set up a specific matrix prior and perform sequential linear projections, the mean of your Bayesian belief state tracks the exact same path as the Conjugate Gradient algorithm. This connection was further generalized by Fanaskov Vladimir et al., who demonstrated how to reconstruct arbitrary classical projection methods by carefully designing priors that incorporate information about the matrix's null space.

This insight allows researchers to re-interpret classical numerical concepts through a statistical lens:

  • Preconditioning as Prior Beliefs: In traditional linear algebra, a preconditioner transforms a system to make it easier to solve. Simon Bartels et al. proved that right-preconditioning corresponds to defining a prior distribution over the solution space, while left-preconditioning modifies the observation model.
  • Matrix Decompositions as Inference: Standard matrix factorizations can similarly be viewed as the posterior mean of a Gaussian distribution over matrix elements, revealing that standard linear algebra routines contain inherent, hidden probabilistic measures (Philipp Hennig et al.).

Calibrating Numerical Uncertainty

For a probabilistic solver to be useful, its "error bars" must be statistically meaningful. If a solver terminates early and outputs a posterior variance, that variance must accurately reflect the true approximation error.

Tim W. Reid et al. investigated the statistical properties of these methods under Krylov priors, showing how the posterior distribution tracks uncertainty during convergence. To ensure rigorous calibration, Chris J. Oates et al. introduced a "lifting" procedure. By randomizing the initial guess of a linear stationary iteration, the solver produces a sequence of strongly calibrated probability distributions. Under this framework, the true solution becomes statistically indistinguishable from samples drawn from the solver's output distribution.

Why Refine Solvers into Probabilistic Agents?

Reframing linear algebra as Bayesian inference is more than a theoretical novelty; it solves critical practical challenges in modern machine learning and engineering.

Trading Computation for Uncertainty

In large-scale machine learning, such as Gaussian Process (GP) regression, computing predictions requires solving massive linear systems. When these systems are too large to solve exactly, we must truncate our computations.

Frameworks like IterGP (Jonathan Wenger et al.) and IterNCGP (Jonathan Wenger et al.) treat matrix-vector multiplications as data points to perform incremental Bayesian updates. If computation is stopped early, the remaining error is treated as "computational uncertainty" and added directly to the model's predictive variance. This allows practitioners to explicitly trade off computation time for wider, yet mathematically consistent, confidence intervals.

Robustness to Stochastic Noise

In stochastic optimization (e.g., training deep neural networks), algorithms often require Hessian-vector products. However, because these products are computed over mini-batches, they are corrupted by stochastic noise. Classical deterministic solvers fail or diverge in this environment.

By framing matrix estimation as a Bayesian inference problem, solvers can maintain a Gaussian posterior over the operator's values (Filip de Roos et al.). This probabilistic buffer prevents divergence by treating the mini-batch noise as observation noise within the Bayesian update, stabilizing pre-conditioning in stochastic environments.

Information Recycling

In many applications, we must solve a sequence of related linear systems. A probabilistic solver allows us to "recycle" information. The posterior distribution of a matrix or its inverse learned while solving one system can be used as the prior distribution for the next system (Philipp Hennig). This drastically reduces the total computational effort required across pipelines.

Computation-Aware Physical Control

This framework is vital for physical systems operating under strict hardware constraints. For instance, Alexandre Capone et al. demonstrated that treating the residual error of an early-terminated CG solver as a quantifiable variance component allows for stable robot control. Even when an onboard processor cannot finish the exact calculations in time, the control loop remains safe because it is aware of its own computational limitations.

Key Foundational Work

Probabilistic Interpretation of Linear Solvers (2015) — contributed 5 concept elements to this direction.
Probabilistic Approximate Least-Squares. (2016) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_probabilistic_linear_algebra_b9272013,
  title = {probabilistic linear algebra},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-linear-algebra/rdr_b92720135bbe46c6948de63051fa3b9c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_probabilistic_linear_algebra_b9272013_v1,
  title = {probabilistic linear algebra},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-linear-algebra/rdr_b92720135bbe46c6948de63051fa3b9c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake