PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Stochastic Simulation and Optimization Methods in Signal Processing

Marcelo Pereyra, Philip Schniter, Emilie Chouzenoux, Jean-Christophe Pesquet, Jean-Yves Tourneret, Alfred Hero, Steve McLaughlin

arXiv:1505.00273v4cs.ITmath.IT

TL;DR

Complex, high-dimensional signal-processing models can make statistical inference analytically intractable and exceed deterministic methods. This survey reviews simulation, optimization, surrogate inference, and methods that combine simulation with optimization. It highlights relationships among these approaches and identifies potential future research directions.

  • Problem

    Complex, high-dimensional models can make statistical inference analytically intractable and beyond the scope of deterministic inference methods.

    Source: §I · pp. 1–2

  • Method

    The paper surveys high-dimensional MCMC, deterministic surrogate inference, stochastic and deterministic optimization methods, and overlaps between simulation and optimization.

    Source: §I · pp. 1–2, §VI · p. 14

  • Results

    The survey highlights relationships among methods and discusses approaches combining simulation and optimization.

    Source: §I · p. 2, §VI · p. 14

  • Takeaways & Limitations

    The paper identifies potential future research directions for stochastic simulation and optimization in signal and image processing.

    Source: §I · p. 2

Abstract

from arXiv · show

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.

I. INTRODUCTION

The introduction motivates computational inference methods for complex, high-dimensional signal-processing problems and frames the paper as a tutorial survey of simulation, optimization, and their overlap. It then introduces Bayesian posterior inference and the Metropolis–Hastings framework used to draw samples from a target distribution.

I. INTRODUCTION

  • The survey covers high-dimensional MCMC, deterministic surrogate inference, stochastic optimization, and methods combining optimization with MCMC.Its stated aim is also to highlight relationships among methods and potential future research directions.Source: §I · pp. 1–2
  • Some methods, including sequential Monte Carlo and importance sampling, are outside the survey’s scope mainly because of space limitations.Source: §I · p. 2
  • Bayesian inference represents prior knowledge with p(x; θ), updates it to p(x|y; θ), and may seek posterior means, variances, or expected log statistics.MAP estimation can be more computationally tractable than numerical integration for many models.Source: §I · p. 2
  • Complex, high-dimensional models can make posterior integrals and posterior summaries computationally intractable, motivating more efficient alternatives such as MAP estimation.The introduction frames stochastic simulation and optimization as tools for inference beyond deterministic methods.Source: §I · pp. 1–2

II. STOCHASTIC SIMULATION METHODS

  • Metropolis–Hastings constructs a Markov chain targeting π by proposing a state from q and applying an accept–reject rule; under mild conditions, the chain converges to π.The acceptance probability does not require the normalization constant of π.Source: §II · pp. 2–3
  • Proposal efficiency can be assessed using integrated autocorrelation time, which depends on the chosen summary statistic; in high dimensions, asymptotic diffusion speed provides a statistic-independent comparison.The criterion is related to effective independent Monte Carlo sample counts and the mean square error of estimates.Source: §II · p. 3
  • Conventional Metropolis–Hastings sampling may be infeasible when computing its acceptance probability requires an intractable quantity, such as a Potts-model partition function.Source: §II · p. 3

A. Random walk Metropolis-Hastings algorithms

The section compares random-walk, Langevin, and Hamiltonian Metropolis–Hastings proposals for high-dimensional targets, outlining their efficiency, tuning, and convergence trade-offs.

A. Random walk Metropolis-Hastings algorithms

  • RWMH uses random-walk proposals and is geometrically ergodic under mild conditions, but its performance generally deteriorates at O(N) and samples can be highly correlated in high dimensions.For sufficiently smooth targets, scaling the proposal covariance to yield approximately 20%–25% acceptance can improve performance; the complexity measure excludes proposal-generation and acceptance costs, which typically scale at least linearly with N.Source: A. Random walk Metropolis-Hastings… · p. 3

