Introduction
Sparse Bayesian Learning (SBL) is a premier framework for signal recovery, offering high accuracy and automatic hyperparameter tuning without the need for the tedious cross-validation required by methods like Lasso. However, its adoption in high-dimensional applications—such as medical imaging or large-scale signal processing—has been hindered by a "computational wall." Standard SBL implementations require the explicit storage and inversion of a $D \times D$ covariance matrix, where $D$ is the signal dimension. For a signal of dimension $10^5$, this matrix requires gigabytes of memory and cubic time complexity, leading to frequent memory crashes and prohibitive runtimes.
The CoFEM Solution
This paper introduces CoFEM (Covariance-Free Expectation-Maximization), an inference scheme designed to bypass the covariance matrix entirely. CoFEM leverages two key numerical linear algebra techniques to maintain the benefits of SBL while drastically reducing its overhead:
- Diagonal Estimation: Model updates in SBL only require the diagonal elements of the covariance matrix. CoFEM estimates these values using a small set of random Rademacher "probe" vectors, avoiding the need to ever form the full $D \times D$ matrix.
- Conjugate Gradient (CG) Solver: Instead of direct matrix inversion, CoFEM treats posterior mean estimation as a system of linear equations ($Ax = b$) and solves it using the CG algorithm. This approach only requires matrix-vector multiplications, which are highly efficient and parallelizable.
By combining these methods, the memory footprint drops from $O(D^2)$ to $O(D)$, and the algorithm can directly exploit "fast" transforms (like FFTs or Wavelets) to achieve $O(D \log D)$ time complexity.
Experimental Evaluation
The authors evaluated CoFEM against standard EM, Approximate Message Passing (AMP), Variational Inference (VI), and Iterative Reweighted Least Squares (IRLS). Tests were conducted using both dense Gaussian dictionaries and structured Discrete Cosine Transform (DCT) dictionaries, with signal dimensions scaling up to $D = 2^{18}$ (approximately 262,144), matching the resolution of standard medical images.
Key Findings
- Unprecedented Speed and Scaling: On structured dictionaries, CoFEM achieved speedups of several orders of magnitude compared to standard EM. As shown in the computation time analysis, CoFEM (especially the GPU-accelerated version) scales efficiently to dimensions where other methods fail due to memory constraints.
- Memory Efficiency: By reducing memory requirements to $O(D)$, CoFEM allows SBL to run on a single standard GPU for problems that previously required massive server clusters or were computationally impossible.
- Robustness and Accuracy: Unlike AMP, which can fail to converge when the dictionary is not perfectly "well-behaved," CoFEM remains stable across various undersampling factors. Crucially, the use of estimated diagonals does not sacrifice accuracy; CoFEM converges at the same rate and reaches the same NRMSE as exact EM.
Conclusion
CoFEM removes the primary barrier to using Sparse Bayesian Learning in high-dimensional settings. By replacing explicit covariance matrices with iterative solvers and diagonal estimation, it enables fast, memory-efficient, and robust sparse coding that can fully leverage modern GPU hardware and fast transform implementations. This opens the door for SBL to be used in real-time high-resolution imaging and large-scale signal processing tasks.
Summary updated