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

Deming Song; Chi Kin Lam

math.STOct 12, 2026

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

Authors: Deming Song, Chi Kin Lam

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

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.

Figures & tables

Panel of Figure 1 — Fig. 1: One map, three count laws: simulated spectra against $\mathcal{T}_{c}$ predictions under the two-point weight law $\rho=\tfrac{1}{2}\delta_{1/2}+\tfrac{1}{2}\delta_{3/2}$ , with an identity population and Gaussian entries ( $N=1000$ , $d=800$ , $c=0.8$ , $n_{\mathrm{rep}}=20$ ). Zero atoms are drawn as separate point masses at the origin and are not merged into the density; all three panels share both axes. The three schemes separate as predicted, with second moments $2.000$ , $2.800$ and $2.400$ . The exactly uniform profile is omitted, since there residual resampling reproduces the pre-resampling matrix itself and the two panels would coincide exactly, which is the content of Corollary 24 ; see Table I . The corresponding count probability mass functions are reported in the supplementary material (S.25).

		$m_{2}$		$\nu(\{0\})$		$\mu_{Q}(\{0\})$
Profile	Scheme	empirical	theory	empirical	theory	empirical	theory
uniform	pre	$1.8039\pm 0.0012$	$1.800$	$0$	$0$	$0$	$0$
uniform	multinomial	$2.6118\pm 0.0074$	$2.600$	$0.36805\pm 0.00195$	$0.367879$	$0.21006\pm 0.00244$	$0.209849$
uniform	residual	$1.8039\pm 0.0012$	$1.800$	$0$	$0$	$0$	$0$
two-point	pre	$2.0011\pm 0.0019$	$2.000$	$0$	$0$	$0$	$0$
two-point	multinomial	$2.7985\pm 0.0103$	$2.800$	$0.41215\pm 0.00230$	$0.414830$	$0.26519\pm 0.00288$	$0.268538$

TABLE I: Experiment E1: pre-registered spectral quantities against theory. Empirical values are means over

n_{\mathrm{rep}}=20

independent repetitions, reported with one standard error. Here

\nu(\{0\})

denotes the count zero mass and

\mu_{Q}(\{0\})

the induced spectral atom. Under the uniform profile the residual row reproduces the pre-resampling row exactly, and not merely to within the reported error. The first spectral moment is

1.000

to within Monte Carlo error in every row and is omitted.

Fig. 2: Two weight profiles with exactly equal ESS, of value

640

, and statistically indistinguishable second spectral moments, but macroscopically different null spaces, under multinomial resampling with

c=0.8

N=1000

and

n_{\mathrm{rep}}=30

. The spectral atoms differ by

0.061

against a pre-registered prediction of

0.059

, a separation of nineteen standard errors. Any diagnostic based on ESS reports the two configurations as identical.

Quantity	Profile $A$	Profile $B$
$\mathrm{ESS}$ (exact)	$640$	$640$
$m_{2}$ empirical	$3.0559\pm 0.0101$	$3.0397\pm 0.0161$
$m_{2}$ theory	$3.05$	$3.05$
$\nu(\{0\})$ empirical	$0.47717\pm 0.00143$	$0.42823\pm 0.00215$
$\nu(\{0\})$ theory	$0.476287$	$0.429007$
$\mu_{Q}(\{0\})$ empirical	$0.34646\pm 0.00179$	$0.28529\pm 0.00268$

TABLE II: Experiment E3: identical ESS with different null spaces. Empirical values are means over

n_{\mathrm{rep}}=30

repetitions, reported with one standard error. ESS is verified as an exact identity and is not estimated.

Panel of Figure 5 — Fig. 3: Vanishing weight heterogeneity does not imply vanishing residual randomization, in accordance with Theorem 10 . The second-order deviation $\frac{1}{N}\sum_{i}(\lambda_{i}-1)^{2}$ vanishes at rate $1/N$ in all three constructions, with the dotted line giving the reference slope. The uniform construction is omitted from this panel and marked as identically zero in the legend, since its deviation vanishes exactly at every $N$ and cannot be displayed on a logarithmic axis. Over the same range, $R_{N}/N$ converges to the three distinct limits $0$ , $0.4$ and $1$ . The two panels are to be read together: the simultaneous vanishing of weight heterogeneity and persistence of randomization constitutes the content of Theorem 10 . Since the endpoint construction keeps all weights below $2$ , the effect originates in proximity to the integer grid rather than in heavy tails.

