Regularized free deconvolution for spectral repair of resampling distortion in high-dimensional particle filters

Deming Song; Chi-Kin Lam; Kefeng Li; Hui Yu; Xilin Li; Huagang Lin

cs.LGOct 16, 2026

Regularized free deconvolution for spectral repair of resampling distortion in high-dimensional particle filters

Authors: Deming Song, Chi-Kin Lam, Kefeng Li, Hui Yu, Xilin Li, Huagang Lin

Organizations: Macao Polytechnic University, Macao · College of Textile Science and Engineering, Wuyi University, Jiangmen, China · Guangdong Provincial Key Laboratory of Novel Polyamide 6 Functional Fiber Materials Research and Application, Jiangmen, China

Abstract

Resampling is the standard remedy for weight degeneracy in particle filters, but in high dimensions it distorts the spectrum of the ensemble covariance in a way that is computable from the importance weights. This paper studies the inverse problem: recovering the pre-resampling spectrum from the observed weights and the empirical spectrum alone, and using it without biasing the filter. We first show that the forward spectral law extends to random importance weights once one conditions on the weights together with the realized offspring counts, rather than on the weights alone. We then construct a regularized free-deconvolution estimator, prove its consistency with an explicit error budget at a fixed resolution scale, and certify model mismatch through a computable forward residual. The repaired spectrum enters the filter only as the preconditioner of a Metropolis-adjusted rejuvenation move, so that spectral error affects mixing efficiency but not the invariant target. For the full filtering cycle, we derive a geometrically summable error recursion under stable scalar dynamics and an explicit law for the cost of abstaining from repair. Pre-registered simulations show that the inversion reduces the spectral error by an order of magnitude, that the corrected preconditioner recovers about 90% of the oracle's sampling efficiency in an anisotropic regime, and that the cost of abstention depends on when abstentions occur rather than on how many. The repair recovers eigenvalue laws, not eigenvectors, and is certified only within an explicitly stated exogenous-weight regime.

Figures & tables

Fig. 1: The spectrally corrected filtering cycle and its error recursion. (a) One cycle: propagation (Section 8.2 ), selection by resampling, which acts as a free multiplicative distortion with the law

T_{k+1}

determined by the exogenous weights (Theorem 3 ), and regularized spectral inversion driven by the plug-in law

\widehat{T}_{k+1}

(Theorems 4 – 6 ). The supervisor accepts the repair or abstains and passes on the uncorrected spectrum (Proposition 3 , Algorithm 1, step 9). Solid arrows carry spectral laws, dashed arrows carry certificates and the control signal, and the dotted arrow marks the ideal law

\mu_{k+1}

, which is not computed. With the switch held on abstain, successive selections compound; on accept, each cycle is reset. (b) The first-order comparison system majorizing the error

\eta_{k}=W_{1}(H_{k}^{+},H_{k}^{\star,+})

: the recursion

\eta_{k+1}\leq\bar{a}^{2}\eta_{k}+\mathcal{B}^{\theta}_{k+1}

has pole

\bar{a}^{2}<1

(Theorem 8 (a)), where

\mathcal{B}^{\theta}_{k+1}

is the per-step budget capped at the resolution scale (Section 6.4 ). Panel (b) depicts an upper bound, not the actual error dynamics.

Fig. 2: Static spectral distortion and repair (EXP-1). (a) Empirical spectral distribution after resampling, pooled over 50 repetitions at

N=2000

\alpha=1

, against the predicted law

H_{0}\boxtimes\mathcal{T}_{c}(\nu)

for multinomial and residual resampling; markers on the vertical axis compare the empirical zero-atom mass (o) with the closed form (x). (b) Second spectral moment against the predicted count second moment, for the six weight-profile and scheme groups at

N=2000

; the line is the certificate of Corollary 2 . (c) Median

W_{1}

inversion error against

N

\alpha=1

for the oracle, conditional plug-in, and realized-count inverters (solid: multinomial; dashed: residual; bars: interquartile range); the dotted line is the pre-registered limit of the uncorrected spectrum.

Fig. 3: Diagnostic certificates and identifiability (EXP-2). (a) Mismatch statistic $\widehat{\varepsilon}_{\rm model}$ across the nine settings at $N=2000$ , $\alpha=1$ ; the statistic rises sharply only for the wrong mechanism and for strongly correlated particles. (b) Median inversion error against the zero-atom mass of the distortion law, $H=\delta_{1}$ , $N=1000$ , colored by $\log_{10}\widehat{\kappa}_{\rm inv}$ ; conditioning degrades as the zero atom grows (Remark 3 ).

Fig. 4: Identifiability and supervisor activity on the $(c,\alpha)$ grid. (a) Map level: median estimated condition number $\widehat{\kappa}_{\rm inv}$ ; conditioning degrades toward large $c$ and heavy-tailed weights (small $\alpha$ ), where the zero atom is largest. (b) Pipeline level: activation fraction of the comparative clause of the supervisor; the framed cell is the deployment setting of EXP-3, $(c,\alpha)=(0.75,3)$ . (c) Distribution of the supervisor’s decision ratio $\widehat{\mathcal{B}}_{N}/\widehat{\delta}_{\rm fb}$ over the 660 steps of EXP-3 (median $0.146$ , maximum $0.824$ ); no step crosses the activation threshold $1$ (dashed).

Fig. 5: Full-cycle behavior (EXP-3). (a) Median error

\eta_{k}=W_{1}(H_{k}^{+},H_{k}^{\star,+})

over 20 repetitions with interquartile bands, for no correction, conditional plug-in, oracle, and plug-in with supervisor; dotted lines mark the weight shocks. (b) Forced abstention with the same number of abstentions,

A_{K}=6

, clustered at the end of the horizon or spread uniformly. (c) Error against the geometric abstention load

