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

Regularized free deconvolution for spectral repair of resampling distortion in high-dimensional particle filters
Oct 16, 2026Deming Song, Chi-Kin Lam, Kefeng Li +3Particle Filtering Spectral Regularization
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
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 16, 2026J/K move · Enter open · S save

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

Deming Song, Chi-Kin Lam, Kefeng Li, Hui Yu+2

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

Open paper AskPDF arXiv

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.

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