Particle_filter - Wikiparency

# Particle filter A **particle filter** is a sequential Monte Carlo method for tracking the hidden state of a dynamical system as noisy, incomplete measurements arrive one at a time. It is built for problems that defeat the [[Kalman_filter]]: a state transition or an observation that is strongly nonlinear, or process and measurement noise that is not Gaussian, so that the posterior probability distribution of the state has no convenient closed form. Rather than propagating a mean and a covariance, a particle filter represents that distribution directly, as a population of candidate states, or "particles," each carrying a weight that records how well it currently explains the data. At each step every particle is advanced through the system's own dynamics, reweighted by how closely it now matches the newest measurement, and the population is periodically resampled so that particles with vanishing weight are discarded and likely ones are duplicated. Repeated over time, this predict-weight-resample cycle turns [[Estimation_theory|state estimation]] into a simulation problem: with enough particles, the weighted cloud approximates the true posterior to any desired accuracy, at a cost that scales with the number of particles rather than with the size of a probability grid. This article carries the Stochastic filter sketch, a one-dimensional Kalman-style filter that stands in for the linear-Gaussian special case a particle filter is built to go beyond; the reader tunes how erratic the hidden signal is against how noisy the sensor is and watches the estimate track a moving target it never observes directly. ## History The mathematical ancestor of the particle filter is the [[Monte_Carlo_method]] itself: replacing an integral or an expectation with the average of random samples, a technique formalized by Nicholas Metropolis and Stanisław Ulam in 1949 for problems, arising in neutron transport, that had no tractable closed form.[^metropolis49] Related resampling schemes for simulating branching random processes circulated earlier still, in physics and in population genetics, but they were not yet framed as a general solution to a filtering problem.[^citneed1] The particle filter as it is used in signal processing today dates to a single, widely cited paper: in 1993, Neil Gordon, David Salmond and Adrian Smith described a "bootstrap filter" that tracked a nonlinear, non-Gaussian state by sampling, weighting and resampling a population of points, and showed it outperforming an extended Kalman filter on a benchmark tracking problem.[^gordon93] Jun Liu and Rong Chen gave the wider class its most common name, sequential Monte Carlo, in a 1998 paper that placed the bootstrap filter inside a general importance-sampling framework and analyzed why resampling is necessary.[^liuchen98] The theoretical foundations of the field — the mean-field interacting-particle picture and the genealogical, Feynman-Kac formulation used to prove convergence — were developed over the following decade and gathered into a single treatment by Pierre Del Moral.[^delmoral04] ## The filtering problem The objective is to compute, at every time step, the conditional probability distribution of a system's unobserved state given every measurement received so far, its posterior distribution, rather than a single best guess. The system is described by a signal-observation model: a state that evolves under its own dynamics plus random process noise, `x(k) = f(x(k-1), w(k))`, and a measurement that depends on the current state plus random observation noise, `z(k) = h(x(k), v(k))`. Both f and h may be nonlinear, and the noise terms w and v may follow any distribution the modeller can sample from; the [[Kalman_filter|Kalman filter's]] linear-Gaussian case is the one instance of this model with an exact, closed-form answer. The posterior updates recursively in two stages. A prediction stage pushes the previous posterior through the state dynamics to obtain a prior for the new state, by the Chapman-Kolmogorov relation; a correction stage multiplies that prior by the likelihood of the new measurement and renormalizes, in words `posterior at k` is proportional to `likelihood of z(k) times prior at k`. This pair of integral equations, exact for any system, is the nonlinear filtering equation; the difficulty is that neither integral has a closed form once f, h or the noise is far from linear and Gaussian, which is exactly why a numerical, simulation-based method earns its place. A related but distinct idea is approximate Bayesian computation, which also estimates a posterior by simulation but targets models whose likelihood cannot be evaluated at all, only sampled from; it accepts simulated data close enough to the real observation, rather than weighting every particle by an exact likelihood. The Feynman-Kac formulation restates the nonlinear filtering equation as a flow of measures acted on by an alternating sequence of Markov transitions and likelihood-weighted reweightings, the same object that appears in path-integral treatments of physical systems; casting the problem this way is what let Del Moral prove that the particle approximation converges to the true filtering distribution as the particle count grows, and bound how fast.[^delmoral04] ## Particle filters A particle filter turns the two-stage nonlinear filtering equation into an algorithm on a finite population. Its general probabilistic principle is a cycle of mutation and selection recognizable from a [[Genetic_algorithm|genetic algorithm]] of the kind [[John_Henry_Holland]] introduced for optimization: particles are propagated, or mutated, through the state dynamics, then culled and replicated, or selected, in proportion to how well each one now fits the data, so that the population as a whole drifts toward the region of state space the measurements support. The particle interpretation of the filtering equation represents the posterior at step k by N particles and their normalized weights, and stands in for the true posterior with their weighted empirical distribution; an expectation under the posterior, such as the state's mean, is approximated by the weighted average over the population. This is a direct application of Monte Carlo principles, the same law of large numbers that lets a Monte Carlo integral converge on a value it cannot compute exactly: the more particles, the closer the weighted population sits to the distribution it represents, at the standard Monte Carlo rate of error shrinking with the square root of the particle count, a rate that, notably, does not depend on the dimension of the state, unlike a fixed grid over the same space. Some convergence results go further than this general rate. Under regularity conditions on f and h, the particle filter's estimate of the posterior mean is consistent at every fixed time step as the particle count grows, and, for filtering as opposed to smoothing problems, the constant in the error bound can be shown not to grow without limit over time, so a particle filter run for a long time does not necessarily need more particles than one run briefly.[^delmoral04] ## Genealogical trees and Unbiasedness properties Because resampling duplicates fit particles and discards poor ones, every surviving particle at step k descends from some particle at step zero along a specific line of ancestors; recording those lines turns the particle system into a genealogical tree. Tracing a particle's ancestry backward gives a cheap way to reconstruct a whole smoothed trajectory rather than just the state at the current time, but the tree has a well-known defect: because every resampling step prunes some lineages entirely, the ancestors of all surviving particles coalesce onto fewer and fewer distinct paths the further back one looks, until, after enough steps, every particle shares a single common ancestor. This path degeneracy makes a naive genealogical-tree smoother unreliable far from the present, which is why backward particle smoothers instead recompute smoothing weights through a separate backward recursion over the stored particle history rather than by reading the forward genealogy directly. A more surprising theoretical result concerns the likelihood itself. The particle filter's byproduct estimate of the marginal likelihood of the observed data, the normalizing constant discarded at each correction step, is an unbiased estimate of the true likelihood exactly, for any particle count greater than zero, not merely in the limit of many particles. This unbiasedness is what lets a particle filter be dropped directly into a Markov chain Monte Carlo sampler, in the particle Markov chain Monte Carlo family of methods, without biasing the sampler's target distribution.[^delmoral04] ## Sequential Importance Resampling (SIR) The most widely used particle filter is the sequential importance resampling algorithm, also called the Monte Carlo filter or the bootstrap filter after Gordon, Salmond and Smith's original paper.[^gordon93] It chooses the proposal distribution from which new particles are drawn to be the state's own transition density, the simplest choice available, so that each particle's incoming weight update collapses to the observation likelihood alone, `w(k) is proportional to w(k-1) times p(z(k) given x(k))`, and it resamples at every step rather than only when needed. Sequential importance sampling without that resampling step is the older and simpler idea, and it fails in a specific, well-understood way: because the same set of particles is reweighted step after step without ever being redrawn, the spread of the weights grows without bound, until one particle carries nearly all the weight and the rest contribute almost nothing to any estimate. The standard diagnostic is the effective sample size, `N_eff = 1 / sum(w_i^2)` for normalized weights, which falls from N toward one as the weights degenerate; resampling whenever N_eff drops below some fraction of N is the usual fix, at the cost of the reduced particle diversity that motivates the genealogical concerns above. Stripped to its steps, this "direct version" of the algorithm is: draw each new particle from the transition density given its parent; weight it by the likelihood of the current measurement; normalize the weights across the population; and resample the population in proportion to those weights before repeating. Every variant of the particle filter changes one of these four steps, a different proposal, a different weighting rule, or a different resampling schedule, without changing the cycle itself. ## Applications Particle filters are used wherever a system is tracked online from noisy sensor data and cannot be trusted to a linear-Gaussian model. In [[Robotics|robotics]], the FastSLAM family of algorithms runs a particle filter over robot trajectories, paired with a small linear filter per landmark, to solve simultaneous localization and mapping in roughly the time a plain particle filter over the trajectory alone would take.[^montemerlo02] [[Radar]] and [[Sonar]] trackers use particle filters to follow maneuvering targets whose motion is not well described by a single linear model; [[Econometrics]] and other applications of [[Estimation_theory|estimation]] use them to filter a [[Time_series|time series]] with stochastic volatility or regime changes that a Kalman filter cannot represent; and [[Bioinformatics]] and [[Genomics]] use them to track hidden ancestries and population states through evolutionary models. The same population-based idea underlies particle-filter methods inside [[Machine_learning|machine learning]] and [[Computer_vision|computer vision]], where it tracks an object in video whose appearance and motion both drift over time. ## Other particle filters Several variants trade the plain bootstrap filter's simplicity for better use of each particle. The auxiliary particle filter looks one step ahead before resampling, favoring particles likely to matter for the next observation rather than the current one. Rao-Blackwellized particle filters, of which FastSLAM is one example, apply the particle filter only to the part of the state that is genuinely nonlinear and solve the remaining linear-Gaussian part exactly with a [[Kalman_filter|Kalman filter]] conditioned on each particle, which needs far fewer particles than filtering the whole state by simulation. The unscented particle filter instead improves the proposal distribution itself, drawing it from an unscented Kalman filter run alongside each particle so that new particles land where the latest measurement actually pulls the state, rather than where the dynamics alone would place them. ## Microsims The Stochastic filter sketch carried on this page is the one-dimensional, linear-Gaussian case that a full particle filter is built to generalize beyond, shown here as a genuine [[Kalman_filter|Kalman filter]] running under its older name of stochastic filter: the canvas plots a hidden state as a random walk with drift (green), a noisy measurement of it (red), and the recursive minimum-variance estimate (cyan). Two sliders set the process noise variance Q, how erratic the true signal is allowed to be, and the measurement noise variance R, how noisy the sensor is taken to be; a third sets the playback speed. A HUD reports the current Kalman gain K, the weight the filter places on the newest measurement against its own prediction, together with the instantaneous error between the true and estimated state and the running root-mean-square error over the visible window. *Try:* Raise the measurement noise R relative to the process noise Q and watch the Kalman gain K fall in the sketch, as the filter learns to trust its own prediction of the drifting state over a sensor it now treats as unreliable. A three.js companion sim renders the general, nonlinear particle-filter case in more depth, showing a cloud of weighted hypotheses tracking a target through propagation, reweighting and resampling.  **Microsim — three.js (Wikitube framework), pending deploy:** *Particle filter: a cloud of hypotheses* will play here once `https://wikitube-3d-microsims.netlify.app/signal/Particle_filter.html` is live.  *Built from `MICROSIM_GUIDE/specs/sims/Particle_filter.json`; part of the [[Signal_processing]] set ([[PORTAL_Signal_Processing]]).*  ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Particle_filter) : [Wikitube](https://en.wikitube.io/wiki/Particle_filter) Skeleton mirrored at revision 1372329655. Prose, emphasis and the microsims are Wikitube's own. ## See also - [[Kalman_filter]] - [[Estimation_theory]] - [[Monte_Carlo_method]] - [[Wiener_filter]] - [[Genetic_algorithm]] - [[Robotics]] ## References Recursive Bayesian filtering, the law of large numbers behind Monte Carlo estimation, and the mechanics of importance sampling and resampling are standard results in estimation theory and are not separately footnoted here, per Wikitube style guide §6.1. The items below ground the article's names, dates and specific claims. [^metropolis49]: Metropolis, N.; Ulam, S. "The Monte Carlo Method." *Journal of the American Statistical Association*, vol. 44, no. 247, 1949, pp. 335-341. DOI: https://doi.org/10.1080/01621459.1949.10483310 [^citneed1]: Citation needed: a specific, dateable primary source (paper, report or patent) for the pre-1993 branching-particle and resampling heuristics in physics and population-genetics simulation that are usually credited as antecedents of the modern particle filter. [^gordon93]: Gordon, N. J.; Salmond, D. J.; Smith, A. F. M. "Novel approach to nonlinear/non-Gaussian Bayesian state estimation." *IEE Proceedings F (Radar and Signal Processing)*, vol. 140, no. 2, 1993, pp. 107-113. DOI: https://doi.org/10.1049/ip-f-2.1993.0015 [^liuchen98]: Liu, J. S.; Chen, R. "Sequential Monte Carlo methods for dynamic systems." *Journal of the American Statistical Association*, vol. 93, no. 443, 1998, pp. 1032-1044. DOI: https://doi.org/10.1080/01621459.1998.10473765 [^delmoral04]: Del Moral, P. *Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications.* Springer, 2004. ISBN 0-387-20268-4. DOI: https://doi.org/10.1007/978-1-4684-9393-1 [^montemerlo02]: Montemerlo, M.; Thrun, S.; Koller, D.; Wegbreit, B. "FastSLAM: A factored solution to the simultaneous localization and mapping problem." *Proceedings of the AAAI National Conference on Artificial Intelligence* (AAAI-02), 2002, paper AAAI02-089. https://cdn.aaai.org/AAAI/2002/AAAI02-089.pdf ## Bibliography - Christian Tiberius; Max Mulder. *Engineering Signal Analysis: From Fourier to filtering: Theory* (2026). Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory - Don Johnson. *Fundamentals of Electrical Engineering I* (2014). Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/fundamentals-of-electrical-engineering-1 ## External links - Stochastic filter, live sketch: https://editor.p5js.org/sciencenibber/full/WtAlQfMmS - Stochastic filter, editor fork: https://editor.p5js.org/sciencenibber/sketches/WtAlQfMmS