\Lambda_{k}

, with the bound of Proposition 3 (red).

Preconditioner	$\kappa$	ESS/step	Acc.	ESS/s	$\max\|z\|$
$I$	42.4	$3.26\times 10^{-4}$	0.237	1355	3.23
$S_{r}^{c}+\varepsilon I$	19.6	$5.45\times 10^{-4}$	0.226	2242	1.60
lift $(\widehat{H})+\varepsilon I$	5.6	$8.72\times 10^{-4}$	0.237	2046	1.88
oracle $\Sigma+\varepsilon I$	2.4	$9.72\times 10^{-4}$	0.240	1794	2.41

Table 1: Metropolis preconditioning in Regime A (

d=225

c=0.15

\kappa(\Sigma)=50

r_{\rm obs}=200

). Condition number of the preconditioned posterior covariance, slowest-direction ESS per step, acceptance rate, ESS per second at equal wall clock, and the maximum

|z|

-score of the target-displacement test.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Fig. 6: Count-law checks. (a) Empirical probability mass function of the counts against the mixed Poisson law,

N=2000

\alpha=1

. (b) Heavy-tailed weights,

\alpha=0.3

, on logarithmic axes. (c) Empirical zero-atom share of the centered resampled matrix against the exact count-rank identity

1-(\#\{n_{j}>0\}-1)/d

(circles) and the limiting value of Corollary 2 (crosses); all points lie on the diagonal.

Fig. 7: Complete comparison for Proposition 1. (a) The active-column fraction

p_{s}

is ordered by the convex order and not by

r_{2}

; equal

r_{2}

can give different

p_{s}

. (b) Two laws with

r_{2}=2

and equal second moment produce different limiting spectra and zero atoms. (c) The scheme-specific excess over the weighted ensemble:

ca_{1}^{2}

for multinomial resampling and

ca_{1}^{2}\mathbb{E}_{\pi}U

for residual resampling.

Fig. 8: Inversion sensitivity. (a) The fixed regularization schedule

\gamma_{0}/N

against the scale-free schedule in the strong-anisotropy regime; dashed lines mark the true values. (b) Relative difference in

W_{1}

between the two schedules, per experiment and step. (c) Activation counts of the comparative clause under three versions of the discretization-floor estimate, at three bandwidths; version 3 is the one reported.

Fig. 9: Fallback error against

N

c=0.75

. (a) Median

\widehat{\delta}_{\rm fb}

with interquartile bands and bootstrap slope intervals, which contain zero for both weight profiles. (b) Worst grid-resolution ratio over repetitions; values above

1

indicate that the resolution cap is reached. (c) Dependence on the bandwidth.

Fig. 10: Ledoit–Wolf nonlinear shrinkage as an external baseline. (a) Median

W_{1}

error of each inverter, 900 paired draws. (b) Number of paired draws in which Ledoit–Wolf is closer to

H_{0}

than each inverter. (c)

W_{1}

error against the mass that Ledoit–Wolf assigns to the common null value.

Fig. 11: Burn-in diagnostics for the Metropolis chains of Table 1. (a) The Robbins–Monro step-size controller settles before the end of burn-in (dashed). (b) Tail drift ratio of each controller at the end of burn-in, against the pre-stated threshold

0.2

. (c) Burn-in length in units of the integrated autocorrelation time, per chain, against the pre-stated floor of five.

Fig. 12: Activation zone of the comparative clause. (a) Median decision ratio $\widehat{\mathcal{B}}_{N}/\widehat{\delta}_{\rm fb}$ on the $(c,\alpha)$ grid at the deployment bandwidth; large markers indicate activation. (b) Activated fraction against $c$ at three bandwidths.

Fig. 13: Passive monitor experiment. (a) ESS, zero-atom mass, and effective dimension relative to their steady-state means; dotted lines mark the weight shocks. (b) Zero-atom mass against ESS; steady and shock steps form two separated clusters on one curve. (c) Shock-to-steady ratios against the pre-registered threshold

1.5

for a silent ESS; the ESS falls by a factor of

3.23

, so the prediction fails.

Particle Filtering

Particle filtering estimates evolving hidden states by propagating and reweighting samples under nonlinear or non-Gaussian uncertainty.

See all 28 papers

Spectral Costs of Multinomial and Residual Resampling in High-Dimensional Particle Ensembles: A Free-Probability Analysis
Oct 12, 2026Deming Song, Chi Kin LamSpectral Methods Random Matrix Theory
the Faculty of Applied Sciences, Macao Polytechnic University, Macao, China
Learning Discriminators for Resampling in the Ensemble Gaussian Mixture Filter through a Normalizing Flow Approach
May 1, 2026Zain Jabbar, Andrey A. PopovParticle Filtering Bayesian Filtering
Differentiable Systematic Resampling for Variational Sequential Monte Carlo
Oct 8, 2026Fredrik Cumlin, Saikat ChatterjeeVariational Monte Carlo Particle Filtering
Department of Information Science, KTH Royal Institute of Technology, Stockholm, Sweden

Oct 12, 2026J/K move · Enter open · S save

Spectral Costs of Multinomial and Residual Resampling in High-Dimensional Particle Ensembles: A Free-Probability Analysis

Deming Song, Chi Kin Lam

the Faculty of Applied Sciences, Macao Polytechnic University, Macao, China

Spectral Methods Random Matrix Theory

Open paper AskPDF arXiv

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.

Abstract

Particle Filtering

Explore similar work

Spectral Costs of Multinomial and Residual Resampling in High-Dimensional Particle Ensembles: A Free-Probability Analysis

Learning Discriminators for Resampling in the Ensemble Gaussian Mixture Filter through a Normalizing Flow Approach

Differentiable Systematic Resampling for Variational Sequential Monte Carlo