# Efficient Covariance Approximations for Large Sparse Precision Matrices

arXiv: https://arxiv.org/abs/1705.08656 · HTML: https://mlsanity.com/paper/1705.08656/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2017.

## Built on by (most cited first, 4 of 4)

- [Patch-Based Image Restoration using Expectation Propagation](https://mlsanity.com/paper/2106.15327/) (2021)
- [Fast Scalable Image Restoration using Total Variation Priors and Expectation Propagation](https://mlsanity.com/paper/2110.01585/) (2021)
- [Flexible and Efficient Probabilistic PDE Solvers through Gaussian Markov Random Fields](https://mlsanity.com/paper/2503.08343/) (2025)
- [Deep Gaussian Markov Random Fields for Graph-Structured Dynamical Systems](https://mlsanity.com/paper/2306.08445/) (2023)

## Abstract (arXiv)

The use of sparse precision (inverse covariance) matrices has become popular because they allow for efficient algorithms for joint inference in high-dimensional models. Many applications require the computation of certain elements of the covariance matrix, such as the marginal variances, which may be non-trivial to obtain when the dimension is large. This paper introduces a fast Rao-Blackwellized Monte Carlo sampling based method for efficiently approximating selected elements of the covariance matrix. The variance and confidence bounds of the approximations can be precisely estimated without additional computational costs. Furthermore, a method that iterates over subdomains is introduced, and is shown to additionally reduce the approximation errors to practically negligible levels in an application on functional magnetic resonance imaging data. Both methods have low memory requirements, which is typically the bottleneck for competing direct methods.