betaFeedback

WorksComputer Science

Certifiable inversion of resampling-induced spectral distortion in high-dimensional particle filters

Abstract

This paper formulates and solves the inverse problem of recovering the pre-resampling spectrum of a particle filter's ensemble covariance from the importance weights and the observed spectrum alone. Resampling controls weight degeneracy, but in high dimensions it also distorts that spectrum: the distortion is a free multiplicative convolution with a law computable from the weights, so the repair is a deconvolution. We first extend the forward spectral law to random importance weights by conditioning on the weights together with the realized offspring counts rather than on the weights alone, which makes the distortion law deterministic at the observed data and gives the zero-atom mass of the limiting law a direct reading as an effective-dimension proxy for the second-order information the filter has lost. Second, a regularized free deconvolution inverts the distortion with an explicit error budget at a fixed resolution scale, and a computable forward residual certifies when the model behind it is violated. Injectivity makes the inverse identifiable but not stable, so the budget rests on a resolution-restricted condition number whose positivity we prove, and is vacuous below that resolution rather than concealed in a hypothesis. Third, the repaired spectrum enters only as the preconditioner of a Metropolis-adjusted rejuvenation move, so spectral error changes the mixing constants and not the invariant target, and the full cycle obeys a geometrically summable error recursion whose abstention term is governed by when abstentions fall rather than how many occur. Pre-registered simulations confirm the forward law, an order-of-magnitude reduction of spectral error, and the abstention law. The repair recovers eigenvalue laws, not eigenvectors.

Introduction

A particle filter can report a healthy effective sample size (ESS) while its covariance estimate has already collapsed. The ESS is a scalar summary of the weight distribution; the object that the filter’s own propagation, its proposal adaptation and any downstream Gaussian summary actually consume is the spectrum of the ensemble second-moment matrix. In the proportional regime d/N→cd/N \to c these two objects decouple. In the companion paper [1] we showed what a single resampling step does to the spectrum: the limiting spectral distribution factorizes into a population channel and a count channel,

μS=H⊠Tc(ν),\mu_S = H \boxtimes\mathcal{T}_c(\nu),

with exact zero-atom masses, a rank-and-spectral-gap transition and exact second-moment costs. The present paper solves the associated inverse problem, which is ill-posed in a way that is specific to this setting and which we make precise.

The zero-atom mass m0m_0 of the limiting law has an interpretation that we develop in § 2.5 and which motivates everything that follows. Asymptotically a fraction m0m_0 of the limiting eigenvalue mass sits at zero, so only a fraction 1−m01-m_0 of the spectrum carries nonzero second-order information, and (1−m0)d(1-m_0)d is an effective-dimension proxy for spectral preconditioning and condition-number control. Weight-only summaries such as the ESS do not determine the limiting spectral law or its zero-atom mass, so they cannot say how much was lost. This is a structural information gap, not a claim that the ESS never responds to degeneration: the monitor experiment of § 5.5 shows synchronized dynamics, and even when the ESS alarms it cannot identify the distortion law or say how to repair it.

The forward map from population spectra to observed spectra is injective, so two population spectra can produce two different observed spectra under one and the same weight vector. A diagnostic that is a function of the weights alone therefore takes the same value on both, which is the precise sense in which spectral information is necessary rather than convenient (Lemma 3).

The inverse problem is harder than invertibility alone suggests. The forward map, a free multiplicative convolution with the distortion law, has no uniformly Lipschitz inverse on any class containing nearby atoms, so no error budget can be carried by the inverse itself. We therefore work at a resolution scale θ\theta and control a resolution-restricted condition number, whose positivity we prove; the budget is informative above θ\theta and vacuous below it, and we say so rather than concealing the floor in a hypothesis.

The motivation for a repair carrying its own diagnostics comes from the contrast with linear filtering. The Kalman filter [2] propagates an error covariance, a computable certificate of its uncertainty that drives the gain and bounds its precision. Particle filters have no counterpart. Our contribution is to give them one, and to delimit when it is trustworthy. Raising NN does not by itself remove the distortion: in the proportional limit it changes cc and hence the distortion law, and the pre-registered limit W1(H0⊠T,H0)W_1(H_0 \boxtimes T,H_0) remains bounded away from zero over the range studied. A different scheme changes TT, which once known can still be divided out at a fixed resolution scale. The repair buys spectral accuracy at fixed NN, the budget that binds in high dimensions.