B. Metropolis adjusted Langevin algorithms

  • For sufficiently smooth targets, MALA scales as O(N^1/3), compared with O(N) for RWMH, but may perform poorly on nonsmooth or multimodal targets or with unsuitable tails or step size.MALA uses gradient information in its proposal; covariance or step-size scaling can improve efficiency, while computing full Hessian or Fisher matrices may be too costly at high dimensions.Source: B. Metropolis adjusted Langevin… · pp. 3–4

C. Hamiltonian Monte Carlo

  • For certain target densities, HMC complexity scales as O(N^1/4), favorably versus MALA’s O(N^1/3), though convergence is less understood and it may fail with super-Gaussian or heavy tails or overly large δ.Source: C. Hamiltonian Monte Carlo · p. 4

D. Gibbs sampling

Gibbs sampling updates components or groups using their conditional distributions, preserving the joint target while making efficiency depend on update structure and conditional sampling cost.

D. Gibbs sampling

  • Gibbs sampling updates elements or groups of x from their conditional distributions, and concatenating these component-wise kernels preserves π(x) as the joint invariant distribution.The invariant-target property also holds when conditional updates use other MCMC algorithms, though convergence may deteriorate.Source: D. Gibbs sampling · p. 5
  • Efficiency improves when strongly correlated elements are updated together and slow-moving elements more often, but parallel updates can require more costly conditional distributions.Pilot runs or adaptive Gibbs samplers can learn the dependence structure and adjust the update schedule.Source: D. Gibbs sampling · p. 5
  • Signal-processing models often have sparse conditional-independence structures and conjugate exponential-family priors, yielding simple one-dimensional conditionals that can be updated in parallel by groups.Source: D. Gibbs sampling · p. 5

E. Partially collapsed Gibbs sampling

Partially collapsed Gibbs sampling replaces selected conditionals with marginalized ones to address inefficient conventional updates, while variational Bayes approximates the posterior within a tractable density family.

E. Partially collapsed Gibbs sampling

  • Partially collapsed Gibbs sampling replaces a conditional with a marginalized conditional to address poor exploration when strongly dependent variables are updated separately.The method is at least as efficient as conventional Gibbs sampling, but requires exact draws from partially collapsed conditionals; using MCMC within it can produce an incorrect algorithm, and changing update order may alter the target.Source: E. Partially collapsed Gibbs sampling · p. 5

A. Variational Bayes

  • Variational Bayes approximates the true posterior with a density from a restricted family, balancing fidelity against tractability because the posterior is difficult to work with.Source: A. Variational Bayes · pp. 5–6
  • Using D(q∥p) favors agreement with the true posterior where p(x|y) is large, and the variational optimization avoids the difficult integral.Source: A. Variational Bayes · p. 6

B. The mean-field approximation

The mean-field approximation restricts variational Bayes to fully factorized densities and obtains component-wise updates through coordinate ascent, with closed-form updates available under an exponential-family condition.

B. The mean-field approximation

  • Choosing fully factorized densities for Q yields the mean-field approximation.Source: B. The mean-field approximation · p. 6
  • The mean-field free energy leads to an iterative coordinate-ascent procedure that updates each qj(xj) while holding the other components fixed.The update requires solving an integral unless the stated conditional-distribution condition holds.Source: B. The mean-field approximation · p. 6
  • When each conditional p(xj, y|x\j) belongs to the same exponential family, the sufficient statistic parameterizes the family and supports the component updates.The family includes jointly Gaussian and multinomial distributions.Source: B. The mean-field approximation · p. 6

C. The Bethe approach

The Bethe approach approximates a posterior by designing consistent cluster marginals that preserve its dependency structure. On trees, minimizing the Bethe free energy recovers the true cluster marginals.

C. The Bethe approach

  • The factor graph represents variables and factors, while choices of inner clusters range from singleton variables to grouped supernodes.The figure illustrates full, partial, and no factorization.Source: Figure 1 · p. 6, C. The Bethe approach · p. 6
  • The approximation is built from nonnegative, normalized, mutually consistent cluster marginals rather than by designing the joint q(x) directly.The clusters follow the posterior's factorization structure; inner clusters partition x.Source: C. The Bethe approach · pp. 6–7
  • For a tree-structured posterior, minimizing the Bethe free energy recovers the true cluster marginals when only the stated marginal-consistency constraints are imposed.The section identifies the tree-structured expression as the Bethe free energy.Source: C. The Bethe approach · p. 7
  • The Bethe free energy can approximate the Gibbs free energy, and minimizing it can be interpreted as locally matching the true posterior.Its minimization is subject to linear marginal constraints and involves convex KL terms and concave entropies.Source: C. The Bethe approach · p. 7

