Convergence in Variance of Chebyshev Accelerated Gibbs Samplers
Authors:
- Colin FoxColin Fox
- Albert ParkerAPAlbert Parker
- 1 January 2014
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 36 (1) , A124-A147
Abstract
A stochastic version of a stationary linear iterative solver may be designed to converge in distribution to a probability distribution with a specified mean $\mu$ and covariance matrix $A^{-1}$. A common example is Gibbs sampling applied to a multivariate Gaussian distribution which is a stochastic version of the Gauss--Seidel linear solver. The iteration operator that acts on the error in mean and covariance in the stochastic iteration is the same iteration operator that acts on the solution error in the linear solver, and thus both the stationary sampler and the stationary solver have the same error polynomial and geometric convergence rate. The polynomial acceleration techniques that are well known in numerical analysis for accelerating the linear solver may also be used to accelerate the stochastic iteration. We derive first-order and second-order Chebyshev polynomial acceleration for the stochastic iteration to accelerate convergence in the mean and covariance by mimicking the derivation for the linear solver. In particular, we show that the error polynomials are identical and hence so are the convergence rates. Thus, optimality of the Chebyshev accelerated solver implies optimality of the Chebyshev accelerated sampler. We give an algorithm for the stochastic version of the second-order Chebyshev accelerated SSOR (symmetric successive overrelaxation) iteration and provide numerical examples of sampling from multivariate Gaussian distributions to confirm that the desired convergence properties are achieved in finite precision.
Keywords
This publication has 16 references indexed in Scilit:
- Sampling Gaussian Distributions in Krylov Spaces with Conjugate GradientsSIAM Journal on Scientific Computing, 2012
- An Explicit Link between Gaussian Fields and Gaussian Markov Random Fields: The Stochastic Partial Differential Equation ApproachJournal of the Royal Statistical Society Series B: Statistical Methodology, 2011
- Optimal scaling for various Metropolis-Hastings algorithmsStatistical Science, 2001
- Rate of Convergence of the Gibbs Sampler in the Gaussian CaseMathematical Geology, 2001
- An Adaptive Metropolis AlgorithmBernoulli, 2001
- Updating Schemes, Correlation Structure, Blocking and Parameterization for the Gibbs SamplerJournal of the Royal Statistical Society Series B: Statistical Methodology, 1997
- Multigrid Monte Carlo method. Conceptual foundationsPhysical Review D, 1989
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of ImagesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1984
- Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methodsNumerische Mathematik, 1961
- ON STATIONARY PROCESSES IN THE PLANEBiometrika, 1954