The main theorems hold in an exogenous-weight generalized sample-covariance model (G1–G4), covering exogenous importance weights, sample-split and cross-fitted weighting, and conditionally exogenous local approximations (§ 2.3). Its boundary has three regions, located numerically in § 5.3: where the repair is certified, where the mismatch diagnostic stays dormant because the distortion law is unchanged even though the weights are not exogenous, and where neither applies. The fluctuation matrix is Gaussian in the main theorems and universality is left open. No claim about end-to-end filtering accuracy is made beyond the stated spectral and invariance results.

Prior work and what is missing

Resampling and weight degeneracy. Weight degeneracy and the effective sample size go back to [3], with SMC methodology surveyed in [4, 5], convergence theory in [6] and the Feynman–Kac framework in [7]; resampling schemes are compared in [8, 9], and in high dimensions the particle filter collapses unless the ensemble grows exponentially with an effective dimension [10, 11]. These analyses quantify resampling through Monte Carlo variance and weight degeneracy; its spectral effect on high-dimensional ensembles is the subject of [1], whose forward law we invert.

Rejuvenation moves and ensemble filters. Resample–move [12] applies a target-invariant Markov kernel after resampling, formalized for SMC samplers in [13] and embedded in particle MCMC in [14]; geometric ergodicity under drift and minorization is established in [15], and adapting the proposal covariance to the empirical covariance is adaptive Metropolis [16]. Ensemble transform methods [17], optimal-transport formulations of the ensemble Kalman filter [18], hybrid ensemble Kalman and particle filters [19], differentiable resampling [20], the feedback particle filter [21] and interacting-particle samplers [22, 23] avoid the multiplicative count channel altogether. Our addition is a proposal preconditioner whose spectrum has been corrected for resampling distortion, confining spectral error to the mixing constants, and we keep standard resampling rather than replacing it.

Inverse problems and regularization. The unknown here is a measure rather than a finite-dimensional parameter, the forward map is a free multiplicative convolution with a law that is itself estimated, and the inverse is injective but not Lipschitz. This places the problem within the classical theory of ill-posed problems and regularization [24, 25, 26]; the statistical and Bayesian viewpoints [27, 28] apply as well, since the distortion law is estimated from the weights and the repair carries both an error budget and a mismatch diagnostic. What replaces a singular-value decomposition or a discrepancy principle is a resolution-restricted condition number, a budget valid above that resolution, and a forward residual certifying model mismatch.

Spectrum estimation and free deconvolution. The Marchenko–Pastur law [29] and its generalization [30] describe the sample spectrum as a deformation of the population spectrum; El Karoui [31] inverts this relation, Ledoit and Wolf [32] derive nonlinear shrinkage, and [33] reviews eigenvalue cleaning. Free deconvolution with a known factor is developed for signal processing in [34, 35], with consistent covariance-eigenvalue estimation in [36] and a survey in [37]. Our inversion differs in that the factor is a random count-law channel built from the weights and in that it carries an error budget and a mismatch diagnostic; nonlinear shrinkage is the external baseline of § 5.2.

The paper makes three contributions.

  1. The conditioning object and what it costs. That spectral law extends to random importance weights when one conditions on the weights together with the realized counts, and we delimit when this conditioning is legitimate. Conditioning on the weights alone leaves the count diagonal random. Because the forward map is injective, this also fixes what no weight-only diagnostic can see: the zero-atom mass of the resulting law quantifies the second-order dimension the filter has lost.

  1. Regularized inversion with an explicit budget. A regularized free-deconvolution estimator is consistent with a local error budget at a fixed resolution scale. Injectivity gives no Lipschitz inverse, so the budget rests on a resolution-restricted condition number whose positivity we establish, together with a computable forward residual that certifies violation of the model.

  1. Diagnosed, target-preserving use. The repaired spectrum is used only as a Metropolis-adjusted preconditioner, so spectral error enters the mixing constants and not the invariant target, and the full-cycle error obeys a recursion whose abstention term is governed by the geometric abstention load.

The repair recovers eigenvalue laws, not eigenvectors, and this boundary separates the tasks the tool serves from those it does not (Table 1).

Depends on the eigenvalue law aloneAlso depends on the eigenbasis
spectral preconditioning; condition-number control;subspace estimation; dimension reduction;
trace- and determinant-based detection statisticsmodal decomposition

Table 1. What the repaired spectrum can and cannot support. The lift of § 4.1 recovers a population eigenvalue law, not the population eigenbasis.

Throughout, dd is the state dimension, NN the ensemble size and c=d/Nc=d/N.

