SMC (sequential Monte Carlo)

Sequential Monte Carlo (SMC), also known as particle filtering, is a powerful technique used for state estimation and inference in dynamic systems. It is particularly useful in scenarios where the underlying system evolves over time and is characterized by uncertainty.

SMC algorithms are designed to estimate the state of a system given a sequence of observations. The state refers to the set of variables that describe the system's internal state, and the observations are measurements or data collected at different time points. The goal of SMC is to compute the posterior distribution of the system's state at each time step, given the observations up to that point.

The main idea behind SMC is to represent the posterior distribution using a set of weighted samples, referred to as particles. Each particle consists of a state hypothesis and an associated weight. The weight indicates the likelihood of the particle being the true state given the observations. Initially, the particles are sampled from the prior distribution, which represents the initial beliefs about the system's state before any observations are available.

The SMC algorithm proceeds iteratively through time, updating the particles at each time step based on the new observation. The process can be summarized as follows:

1. Initialization: Generate an initial set of particles from the prior distribution. Assign equal weights to each particle.
2. Prediction: Propagate each particle to the next time step based on the system dynamics. This involves applying a transition function that models how the state evolves over time.
3. Weighting: Evaluate the likelihood of each particle by comparing the predicted state with the observed data at the current time step. The likelihood is obtained from the observation model, which describes the relationship between the state and the observations.
4. Resampling: Resample particles based on their weights. Particles with higher weights have a higher probability of being selected, while particles with lower weights are less likely to be chosen. The resampling step helps concentrate particles in regions of higher likelihood, improving the representation of the posterior distribution.
5. Estimation: Compute the estimate of the state based on the resampled particles. This can be done by taking the weighted average or using more sophisticated techniques like the maximum likelihood estimate.
6. Repeat steps 2-5 for subsequent time steps until all observations have been processed.

The key advantage of SMC is its ability to handle non-linear and non-Gaussian systems, as well as time-varying dynamics. By representing the posterior distribution with a set of particles, SMC captures the complexity of the true distribution and provides a flexible framework for inference.

However, SMC also has some challenges. As the number of time steps increases, the number of particles needed to maintain an accurate representation of the posterior grows exponentially. This can become computationally demanding, especially for high-dimensional problems. Various techniques, such as importance sampling, resample-move, and sequential Markov chain Monte Carlo, have been developed to address these challenges and improve the efficiency of SMC algorithms.

Overall, SMC is a versatile and widely used approach for state estimation and inference in dynamic systems, finding applications in fields such as robotics, finance, and signal processing.