Abstract
Sparse inverse problems are fundamental to signal processing, yet their solution often hinges on the manual tuning of regularization parameters. This "tuning headache" limits the applicability of standard methods like Lasso or Iterative Hard Thresholding (IHT) in automated or real-time systems. We introduce LEMUR (Latent EM Unsupervised Regression), a novel algorithm that eliminates the need for manual hyperparameter selection. By integrating two distinct Expectation-Maximization (EM) strategies—a stable Joint MAP estimation and a precise Latent Variable EM—LEMUR achieves robust parameter estimation and signal reconstruction. Experimental results demonstrate that LEMUR outperforms existing unsupervised methods like BGAMP in stability, particularly with non-zero mean measurement matrices, and rivals supervised methods in accuracy while maintaining high computational efficiency.
Introduction
In signal processing, inverse problems involve recovering an original signal $x$ from noisy measurements $y$, typically modeled as $y = Ax + e$. When $x$ is known to be sparse, recovery techniques often rely on a regularization parameter $\lambda$ to balance data fidelity against sparsity. In practice, the optimal $\lambda$ depends on unknown quantities like the true noise variance and the signal's sparsity level, leading to a reliance on manual "tweaking" or computationally expensive cross-validation.
Existing unsupervised approaches have notable drawbacks. Bayesian Markov Chain Monte Carlo (MCMC) methods, while accurate, are too slow for many applications. Approximate Message Passing (AMP) algorithms are fast but fragile; they frequently diverge if the measurement matrix $A$ deviates from the idealized zero-mean i.i.d. Gaussian assumption. LEMUR addresses these gaps by providing a fully unsupervised, robust, and efficient framework for sparse recovery.
Methodology
LEMUR models the sparse signal using a Bernoulli-Gaussian (BG) distribution, where each element is zero with probability $1-p$ and Gaussian with probability $p$. The algorithm's core innovation lies in its hybrid Expectation-Maximization strategy, which leverages a latent variable formulation ($z = x + n$) to decouple the signal from the measurement matrix.
The authors identified that two common EM formulations have complementary strengths:
- Joint MAP Estimation ($J_x$): This approach treats the signal $x$ as a parameter. It is highly stable and robust to initialization but yields biased parameter estimates.
- Latent Variable EM ($J_z$): This treats $x$ as a hidden variable. While theoretically unbiased and highly accurate near the optimum, it is extremely sensitive to initialization.
LEMUR combines these into a multi-stage pipeline: it starts with a "Method of Moments" for a coarse initial guess, employs the stable $J_x$ algorithm to move into the correct region of the parameter space, and finally uses the precise $J_z$ algorithm to achieve high-accuracy convergence.
Key Results
LEMUR demonstrated superior robustness and accuracy across the test suite. As shown in Figure 1, while the performance of BGAMP (cyan) collapses when the measurement matrix mean is non-zero ($\mu = 0.5$), LEMUR (blue) maintains a high output Signal-to-Noise Ratio (oSNR).
Key findings include:
- Parameter Estimation: LEMUR accurately recovers the sparsity $p$ and variances $\sigma_x^2, \sigma_e^2$ without prior knowledge.
- Support Recovery: It achieves a lower False Positive rate than SBL, meaning it is more reliable at identifying the true locations of non-zero signal elements.
- Computational Efficiency: LEMUR is significantly faster than SBL; in one benchmark, it converged in 3 seconds compared to SBL's 260 seconds.
- Oracle-Level Performance: In many cases, LEMUR's unsupervised recovery matched or exceeded the performance of supervised IHT tuned with perfect knowledge of the signal parameters.
Conclusion and Future Work
LEMUR provides a robust, "tuning-free" solution for sparse inverse problems, effectively breaking the requirement for zero-mean measurement matrices that plagues many fast recovery algorithms. While currently optimized for Bernoulli-Gaussian signals, future work could extend the framework to other distributions, such as Laplacian priors for heavy-tailed signals. Additionally, scaling the algorithm to massive 3D imaging datasets through the use of fast operators remains a promising direction for further research.
Summary updated