D. Belief propagation

Belief propagation computes or approximates posterior marginals through messages on a factor graph; expectation propagation offers a more flexible approximation. Their fixed points have distinct Bethe-free-energy interpretations, and neither method is guaranteed to converge.

D. Belief propagation

  • On tree-structured factor graphs, one forward and backward message pass yields the true marginals.In hidden Markov models, this is known as the forward-backward algorithm.Source: D. Belief propagation · p. 7
  • On loopy graphs, iterated BP gives approximate beliefs, and convergence is not guaranteed; exact marginal computation is NP-hard.Despite this, the passage reports that LBP is often accurate and has applications including turbo and LDPC decoding, Markov random fields, multiuser detection, and compressive sensing.Source: D. Belief propagation · p. 7
  • LBP fixed points coincide with stationary points of the constrained Bethe free energy.The Lagrangian derivation makes the stationary-point multipliers equivalent to fixed-point log-messages.Source: D. Belief propagation · p. 7

E. Expectation propagation

  • EP replaces a factor's site approximation with the true factor, projects the resulting cavity distribution onto an exponential family, and updates the site.EP and expectation consistent (EC) fixed points correspond to Bethe-free-energy stationary points under weak, moment-matching consistency.Source: E. Expectation propagation · p. 8
  • For exponential-family factors closed under marginalization, EP is equivalent to the sum-product algorithm up to message schedule; for generic factors, it approximates that algorithm.EP updates all outgoing directions simultaneously, whereas the sum-product algorithm updates one direction per factor at a time; EP is not guaranteed to converge.Source: E. Expectation propagation · p. 8

F. Approximate message passing

Approximate message passing (AMP) approximates belief propagation for a separable generalized linear model with a fully factorizable prior. Its large-system updates are computationally efficient, with exactness and convergence properties depending on the matrix and model conditions.

F. Approximate message passing

  • AMP derives from LBP on a factor graph for a separable generalized linear model with a fully factorizable prior and observation likelihood.The hidden transform output is z = Ax.Source: F. Approximate message passing · p. 9
  • Each AMP iteration uses mean and variance evaluations, multiplications by A and A^T, and relatively few iterations, making it computationally efficient, especially with fast transform implementations.Examples include fast Fourier and discrete wavelet transforms.Source: F. Approximate message passing · p. 9
  • In the large-system limit with a unique state-evolution fixed point, AMP's marginal posterior approximations are exact for i.i.d. sub-Gaussian A.In this limit, AMP is characterized by scalar state evolution.Source: F. Approximate message passing · p. 9
  • For generic A, AMP fixed points are stationary points of a large-system Bethe free energy, but AMP is not guaranteed to converge.Damping helps for generic prior and likelihood, while theoretical guarantees are lacking; a globally convergent double-loop method is reported for strictly log-concave prior and likelihood.Source: F. Approximate message passing · p. 9

IV. OPTIMIZATION METHODS

The optimization section formulates MAP estimation and stochastic optimization problems, then describes computational strategies for optimizing expected losses. These include empirical-loss minimization and sequential stochastic-approximation methods.

A. Optimization problem

  • MAP estimation in many signal-processing applications can be formulated as an optimization problem involving a data-fit term and a regularizing term.Examples include a Gaussian-noise least-squares criterion and an ℓ1 sparsity-promoting measure.Source: A. Optimization problem · p. 9
  • Stochastic optimization minimizes an expected loss that is often impractical to compute because the expectation is high-dimensional and its probability measure is usually unknown.The section assumes convex, Lipschitz-differentiable losses for the subsequent presentation.Source: B. Optimization algorithms for solving… · p. 10, A. Optimization problem · p. 10

