  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.