Construction	$N$	$R_{N}/N$	zero fraction	$b_{2,N}$	$\frac{1}{N}\sum(\lambda_{i}-1)^{2}$
uniform	all	$0$	$0$	$1$	$0$
	(theory)	$0$	$0$	$1$	—
interior	$256$	$0.3984$	$0.15408\pm 0.00089$	$1.3963\pm 0.0037$	$2.59\times 10^{-3}$
	$16384$	$0.4000$	$0.14835\pm 0.00012$	$1.3998\pm 0.0005$	$4.07\times 10^{-5}$
	(theory)	$0.4$	$0.147152$	$1.4$	$\to 0$
endpoint	$256$	$0.9961$	$0.36859\pm 0.00135$	$2.0034\pm 0.0062$	$3.89\times 10^{-3}$

TABLE III: Experiment E4: count-level quantities for the three constructions of Theorem 10 , at the endpoints of the sweep; the full sweep

N=2^{8},\dots,2^{14}

is tabulated in the supplementary material (S.26). For the uniform construction the counts are deterministic, so that all entries are exact and carry no Monte Carlo error.

Panel of Figure 7 — Fig. 4: The atom-free window of Corollary 23 , at $N=1024$ , $d=819$ and $c=0.7998$ , with the interior construction at $\alpha=0.5$ . The value of $\alpha$ differs from that of Fig. 3 , where $\alpha=0.4$ ; the larger value places $c$ near the centre of the window $(p_{\mathrm{multi}},p_{\mathrm{res}})=(0.632,0.816)$ . All three panels share both axes. The pre-resampling spectrum recovers $\mathrm{MP}(c)$ . Multinomial resampling carries a zero atom of empirical mass $0.217$ against the predicted $0.210$ . Residual resampling carries no atom: within this window it retains full rank with probability tending to one, whereas multinomial resampling has already annihilated a fixed fraction of directions.

Fig. 5: End-to-end check of Theorem 12 : directly simulated spectrum under the two-point population

H=\frac{1}{2}\delta_{1/2}+\frac{1}{2}\delta_{3/2}

against the

H\boxtimes\mathcal{T}_{c}(\operatorname{Poi}(1))

prediction, with the zero atom drawn separately. The two computation routes agree to a maximum Stieltjes deviation of

5.1\times 10^{-4}

Spectral Methods

Spectral methods use eigenvalues, eigenvectors, and frequency decompositions to analyze data, graphs, operators, and learning algorithms.

See all 237 papers

Oct 16, 2026

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

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.

Deming Song, Chi-Kin Lam, Kefeng Li +3

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

Particle Filtering Spectral Regularization

Ask PDF

May 1, 2026

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

The ensemble Gaussian mixture filter (EnGMF) is a powerful, convergent particle filter capable of medium-to-high dimensional non-linear filtering. The EnGMF relies on a resampling step that can generate physically unrealistic posterior samples, that would subsequently produce physically meaningless forecasts. This work introduces the discriminator-informed resampling procedure, that augments the posterior resampling step with a discriminator that accepts or rejects candidate particles based on their physical plausibility. In this work these discriminators are learned through a normalizing flow approach. Numerical experiments on both the Ikeda map and the Lorenz '63 system show that discriminator informed resampling procedure consistently reduces error relative to the standard EnGMF in low-ensemble regimes.

Zain Jabbar, Andrey A. Popov

Particle Filtering Bayesian Filtering Data Assimilation

Ask PDF

Oct 8, 2026

Differentiable Systematic Resampling for Variational Sequential Monte Carlo

Particle filters are a standard tool for nonlinear state estimation, but their resampling step is discrete, preventing gradient-based learning in variational sequential Monte Carlo. We introduce Differentiable Systematic Resampling (DSR), a temperature-controlled relaxation of systematic resampling, that preserves the CDF-ordered, banded structure of systematic resampling while enabling full gradient flow. DSR converges to exact systematic resampling as the temperature vanishes, and we prove a pointwise exponential convergence rate for the induced bias. Compared to optimal-transport-based differentiable resampling, DSR avoids iterative solvers and has substantially lower computational overhead. Experiments on stochastic dynamical systems and real-world handwriting data show that DSR achieves comparable or superior filtering and dynamics learning performance.

Fredrik Cumlin, Saikat Chatterjee

Department of Information Science, KTH Royal Institute of Technology, Stockholm, Sweden

Variational Monte Carlo Particle Filtering

Ask PDF

Abstract

Spectral Methods

Explore similar work

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

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

Differentiable Systematic Resampling for Variational Sequential Monte Carlo