B. Optimization algorithms for solving stochastic problems

  • One strategy minimizes empirical loss from a finite observation set; another processes identically distributed samples sequentially in stochastic approximation to produce iterates converging to a solution.The section begins its algorithm review with online-learning extensions of stochastic gradient descent and then adaptive-filtering methods.Source: B. Optimization algorithms for solving… · p. 10
  • With gradient estimates available at each iteration, stochastic forward-backward is a strategy for solving the stochastic optimization problem.It is also called the stochastic proximal gradient algorithm.Source: 1) Online learning methods based on SGD · p. 10

1) Online learning methods based on SGD:

This section surveys stochastic forward-backward (SFB) methods for online learning, their convergence behavior, and approaches for handling nonsmooth objectives and accelerating updates.

2) Adaptive filtering methods:

The section covers stochastic methods for adaptive filtering and large-scale deterministic optimization, including incremental-gradient approaches and their trade-offs.

2) Adaptive filtering methods:

  • For time-varying adaptive-filtering problems, affine projection uses multiple recent observations in a mini-batch-like formulation to accelerate convergence.Source: 2) Adaptive filtering methods · p. 11
  • Sparse adaptive-filtering solutions can be pursued with proportionate methods, penalized stochastic subgradient or proximal methods, and feasibility-based approaches [115].Source: 2) Adaptive filtering methods · p. 11

C. Stochastic algorithms for solving deterministic optimization problems

1) Incremental gradient algorithms:

  • SAGA solves (51) when g is not necessarily smooth using a proximity operator; SVRG and semi-stochastic gradient descent take a full-gradient step every K ≥ 1 iterations, reducing memory at the expense of more gradient evaluations.Source: 1) Incremental gradient algorithms · pp. 11–12
  • Finito and some MISO variants store averages of component variables; MISO also has convergence guarantees when the nonsmooth term is nonzero.Source: 1) Incremental gradient algorithms · p. 12

2) Block coordinate approaches:

Random block-coordinate methods apply proximal updates to blockwise objectives; the section also situates these methods within broader simulation–optimization connections.

2) Block coordinate approaches:

  • The stochastic primal-dual proximal algorithm accommodates blockwise regularizers decomposed into two convex terms and updates activated blocks using proximal steps [137].Source: 2) Block coordinate approaches · p. 12
  • With positive block-activation probabilities independent of iteration, the stochastic block algorithm converges almost surely and requires no matrix inversion [137].Source: 2) Block coordinate approaches · p. 12

V. AREAS OF INTERSECTION: OPTIMIZATION-WITHIN-MCMC AND MCMC-DRIVEN

  • The paper identifies optimization-within-MCMC and MCMC-driven optimization as areas of overlap between stochastic simulation and optimization.Source: §V · p. 13

A. Riemannian manifold MALA and HMC

The section connects optimization tools with MCMC, describing geometry-aware and proximal proposals, optimization-driven Gaussian sampling, and possible future combinations of computational methods.

A. Riemannian manifold MALA and HMC

  • Riemannian MALA and HMC use position-dependent covariance metrics to adapt proposals to target geometry, linking metric choice to gradient preconditioning [20, 21, 31, 105].Source: A. Riemannian manifold MALA and HMC · p. 13

B. Proximal MCMC algorithms

  • Proximal MALA is presented as a stable option for log-concave targets, including nonsmooth image models, while proximal HMC has empirical promise but incompletely understood convergence.Source: B. Proximal MCMC algorithms · p. 13

C. optimization-driven Gaussian simulation

  • Optimization-driven Gaussian simulators replace costly Cholesky sampling with a randomized minimization; approximate conjugate-gradient solves can be corrected by an MH step [156, 159–161].Source: C. optimization-driven Gaussian… · pp. 13–14

VI. CONCLUSIONS AND OBSERVATIONS

  • The conclusion anticipates more adaptable methods that combine simulation, variational approximations, and optimization to address varied models, datasets, inference needs, accuracy, and computation times.Source: §VI · p. 14

Related papers

Loading 1505.00273v4…