Probabilistic Iterative Methods for Linear Systems

This paper presents a probabilistic perspective on iterative methods for approximating the solution x_* ∈ ℝd of a nonsingular linear system A x_* = b. In the approach a standard iterative method on ℝd is lifted to act on the space of probability distributions P(ℝd). Classically, an iterative method produces a sequence xm of approximations that converge to x_*. The output of the iterative methods proposed in this paper is, instead, a sequence of probability distributions μm ∈ P(ℝd). The distributional output both provides a "best guess" for x_*, for example as the mean of μm, and also probabilistic uncertainty quantification for the value of x_* when it has not been exactly determined. Theoretical analysis is provided in the prototypical case of a stationary linear iterative method. In this setting we characterise both the rate of contraction of μm to an atomic measure on x_* and the nature of the uncertainty quantification being provided. We conclude with an empirical illustration that highlights the insight into solution uncertainty that can be provided by probabilistic iterative methods.