  Sparse Bayesian learning (SBL) is a powerful framework for tackling the
sparse coding problem. However, the most popular inference algorithms for SBL
become too expensive for high-dimensional settings, due to the need to store
and compute a large covariance matrix. We introduce a new inference scheme that
avoids explicit construction of the covariance matrix by solving multiple
linear systems in parallel to obtain the posterior moments for SBL. Our
approach couples a little-known diagonal estimation result from numerical
linear algebra with the conjugate gradient algorithm. On several simulations,
our method scales better than existing approaches in computation time and
memory, especially for structured dictionaries capable of fast matrix-vector
multiplication.
