High-Dimensional Sparse Bayesian Learning without Covariance Matrices
This addresses a bottleneck for researchers and practitioners using sparse Bayesian learning with large datasets, though it is incremental as it builds on existing methods.
The paper tackles the computational expense of sparse Bayesian learning in high-dimensional settings by introducing a new inference scheme that avoids explicit covariance matrix construction, resulting in better scaling in computation time and memory on simulations.
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.