Abstract
This paper provides a unified tutorial on stochastic simulation and optimization methods within the context of modern signal processing. As models increase in complexity and data dimensionality grows, traditional analytical solutions become intractable. We explore the convergence of Markov Chain Monte Carlo (MCMC) techniques and optimization strategies, highlighting how their integration addresses high-dimensional, non-smooth inverse problems.
Introduction
Modern signal processing applications, such as hyperspectral imaging and medical reconstruction, involve millions of unknown variables, rendering traditional analytical models obsolete. The core challenge lies in characterizing complex posterior distributions and scaling inference to "Big Data" regimes. This survey bridges the gap between stochastic simulation for uncertainty characterization and optimization for point estimate determination.
Stochastic Simulation (MCMC)
Markov Chain Monte Carlo (MCMC) methods are essential for sampling from intractable distributions. The Metropolis-Hastings (MH) algorithm serves as the foundational "universal machine" for this purpose, allowing for sampling from a target distribution $\pi(x)$ using a proposal distribution $q$.
While MH is universal, its efficiency can be limited in high dimensions due to random walk behavior. Advanced variants like the Metropolis Adjusted Langevin Algorithm (MALA) and Hamiltonian Monte Carlo (HMC) incorporate gradients and physics-inspired dynamics to improve scaling, moving from $O(N)$ to $O(N^{1/4})$. Gibbs sampling further simplifies the problem by updating variables individually or in blocks, effectively using a "divide and conquer" strategy.
Deterministic Surrogates
When exact simulation is too costly, deterministic approximations like Variational Bayes (VB) and Message Passing are employed. VB turns inference into an optimization problem by minimizing Kullback-Leibler divergence. Message passing algorithms, such as Belief Propagation (BP) and Approximate Message Passing (AMP), operate on factor graphs to pass "beliefs" between variables and factors.
AMP is particularly noted for its extreme efficiency in high-dimensional linear models, often achieving theoretical optimality in the large system limit. The paper highlights that running BP is actually a way of optimizing a specific approximation of the target distribution, specifically the Bethe Free Energy.
Optimization and the Proximal Revolution
Optimization tools like Stochastic Gradient Descent (SGD) and proximal methods are now being integrated into simulation. Proximal MCMC allows sampling from non-differentiable distributions, a critical advancement for models using sparsity-promoting priors or Total Variation. Incremental algorithms like SAGA and MISO further speed up convergence by processing data in small batches while maintaining global gradient information, achieving geometric convergence rates.
Key Insights and Results
The integration of these methods has led to several breakthroughs:
- Efficiency: Gradient-aware samplers (MALA, HMC) significantly outperform random walk methods in high dimensions, making complex Bayesian inference feasible.
- Theoretical Links: The connection between Belief Propagation and Bethe Free Energy optimization provides a solid theoretical foundation for message passing.
- Stability: Proximal MALA provides a stable framework for sampling from heavy-tailed or non-smooth distributions where standard methods might diverge.
Conclusion and Future Work
While powerful, these methods face challenges in robustness and parameter tuning. Future research is directed toward understanding the theoretical convergence of HMC, improving robustness for non-differentiable models, and exploring Riemannian manifolds to adapt to local data geometry. The continued blurring of the line between simulation and optimization remains a key driver of innovation in signal processing.
Summary updated