Resampling changes particle filters spectrum in new detailed ways
Spectral Costs of Multinomial and Residual Resampling in High-Dimensional Particle Ensembles: A Free-Probability Analysis
Machine Learning
Summary
Particle filters track many possible scenarios to estimate changing situations, but they need resampling to keep working well. This paper studies how resampling changes certain mathematical properties of these particles, especially their spread and diversity. The authors analyze two common resampling methods and show how each alters the spectrum of particle data differently. Their findings explain why some summary statistics don’t capture these spectral changes and provide exact formulas to understand them better.
What this means in practice
- •For signal processing engineers: Optimize particle filter designs by precisely understanding how resampling alters particle diversity and spectrum for better tracking accuracy.
- •For financial risk modelers: Improve simulations in high-dimensional models using new spectral insights about resampling to better estimate uncertainty and risk.
Authors
Deming Song, Chi Kin Lam
Abstract
Resampling is the standard remedy against weight degeneracy in particle filters, yet its effect on the spectrum of the particle second-moment matrix is poorly understood. We study a single resampling step for a d-dimensional ensemble of N particles with d/N -> c. For any unbiased scheme, the resampled empirical second-moment matrix dominates its pre-resampling counterpart in conditional convex order, while the conditional mean is preserved; the excess second spectral moment equals the Frobenius energy of the resampling perturbation. For multinomial resampling, the empirical count law converges to the mixed-Poisson law determined by the limiting weight law. For residual resampling, the count law is determined by the joint limit of floor-fraction pairs: we classify all residual limits of weight sequences converging to delta_1 in law as a one-parameter family between the deterministic identity and the full multinomial count law. Each count law feeds a common covariance-side spectral map, yielding exact consequences: a closed-form zero-eigenvalue mass, a rank-and-spectral-gap transition with a universal lower edge benchmark, computable regular edges, unbounded right support, and scheme-specific second-moment costs. The effective sample size determines one bulk statistic but cannot determine the limiting spectrum. Pre-registered numerical experiments confirm the theory at every level.