Source-linked AI summary
Sharp failure rates for the bootstrap particle filter in high dimensions
Peter Bickel, Bo Li, Thomas Bengtsson
TL;DR
High-dimensional particle filters can suffer weight collapse, motivating rigorous conditions for when the maximum importance weight approaches one. The paper proves Gaussian-filter results under weaker covariance-eigenvalue assumptions and shows that collapse is governed by effective dimension, with ensemble sizes needing exponential growth in the relevant dimension.
Problem
Particle filters can produce highly variable importance weights and collapse in high-dimensional systems, while earlier analyses imposed restrictive assumptions on prior covariance eigenvalues.
Method
The paper rigorously analyzes maximum importance weights in a Gaussian particle filter and weakens prior eigenvalue assumptions through effective-dimension analysis.
Results
Unless n grows super-exponentially in d′, the Gaussian particle filter exhibits weight collapse; the maximum sample weight converges to unity under the stated conditions.
Takeaways & Limitations
Collapse depends on effective dimension rather than absolute dimension, so systems with growing vector dimension can avoid collapse when their effective dimension remains controlled.
Takeaways & Limitations
The effective-dimension conclusions assume commensurate nonzero eigenvalues, and the analysis eschews the complication of double-array eigenvalue settings.
Abstract
from arXiv · showhide
We prove that the maximum of the sample importance weights in a high-dimensional Gaussian particle filter converges to unity unless the ensemble size grows exponentially in the system dimension. Our work is motivated by and parallels the derivations of Bengtsson, Bickel and Li (2007); however, we weaken their assumptions on the eigenvalues of the covariance matrix of the prior distribution and establish rigorously their strong conjecture on when weight collapse occurs. Specifically, we remove the assumption that the nonzero eigenvalues are bounded away from zero, which, although the dimension of the involved vectors grow to infinity, essentially permits the effective system dimension to be bounded. Moreover, with some restrictions on the rate of growth of the maximum eigenvalue, we relax their assumption that the eigenvalues are bounded from above, allowing the system to be dominated by a single mode.
1. Introduction
Particle filters combine models and data through Monte Carlo reweighting, but their importance weights can collapse in high dimensions. This paper rigorously characterizes collapse and shows that effective dimension, rather than absolute dimension, governs the phenomenon.
- Particle filters estimate posterior state distributions by Monte Carlo sampling and sequentially condition on data and system dynamics.
- Importance weights from likelihood-based reweighting are the paper’s primary object of study as functions of system dimension and sample size.
- High-dimensional particle filters may require large ensembles and frequent resampling, yet still become unstable and collapse onto a single point mass.
- The paper makes earlier Gaussian weight-collapse conjectures fully rigorous and identifies effective dimension, rather than absolute dimension, as the governing quantity.
2. Model setting
The particle filter propagates a prior ensemble, updates weights using the likelihood when observations arrive, and resamples to approximate the posterior. The paper studies why these weights become highly uneven in large Gaussian systems.
- The filter represents the evolving state distribution with an ensemble drawn from the prior and propagates particles using the system dynamics.
- When new data arrive, Bayes’ theorem adjusts particle weights according to how close their associated sample points are to the observations.
- The Bayes update reweights prior samples by their likelihood and can convert them into a posterior sample through resampling with replacement.
- The analysis specializes to Gaussian prior and likelihood distributions and focuses on the resulting Bayes update.
- The formal setting uses n sample points in R^d, with both ensemble size n and system dimension d treated as large.
- Highly variable weights can yield estimates collapsed onto a point mass, with max(w_i) approximately 1, especially in high-dimensional systems.
3. Gaussian case
The Gaussian analysis expresses particle-filter weights through the singular values of cov(HX), then characterizes when the maximum weight converges to one. The results distinguish bounded effective dimension, where collapse need not occur, from regimes where collapse occurs unless the ensemble grows super-exponentially.
- Model and weight representation: The Gaussian model uses a linear observation equation with Gaussian proposal and independent Gaussian noise, normalized without loss of generality to identity noise covariance and zero prior mean.The data model is Y = HX + ε, with p(X) Gaussian and p(ε) Gaussian.
- Model and weight representation: The likelihood-weight exponent is written using the singular values λ1, …, λd′ of cov(HX), after an orthogonal transformation QT HX = DV.The transformed state coordinates are standard normal, and the conditional transformed variables are Gaussian.
- Collapse regime: Proposition 3.1 establishes convergence of the normalized denominator quantity, with 2 log n E(Tn,d) tending to 1 under its stated conditions.This convergence is used to establish weight collapse in the Gaussian case.
- Collapse regime: Unless n grows super-exponentially in d′, Proposition 3.2 implies that the maximum importance weight converges to unity under its additional Gaussian assumptions.The proposition sharpens the convergence rate relative to the earlier result discussed in.
- Effective dimension: The effective dimension is defined through the singular values of cov(HX), so large ambient dimension alone need not determine collapse.The analysis explicitly identifies effective dimension as the quantity that really matters.
- Effective dimension: When the eigenvalue condition in case (i) holds, there is no weight collapse and the importance weights have the correct expectation with vanishing variance.The alternative case (ii) yields convergence of 2 log n E(Tn,d′) to 1 and hence collapse.
- Eigenvalue conditions: The eigenvalue formulation permits slower collapse than Proposition 3.2 suggests, and the infinite-sequence requirement can be weakened to uniform boundedness above.The authors also restrict the main formulation to an infinite eigenvalue sequence rather than a double array, although the arguments can be modified.
Appendix
The appendix develops uniform normal approximations and verifies the conditions needed to prove the main asymptotic result. It then decomposes the key integral and identifies the interval supplying its dominant contribution.
- Approximation lemmas: The appendix introduces Edgeworth expansion-type uniform normal approximations for the cdf and density of sums of independent random variables.These lemmas provide the groundwork for Proposition 3.1.
- Approximation lemmas: Lemma A.1 supplies the cdf approximation used in Proposition 3.1, while Lemma A.2 supplies a corresponding density approximation under bounded-density conditions.The density approximation is uniform for x ≥ 0 with x = o(B_d/K_d), where K_d is the maximum of the relevant parameters.
- Condition verification: The required Lyapunov conditions hold with probability tending to 1 for the Gaussian construction described in the appendix.The appendix also notes that the boundedness condition on the component densities does not hold for the Gaussian–Gaussian variables Z_j, although a two-term Gaussian convolution satisfies it.
- Proof of Proposition 3.1: Uniformity of the o(1) terms and bounded convergence yield R_d(x) = (1/τ_d)(1 + o(1)) under the stated asymptotic conditions.The argument assumes x → −∞, |x| < ε_dτ_d, and |x|Δ_n,d → ∞.
- Proof of Proposition 3.1: The middle interval, represented by II_n,d, is the dominating part of the decomposed integral.The proof combines this contribution with bounds for the remaining two parts to obtain the desired result.