# Iterative samplers

Here's some illustrations of the theorem that a **stationary sampler converges iff the corresponding stationary linear solver converges** (Fox & Parker,

*Bernoulli*, 2016; Fox & Parker,

*SISC*, 2014).

Here's an image of Gibbs iterates from a 2-D dimensional Gaussian in the typical coordinate
directions.

The Gauss-Siedel iteration which minimizes the corresponding quadratic using the same
coordinate directions converges geometrically (i.e., linear on the log scale) in 90
iterations:

When accelerated with Chebyshev polynomials, the sampling directions are more in line
with the eigen-directions of maximal variability.

The Chebyshev accelerated forward-backward sweeps of Gauss-Siedel on the corresponding
quadratic converges in 15 iterations:

Acceleration by non-stationary Conjugate Gradients (or Lanczos vectors) works in theory,
but implementation in finite precision is a work in progress (Parker & Fox, *SISC*, 2012; Parker et al., *JASA*, 2016). As expected from results from numerical linear algebra, a CG (or CD) sampler's
performance depends on the distribution of the eigenvalues of the covariance matrix.
2-D is easy to sample from, shown here are iterates from a Lanczos implementation
of a CG accelerated Gibbs sampler:

Unlike other iterative linear solvers, a CG linear solve finds the minimum of the
corresponding quadratic in a finite number of iterations (ie faster than geometric
convergence):