Section 2 states the forward problem and identifies the object to be conditioned on; Section 3 develops the inversion, its condition number and its certificate; Section 4 treats the target-preserving use of the recovered spectrum and the full cycle; Section 5 reports the pre-registered experiments. Proofs of the main results are in the supplementary material.

The forward problem and the conditioning object

Notation

Ensemble and second-moment matrices. X=[x1,…,xN]∈Rd×NX=[x_1,\ldots,x_N]\in\mathbb{R}^{d\times N}; weights wi≥0w_i\ge0, ∑iwi=1\sum_i w_i=1; λi=Nwi\lambda_i=Nw_i; ρN=1N∑iδλi\rho_N=\frac{1}{N}\sum_i\delta_{\lambda_i}; m^=Xw\hat m=Xw; Sw=∑iwixixi⊤S_w=\sum_iw_ix_ix_i^\top; Swu=Sw−m^m^⊤S_w^u=S_w-\hat m\hat m^\top; counts n=(n1,…,nN)n=(n_1,\ldots,n_N) satisfying (A1) ∑ini=N\sum_i n_i=N a.s. and (A2) E[ni∣X,w]=Nwi\mathbb{E}[n_i\mid X,w]=Nw_i; m^r=1NXn\hat m_r=\frac{1}{N}Xn; Sru=1N∑inixixi⊤S_r^u=\frac{1}{N}\sum_i n_ix_ix_i^\top; Sr=Sru−m^rm^r⊤S_r=S_r^u-\hat m_r\hat m_r^\top; ki=⌊λi⌋k_i=\lfloor\lambda_i\rfloor, ui=frac⁡(λi)u_i=\operatorname{frac}(\lambda_i), RN=∑iuiR_N=\sum_i u_i. For a symmetric matrix AA, μA\mu_A denotes its empirical spectral distribution (ESD).

Metrics. dBLd_{\mathrm{BL}} is the bounded-Lipschitz metric and W1W_1 the 1-Wasserstein metric. The fixed-band Stieltjes discrepancy between finite measures μ,ν\mu,\nu on R\mathbb{R}, at bandwidth h>0h>0 over the segment [0,ξhi][0,\xi_{\mathrm{hi}}], is

dSt(μ,ν):=dSt(h,ξhi)(μ,ν):=sup⁡{∣mμ(z)−mν(z)∣:z=ξ+ih, ξ∈[0,ξhi]}(1)d_{\mathrm{S t}}(\mu,\nu):=d_{\mathrm{S t}}^{(h,\xi_{\mathrm{hi}})}(\mu,\nu):=\sup\left\{\lvert m_\mu(z)-m_\nu(z)\rvert:z=\xi+ih,\ \xi\in[0,\xi_{\mathrm{hi}}]\right\} \tag*{(1)}

on the upper-half-plane branch Im⁡mμ>0\operatorname{Im}m_\mu>0, with mμ(z)=∫(t−z)−1μ(dt)m_\mu(z)=\int(t-z)^{-1}\mu(dt). Values on the segment determine μ\mu, and weak convergence implies uniform convergence there, so dStd_{\mathrm{S t}} is a metric adapted to the limit theorems below. The pair (h,ξhi)(h,\xi_{\mathrm{hi}}) is fixed in the theory (Remark 3); smaller hh is more sensitive to local differences, which is the bandwidth dependence of the activation zone (§ 5.5).

Free probability. ⊞\boxplus, ⊠\boxtimes are the free additive and multiplicative convolutions [38, 39, 40]. Tc(η)T_c(\eta) is the covariance-side spectral map, defined by cTc(η)+(1−c)δ0=Dc(η⊠MP⁡(1/c))cT_c(\eta)+(1-c)\delta_0=D_c(\eta\boxtimes\operatorname{MP}(1/c)) with MP the Marchenko–Pastur law [29], equivalently by the companion fixed-point equation z=−1/m(z)+∫t(1+ctm(z))−1η(dt)z=-1/m(z)+\int t(1+ctm(z))^{-1}\eta(dt). We write sT(z):=∫(1−zx)−1T(dx)s_T(z):=\int(1-zx)^{-1}T(dx) for the companion transform, Lμ(t):=∫e−txμ(dx)L_\mu(t):=\int e^{-tx}\mu(dx) for the Laplace transform, and νmulti(ρ):=MixPoi⁡(ρ)\nu_{\mathrm{multi}}(\rho):=\operatorname{MixPoi}(\rho), νres(π):=L(K+Poi⁡(U))\nu_{\mathrm{res}}(\pi):=\mathcal{L}(K+\operatorname{Poi}(U)) with (K,U)∼π(K,U)\sim\pi for the count laws.

