A Survey of Stochastic Simulation and Optimization Methods in Signal Processing

Abstract

Modern signal processing (SP) methods rely very heavily on probability and statistics to solve challenging SP problems. SP methods are now expected to deal with ever more complex models, requiring ever more sophisticated computational inference techniques. This has driven the development of statistical SP methods based on stochastic simulation and optimization. Stochastic simulation and optimization algorithms are computationally intensive tools for performing statistical inference in models that are analytically intractable and beyond the scope of deterministic inference methods. They have been recently successfully applied to many difficult problems involving complex statistical models and sophisticated (often Bayesian) statistical inference techniques. This survey paper offers an introduction to stochastic simulation and optimization methods in signal and image processing. The paper addresses a variety of high-dimensional Markov chain Monte Carlo (MCMC) methods as well as deterministic surrogate methods, such as variational Bayes, the Bethe approach, belief and expectation propagation and approximate message passing algorithms. It also discusses a range of optimization methods that have been adopted to solve stochastic problems, as well as stochastic methods for deterministic optimization. Subsequently, areas of overlap between simulation and optimization, in particular optimization-within-MCMC and MCMC-driven optimization are discussed.

To appear in the IEEE Journal of Selected Topics in Signal Processing special issue on Stochastic Simulation and Optimisation in Signal Processing, March 2016

References in corpus (34)

• MCMC using Hamiltonian dynamics
• Loopy Belief Propagation for Approximate Inference: An Empirical Study
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• The pseudo-marginal approach for efficient Monte Carlo computations
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Online Sparse System Identification and Signal Reconstruction using Projections onto Weighted ${\ell }_1$ Balls
• Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
• Proximal Splitting Methods in Signal Processing
• Communication-Efficient Distributed Dual Coordinate Ascent
• Optimal scalings for local Metropolis--Hastings chains on nonproduct targets in high dimensions
• Langevin diffusions and the Metropolis-adjusted Langevin algorithm
• Regularized Least-Mean-Square Algorithms
• Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions
• Estimating the granularity coefficient of a Potts-Markov random field within an MCMC algorithm
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Weak convergence of Metropolis algorithms for non-i.i.d. target distributions
• Optimizing The Integrator Step Size for Hamiltonian Monte Carlo
• Efficient Gaussian Sampling for Solving Large-Scale Inverse Problems using MCMC Methods
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• A General Metric for Riemannian Manifold Hamiltonian Monte Carlo
• Adaptive Gibbs samplers and related MCMC methods
• An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals
• Metropolis-Hastings within Partially Collapsed Gibbs Samplers
• Accelerated, Parallel and Proximal Coordinate Descent
• Variational Free Energies for Compressed Sensing
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• The Geometric Foundations of Hamiltonian Monte Carlo
• Fast Stochastic Alternating Direction Method of Multipliers
• A Stochastic forward-backward splitting method for solving monotone inclusions in Hilbert spaces
• Block stochastic gradient iteration for convex and nonconvex optimization
• mS2GD: Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• A shrinkage-thresholding Metropolis adjusted Langevin algorithm for Bayesian variable selection

Cited by in corpus (33)

• Evolutionary Reinforcement Learning: A Survey
• Uncertainty quantification for radio interferometric imaging: I. proximal MCMC methods
• Group Importance Sampling for Particle Filtering and MCMC
• Stochastic Physics-Informed Neural Ordinary Differential Equations
• Hybrid Approximate Message Passing
• Split-and-augmented Gibbs sampler - Application to large-scale inference problems
• Unsupervised Nonlinear Spectral Unmixing based on a Multilinear Mixing Model
• A Random Block-Coordinate Douglas-Rachford Splitting Method with Low Computational Complexity for Binary Logistic Regression
• Proximal nested sampling for high-dimensional Bayesian model selection
• Optimized Population Monte Carlo
• Preconditioned P-ULA for Joint Deconvolution-Segmentation of Ultrasound Images -- Extended Version
• Optimal Diffusion Processes
• Fast Gibbs sampling for high-dimensional Bayesian inversion
• Stochastic Optimization from Distributed, Streaming Data in Rate-limited Networks
• Covid19 Reproduction Number: Credibility Intervals by Blockwise Proximal Monte Carlo Samplers
• Bayesian imaging using Plug & Play priors: when Langevin meets Tweedie
• Stochastic Proximal Gradient Algorithms for Multi-Source Quantitative Photoacoustic Tomography
• Efficient Bayesian computation by proximal Markov chain Monte Carlo: when Langevin meets Moreau
• Markov-Chain Monte Carlo Approximation of the Ideal Observer using Generative Adversarial Networks
• Accelerating proximal Markov chain Monte Carlo by using an explicit stabilised method
• Maximum likelihood estimation of regularisation parameters in high-dimensional inverse problems: an empirical Bayesian approach. Part I: Methodology and Experiments
• Efficient sampling of non log-concave posterior distributions with mixture of noises
• A Distributed Block-Split Gibbs Sampler with Hypergraph Structure for High-Dimensional Inverse Problems
• The Stochastic Fejér-Monotone Hybrid Steepest Descent Method and the Hierarchical RLS
• Joint Segmentation and Deconvolution of Ultrasound Images Using a Hierarchical Bayesian Model based on Generalized Gaussian Priors
• A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation
• Variational Bayesian Approach and Gauss-Markov-Potts prior model
• Tomography for Plasma Imaging: a Unifying Framework for Bayesian Inference
• Bayesian Imaging With Data-Driven Priors Encoded by Neural Networks: Theory, Methods, and Algorithms
• Quantifying Uncertainty in High Dimensional Inverse Problems by Convex Optimisation
• Deep Neural Network for Analysis of DNA Methylation Data
• Infinite Mixture of Inverted Dirichlet Distributions
• A Variational Bayesian Approach for Image Restoration. Application to Image Deblurring with Poisson-Gaussian Noise