Compressive Sensing of Signals from a GMM with Sparse Precision Matrices

Jianbo Yang, Xuejun Liao, Minhua Chen, Lawrence CarinNeurIPS 2014

Overview

This paper introduces a method to reconstruct signals from highly incomplete measurements without needing a pre-trained model. By modeling signals as a Gaussian Mixture Model (GMM) with sparse precision matrices, the authors develop a "blind" compressive sensing framework that simultaneously learns the signal statistics and recovers the underlying data, significantly outperforming existing methods in image and video reconstruction.

The Challenge of "Blind" Compressive Sensing

Compressive Sensing (CS) allows us to acquire signals (like images or video) using far fewer samples than traditional theory suggests is necessary. However, most high-performance CS algorithms rely on a "prior"—a mathematical model of what the signal should look like.

Gaussian Mixture Models (GMMs) are excellent priors, but they face two major hurdles in the real world:

  1. The Training Gap: Usually, you need a massive database of "clean" signals to train a GMM before you can use it for reconstruction. In many applications, this clean data doesn't exist.
  2. Parameter Explosion: A standard GMM estimates full covariance matrices. For a signal of size $n$, the number of parameters grows quadratically ($n^2$), making it computationally expensive and prone to overfitting when data is scarce.

The authors tackle the challenge of "blind" CS: reconstructing signals from incomplete, noisy measurements when the underlying GMM is unknown and must be learned on the fly.

Methods: Hierarchical Bayesian Modeling

The authors propose a Hierarchical Bayesian Model that unifies signal recovery and model learning. The core innovation lies in how they constrain the GMM:

  • Sparse Precision Matrices (GMRFs): Instead of estimating dense covariance matrices, they estimate sparse precision matrices (the inverse of covariance). This treats the signal as a Gaussian Markov Random Field (GMRF), where each pixel only depends on its immediate neighbors. This reduces the number of parameters from $n^2$ to $n+s$ (where $s$ is the number of non-zero off-diagonals).
  • Laplacian Shrinkage & Group Sparsity: They use a Bayesian shrinkage prior (similar to the Graphical Lasso) to force unimportant connections in the precision matrix to zero. They specifically introduce "banding patterns" to exploit the fact that in vectorized image patches, neighboring pixels appear at predictable intervals.
Comparison of precision matrices learned by PLE, Sparse-GMM, and Sparse-GMM(G).
  • Variational EM Algorithm: Since they don't know the signals or the GMM parameters, they use a Variational Expectation-Maximization (EM) approach. The algorithm iterates: it estimates the signals based on the current GMM, then updates the GMM parameters based on those estimated signals.

Key Insights

  • Precision vs. Covariance: The shift from covariance to precision matrices is a powerful move. In images, a pixel’s relationship with the rest of the image is complex (dense covariance), but its relationship with its immediate neighbors is simple and direct (sparse precision).
  • Exploiting Image Topology: By using "group sparsity" based on banding patterns, the model encodes the physical 2D/3D structure of images and videos directly into the learning process.
  • Theoretical Soundness: The authors provide a theoretical performance bound proving that the reconstruction error vanishes as the number of available signals ($N$) increases, even though the GMM starts as an unknown. This bridges the gap between heuristic "blind" methods and rigorous CS theory.

Key Results

The proposed method, termed Sparse-GMM(G), consistently beat state-of-the-art algorithms like TwIST, GAP, and PLE across various datasets, including USPS handwritten digits, face datasets, and real-world hardware measurements.

  • Quantitative Performance: On the simulated NBA high-speed video dataset, Sparse-GMM(G) achieved an average PSNR (Peak Signal-to-Noise Ratio) of 28.05 dB, significantly higher than the 25.35 dB achieved by the Piecewise Linear Estimator (PLE).
PSNR evaluation across frames for the NBA video dataset.
  • Qualitative Improvements: In real hardware tests using data from a Coded Aperture Compressive Temporal Imaging (CACTI) camera featuring a rotating chopper wheel, the method produced much sharper images with fewer "ghosting" artifacts compared to traditional GMM methods.
  • Robustness: By restricting the precision matrices to be sparse, the model remained robust even when the "incompleteness" of the measurements was high.

Limitations and Future Work

  • Computational Cost: While more parameter-efficient than dense GMMs, the Variational EM process is iterative and computationally more demanding than simple analytical solvers.
  • Stationarity Assumption: The model assumes that the signals being sensed together share the same underlying GMM statistics. If the scene changes drastically and abruptly, the "batch" learning approach might struggle.
  • Hyperparameter Sensitivity: Although the Bayesian framework handles many parameters automatically, the choice of the number of mixture components ($K$) still requires tuning (e.g., via the Bayesian Information Criterion).

Future work could involve extending this framework to even more complex signal structures or optimizing the algorithm for real-time hardware implementation.

Summary updated

BibTeX
@inproceedings{yang2014compressive,
  author = {Jianbo Yang and Xuejun Liao and Minhua Chen and Lawrence Carin},
  title = {{Compressive Sensing of Signals from a GMM with Sparse Precision Matrices}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}

Loading related content...

Figure