Resolution scale and classes. θ>0\theta>0 is the resolution scale of the spectral inversion (§ 3.2), a scalar distinct from the count law ν\nu. Ha,b:=P([a,b])\mathcal{H}_{a,b}:=\mathcal{P}([a,b]) with 0<a<b<∞0<a<b<\infty, and U⊆Ha,b\mathcal{U}\subseteq\mathcal{H}_{a,b} is the certified class, the relative neighborhood of H0H_0 on which the condition number is evaluated; it is fixed exogenously and is never estimated from the data.

High-dimensional and spectral assumptions

References

  1. [1]D. Song and C.-K. Lam. Spectral costs of multinomial and residual resampling in high-dimensional particle ensembles: A free-probability analysis, 2026.arxiv.org/abs/2610.16680
  2. [2]R. E. Kalman. A new approach to linear filtering and prediction problems. Trans. ASME J. Basic Eng., 82(1):35–45, 1960.DOI
  3. [3]Augustine Kong, Jun S Liu, and Wing Hung Wong. Sequential imputations and Bayesian missing data problems. Journal of the American statistical association, 89(425):278–288, 1994.DOI
  4. [4]Arnaud Doucet, Adam M Johansen, et al. A tutorial on particle filtering and smoothing: Fifteen years later. In D. Crisan and B. Rozovskii, editors, The Oxford Handbook of Nonlinear Filtering, volume 12, pages 656–704. Oxford University Press, 2011.
  5. [5]J. S. Liu and R. Chen. Sequential Monte Carlo methods for dynamic systems. J. Am. Stat. Assoc., 93(443):1032–1044, 1998.DOI
  6. [6]Dan Crisan and Arnaud Doucet. A survey of convergence results on particle filtering methods for practitioners. IEEE Transactions on signal processing, 50(3):736–746, 2002.
  7. [7]P. Del Moral. Feynman–Kac Formulae. Springer, 2004.DOI
  8. [8]T. Li, M. Bolić, and P. M. Djurić. Resampling methods for particle filtering: Classification, implementation, and strategies. IEEE Signal Process. Mag., 32(3):70–86, 2015.DOI
  9. [9]R. Douc and O. Cappé. Comparison of resampling schemes for particle filtering. In Proc. 4th Int. Symp. Image and Signal Processing and Analysis (ISPA), pages 64–69, 2005.
  10. [10]T. Bengtsson, P. Bickel, and B. Li. Curse-of-dimensionality revisited: Collapse of the particle filter in very large scale systems. In Probability and Statistics: Essays in Honor of David A. Freedman, pages 316–334, 2008.DOI
  11. [11]C. Snyder, T. Bengtsson, P. Bickel, and J. Anderson. Obstacles to high-dimensional particle filtering. Mon. Weather Rev., 136(12):4629–4640, 2008.DOI
  12. [12]Walter R Gilks and Carlo Berzuini. Following a moving target—monte carlo inference for dynamic bayesian models. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 63(1):127–146, 2001.DOI
  13. [13]P. Del Moral, A. Doucet, and A. Jasra. Sequential Monte Carlo samplers. Journal of the Royal Statistical Society Series B: Statistical Methodology, 68(3):411–436, 2006.
  14. [14]Christophe Andrieu, Arnaud Doucet, and Roman Holenstein. Particle Markov chain Monte Carlo methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 72(3):269–342, 2010.DOI
  15. [15]Gareth O Roberts and Richard L Tweedie. Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms. Biometrika, 83(1): 95–110, 1996.DOI
  16. [16]H. Haario, E. Saksman, and J. Tamminen. An adaptive Metropolis algorithm. Bernoulli, 7(2):223–242, 2001.DOI
  17. [17]Sebastian Reich. A nonparametric ensemble transform method for Bayesian inference. SIAM Journal on Scientific Computing, 35(4):A2013–A2024, 2013.DOI
  18. [18]Amirhossein Taghvaei and Prashant G Mehta. An optimal transport formulation of the ensemble Kalman filter. IEEE Transactions on Automatic Control, 66(7):3052–3067, 2020.arxiv.org/abs/1910.02338
  19. [19]Marco Frei and Hans R Künsch. Bridging the ensemble kalman and particle filters. Biometrika, 100(4):781–800, 2013.DOI
  20. [20]A. Corenflos, J. Thornton, G. Deligiannidis, and A. Doucet. Differentiable particle filtering via entropy-regularized optimal transport. In International Conference on Machine Learning, pages 2100–2111. PMLR, 2021.arxiv.org/abs/2102.07850
  21. [21]Tao Yang, Prashant G Mehta, and Sean P Meyn. Feedback particle filter. IEEE Trans. Autom. Control, 58(10):2465–2480, 2013.
  22. [22]Q. Liu and D. Wang. Stein variational gradient descent. In Advances in Neural Information Processing Systems 29 (NeurIPS), pages 2138–2146, 2016.arxiv.org/abs/1608.04471
  23. [23]Alfredo Garbuno-Inigo, Franca Hoffmann, Wuchen Li, and Andrew M Stuart. Interacting langevin diffusions: Gradient structure and ensemble kalman sampler. SIAM Journal on Applied Dynamical Systems, 19(1):412–441, 2020.
  24. [24]A. N. Tikhonov and V. Y. Arsenin. Solutions of Ill-Posed Problems. V. H. Winston & Sons, 1977.DOI
  25. [25]Heinz Werner Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996.
  26. [26]Andreas Kirsch et al. An introduction to the mathematical theory of inverse problems, volume 120. Springer, 2011.
  27. [27]Jari P Kaipio and Erkki Somersalo. Statistical and computational inverse problems. Springer, 2005.DOI
  28. [28]Andrew M Stuart. Inverse problems: a bayesian perspective. Acta numerica, 19:451–559, 2010.DOI
  29. [29]Vladimir A Marčenko and Leonid Andreievich Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of the USSR-Sbornik, 1(4):457–483, 1967.DOI
  30. [30]Jack W Silverstein and Zhi Dong Bai. On the empirical distribution of eigenvalues of a class of large dimensional random matrices. Journal of Multivariate analysis, 54(2): 175–192, 1995.DOI
  31. [31]N. El Karoui. Spectrum estimation for large dimensional covariance matrices. Ann. Statist., 2008.
  32. [32]Olivier Ledoit and Michael Wolf. Nonlinear shrinkage estimation of large-dimensional covariance matrices. Ann. Statist., 2012.
  33. [33]Joël Bun, Jean-Philippe Bouchaud, and Marc Potters. Cleaning large correlation matrices: tools from random matrix theory. Physics Reports, 666:1–109, 2017.
  34. [34]Florent Benaych-Georges and Mérouane Debbah. Free deconvolution: from theory to practice. In Paradigms for Biologically-Inspired Autonomic Networks and Services, pages 201–224. EURASIP, 2008.
  35. [35]Oyvind Ryan and Mérouane Debbah. Free deconvolution for signal processing applications. IEEE Transactions on Information Theory, 53(5):1846–1850, 2007.arxiv.org/abs/cs/0701025
  36. [36]X. Mestre. Improved estimation of eigenvalues and eigenvectors of covariance matrices using their sample estimates. IEEE Trans. Inf. Theory, 54(11):5113–5129, 2008.DOI
  37. [37]R. Couillet and M. Debbah. Random Matrix Methods for Wireless Communications. Cambridge University Press, 2011.DOI
  38. [38]J. A. Mingo and R. Speicher. Free Probability and Random Matrices. Springer, 2017.
  39. [39]D. Voiculescu. Addition of certain noncommuting random variables. Journal of functional analysis, 66(3):323–346, 1986.
  40. [40]Hari Bercovici and Dan Voiculescu. Free convolution of measures with unbounded support. Indiana University Mathematics Journal, 42(3):733–773, 1993.
  41. [41]Benoît Collins and Camille Male. The strong asymptotic freeness of Haar and deterministic matrices. Ann. Sci. Éc. Norm. Supér. (4), 47(1):147–163, 2014.
  42. [42]Bradley Efron and Charles Stein. The jackknife estimate of variance. The Annals of Statistics, pages 586–596, 1981.DOI
  43. [43]L. Le Cam. An approximation theorem for the Poisson binomial distribution. Pacific J. Math., 1960.DOI
  44. [44]P. Biane. On the free convolution with a semi-circular distribution. Indiana University Mathematics Journal, pages 705–718, 1997.DOI
  45. [45]W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97–109, 1970.
  46. [46]Matthias Gelbrich. On a formula for the l² wasserstein metric between measures on euclidean and hilbert spaces. Mathematische Nachrichten, 147(1):185–203, 1990.DOI
  47. [47]G. O. Roberts and J. S. Rosenthal. Optimal scaling for various Metropolis–Hastings algorithms. Statist. Sci., 16(4):351–367, 2001.DOI

Paper details

vlnc:W_c7v2t5mr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents