Importance Sampling: Intrinsic Dimension and Computational Cost

1.1 Our Purpose

• The paper frames importance sampling as approximating a target probability measure with weighted proposal samples, measuring cost by worst-case expectation error and linking it to ρ, effective sample size, and measure distances.Here ρ is the second moment of dµ/dπ under the proposal and is essentially the χ2 divergence.Source: §1.1 · p. 2
• The paper shows that intrinsic dimensions, rather than state or nominal dimension alone, relate to ρ and absolute-continuity breakdown, and transfers these insights from inverse problems to standard and optimal particle-filter proposals.The framework addresses high-dimensional and singular-parameter limits, including state dimensions of order 10^9 and small-noise regimes.Source: §1.1 · pp. 3–4

1.2 Organization of the Paper and Main Contributions

• The main contributions are non-asymptotic error bounds for bounded test functions, connections between intrinsic dimension and posterior-prior absolute continuity, and improved understanding of optimal proposals in filtering.Theorem 2.1 interprets error through ρ, effective sample size, probability-measure metrics, and asymptotic results; Theorem 3.8 supports function-space inference when intrinsic dimension is finite and ρ is moderate.Source: §1.2 · pp. 4–5

1.3 Literature Review

• The literature review situates the framework within work on ρ, intrinsic dimension, absolute continuity, and small-noise limits, while noting that the applications developed here are linear Gaussian and that nonlinear extensions remain open.The paper’s general theory is broader than its linear Gaussian inverse-problem and filtering applications, which enable explicit calculations and insight.Source: §1.3 · pp. 6–7

1.4 Notation

• The notation distinguishes measure-indexing subscripts, sample-related superscripts, vector coordinates, and the law Pv of a random variable.Expectations and variances are written with respect to a measure, with suffixes omitted when unambiguous.Source: §1.4 · pp. 7–8

2.1 General Setting

• Importance sampling estimates target expectations under µ using samples from proposal π and the autonormalized weighted particle measure µN.The particle approximation µN is a random probability measure whose weights determine the approximation of µ.Source: §2.1 · p. 8
• The required particle count N quantifies computational cost through the quality of the approximation µN to the target µ.The framework asks how large N must be to achieve a small approximation error.Source: §2.1 · p. 8

2.2 A Non-asymptotic Bound on Particle Approximation Error

• The central quantity ρ is the second moment of the Radon–Nikodym derivative of µ with respect to π, and ρ ≥1.The lower bound follows from the Cauchy–Schwarz inequality.Source: §2.2 · p. 9
• For bounded test functions, the non-asymptotic theorem bounds both estimator bias and mean square error with constants proportional linearly to ρ.The theorem assumes µ is absolutely continuous with respect to π and has a square-integrable density.Source: §2.2 · p. 9
• For |φ| ≤1, the bounds are useful only when they improve on the trivial error bounds of 2 for absolute error and 4 for MSE.The theorem extends directly to functions with another known uniform bound.Source: §2.2 · p. 9
• The resulting bounds motivate keeping ρ/N small to obtain accurate importance sampling approximations.This heuristic guides the paper’s subsequent analysis of ρ in various limits.Source: §2.2 · p. 9
• The theorem applies directly to bounded-function tasks such as probability estimation and rare event simulation, but unbounded test functions require additional weight-moment assumptions.For example, an importance sampling estimator of µ(g2) can have infinite variance when g has a third but not fourth moment under π.Source: §2.2 · p. 9

2.3 Connections, Interpretations and Extensions

• Although ρ determines sample requirements through the second moment, the section links it to monitoring quantities and notes that other measures can matter in broader analyses.The discussion explicitly frames ρ as important for importance-sampling difficulty while cautioning against interpreting all behavior solely through it.Source: §2.3 · p. 9, §2.3.4 · p. 11

2.3.1 Asymptotic Consistency

• The asymptotic convergence result agrees precisely with Theorem 2.1 under the relevant finite-moment condition for bounded test functions.The section contrasts this asymptotic result with the finite-sample theorem and notes the weaker moment requirement of the asymptotic formulation.Source: §2.3.1 · p. 10

2.3.2 Effective Sample Size

• The effective sample size satisfies 1 ≤ ess ≤ N, attaining N for equal weights and 1 when one weight is one and all others are zero.For large particle numbers, ρ−1 quantifies the proportion of particles effectively represented by ess, supporting its interpretation as an effective sample size.Source: §2.3.2 · p. 10

2.3.3 Probability Metrics

• The required particle count scales exponentially with Kullback–Leibler divergence and linearly with χ2 divergence between proposal and target.Theorem 2.1 also contrasts with an asymptotic N −1/2 convergence rate under weaker moment assumptions.Source: §2.3.3 · p. 11, §2.3.4 · p. 11

2.3.4 Beyond Bounded Test Functions

• For broader test-function classes, non-asymptotic bias and MSE bounds require stronger assumptions on importance weights, and their constants involve moments beyond ρ.In Bayesian inverse problems, the stated conditions can yield O(N −1) convergence for test functions satisfying an additional moment condition.Source: §2.3.4 · pp. 11–12

2.4 Behaviour of the Second Moment ρ

• Importance sampling errors converge as the square root of ρ/N, motivating analysis of how this convergence breaks down near singular limits.The section focuses on high-dimensional problems and measure concentration caused by small parameters in the likelihood.Source: §2.4 · p. 12

2.4.1 High State Space Dimension and Absolute Continuity

• ρd=(ρ1)d with ρ1>1, so exponentially many particles are required as dimension d increases to maintain accurate importance sampling.The product-limit target and proposal become mutually singular, making importance sampling undefined at d=∞.Source: §2.4.1 · p. 13
• High-dimensional collapse reflects loss of absolute continuity in the infinite-dimensional limit, not product structure alone; diminishing likelihood sensitivity can yield well-behaved limits.The paper connects this perspective to later inverse-problem and filtering sections.Source: §2.4.1 · p. 13

2.4.2 Singular Limits

• For fixed-dimensional problems, small parameters can also induce mutual singularity, with ρ growing algebraically and requiring at least ǫ−1 particles.This conclusion uses a twice-differentiable h with a unique nondegenerate minimum and a proposal density with bounded first derivative.Source: §2.4.2 · pp. 13–14

2.5.1 Metrics Between Random Probability Measures

• Theorem 2.1 bounds the MSE of the random, generally biased particle estimator and interprets this bound as a distance between the target and approximation measures.The analysis uses a distance for random probability measures that reduces to total variation when the measures are nonrandom.Source: §2.5 · p. 14, §2.5.1 · p. 14
• Theorem 2.1’s bound is sharp for large N, while ρ is more tractable than covering-number constants and links sample complexity to χ2 and Kullback-Leibler divergences.The discussion indicates that N should grow linearly with Dχ2(µ∥π) or exponentially with DKL(µ∥π).Source: §2.5.1 · pp. 14–15
• ρ alone cannot universally determine error for unbounded test functions, although bounded-second-moment accuracy requires N of order χ2 divergence and hence of order ρ.Theorem 2.3’s constants depend on the problem through the Marcinkiewicz-Zygmund inequality, while [91] supplies the necessary-order result.Source: §2.5.1 · p. 15

2.5.3 Effective Sample Size, and the Case of Infinite Second Moment

• When the proposal has infinite second moment, the largest normalized weight can still vanish as N grows, but heavy-tailed weights can prevent effective sample size from growing linearly with N.For weights with density proportional to γ^−a−1, 1 < a < 2, the effective sample size does not grow linearly with N.Source: §2.5.3 · p. 15

2.5.4 Large State Dimension, and Singular Limits

• In high-dimensional settings, if N does not grow exponentially with dimension d, the maximum weight converges to 1 and the effective sample size is 1, exemplifying importance-sampling collapse.This agrees with the paper’s heuristic that ρ grows exponentially with d; proposed remedies include tempering and Kalman-based combinations, whose applicability remains under study.Source: §2.5.4 · p. 16

3. IMPORTANCE SAMPLING AND INVERSE PROBLEMS

• The section’s main result, Theorem 3.8, proves equivalence among finite intrinsic dimension, posterior absolute continuity with respect to the prior, and finite ρ.The analysis also closes with singular-limit results and a literature review.Source: §3 · p. 16

3.1 General Setting

• The inverse-problem setting models noisy linear observations of an unknown in a separable Hilbert space, with Gaussian noise and prior, and uses the posterior as the Bayesian solution.The framework includes finite-dimensional linear regression and infinite-dimensional deconvolution, while ill-posedness motivates regularization.Source: §3.1 · p. 17

3.2 Intrinsic Dimension

• The operator A quantifies prior–posterior covariance differences, motivating intrinsic dimensions τ and efd whose traces can be finite even in infinite-dimensional problems.efd is bounded by nominal dimension in finite dimensions, and efd and τ are finite simultaneously; both are finite when K has finite rank.Source: §3.2 · pp. 18–19

3.3 Absolute Continuity

• Finite intrinsic dimensions are equivalent to posterior absolute continuity with respect to the prior, ensuring finite ρ and effective sample size proportional to N.Theorem 3.8 links efd < ∞, τ < ∞, forward-image regularity, and posterior absolute continuity; under these conditions, Theorem 2.1 bounds effective sample size.Source: §3.3 · pp. 20–21

3.4 Large Nominal Dimension and Singular Parameter Limits

• The cost parameter ρ can be lower-bounded through intrinsic dimensions and eigenvalues, separating exponential dependence on large-eigenvalue counts from algebraic dependence on eigenvalue magnitude.The analysis considers clustered spectra and simultaneously diagonalizable asymptotics to relate ρ to τ, efd, and eigenvalue size.Source: §3.4 · p. 21, §3.4.1 · p. 21

3.4.1 Spectral Jump

• In the spectral-jump regime, τ ≈ Ck and efd ≈ k, while importance-sampling particle requirements grow exponentially with the number k of large eigenvalues and algebraically with C.This distinguishes the effect of intrinsic dimensionality from the magnitude of the dominant eigenvalues.Source: §3.4.1 · p. 21

3.4.2 Spectral Cascade

• Table 1 shows that ρ deteriorates algebraically for finite-dimensional small-noise limits, exponentially with growing intrinsic dimension, and factorially in infinite-dimensional small-noise or joint limits.Absolute continuity is lost as d →∞ with β ≤1, as β approaches 1 when d = ∞, and as γ →0; Table 1 provides corresponding lower bounds on ρ and particle counts.Source: §3.4.2 · p. 23, Table 1 · p. 24

3.5 Discussion and Connection to Literature

• The discussion situates the framework among finite- and infinite-dimensional inverse problems, including Radon, heat-equation, Laplace-transform, deconvolution, and Bayesian regression analyses.It also points to prior literature on Gaussian measures, posterior formulae, and Bayesian or classical treatments of inverse problems.Source: §3.5 · p. 24

3.5.1 Examples and Hilbert Space Formulation of Inverse Problems

• The framework applies beyond compact operators: the countable-eigenvalue assumption includes compact A and the non-compact case A = I.This provides a Hilbert-space formulation covering both compact and selected non-compact settings.Source: §3.5.1 · p. 24

3.5.2 The Operator A: Centrality and Assumptions

• The operator A preserves the intrinsic dimensions under equivalent formulations, while boundedness of A corresponds to bounded S, S∗, or SS∗ and marks the borderline for prior-induced regularization.Compact SS∗ shrinks data components associated with small eigenvalues, whereas unbounded SS∗ leaves high-frequency components essentially unregularized.Source: §3.5.2 · p. 25

3.5.3 Notions of Dimension and Interpretations

• The effective dimension efd measures posterior-prior covariance change relative to the prior, while τ measures the analogous precision-based change and both quantify data informativeness.efd is also interpreted as the effective dimension of the Bayesian linear model and is bounded by nominal dimension.Source: §3.5.3 · pp. 25–26

4.5 Discussion and Connection to Literature

• The analysis covers only sequential importance sampling without resampling interactions, which are less relevant for the two-time-unit systems studied but necessary for long data-assimilation sequences.In general nonlinear, non-Gaussian problems, the optimal proposal is usually not implementable, although it is implementable in this Gaussian framework and is only locally optimal.Source: §4 · p. 26, §4.5 · pp. 33–34

4.1 General Setting

• The filtering step targets Pv1,v0|y1 and compares the standard proposal Pv1|v0Pv0 with the optimal proposal Pv1|v0,y1Pv0.The standard proposal propagates before observing, whereas the optimal proposal assimilates the observation before propagating conditioned dynamics.Source: §4.1 · p. 27, Figure 1 · p. 29

4.1.1 Standard Proposal

• Filtering with the standard proposal is equivalent to an inverse problem for v1, with proposal covariance Σ = MPM* + Q, observation operator K = H, and noise covariance Γ = R.The target-proposal density depends only on v1, allowing v0 to be ignored in the associated inverse problem.Source: §4.1.1 · pp. 27–28

4.1.2 Optimal Proposal

• Filtering with the optimal proposal is equivalent to an inverse problem for v0, with proposal covariance Σ = P, observation operator K = HM, and noise covariance Γ = HQH* + R.The method first assimilates y1 and then propagates the conditioned measure, requiring sampling from Pv1|v0,y1.Source: §4.1.2 · p. 28

4.2 Intrinsic Dimension

• Intrinsic dimensions τst, efdst, τop, and efdop are defined from proposal-specific operators Ast and Aop, assumed bounded with countable spectra.These operators transfer the inverse-problem framework to standard and optimal filtering proposals.Source: §4.1 · p. 27, §4.2 · p. 29

4.3 Absolute Continuity

• Finite intrinsic dimension, finite effective dimension, and absolute continuity are equivalent for each proposal, while the second-moment quantities ρst and ρop determine relative filtering efficiency.The optimal proposal loses its advantage when the dynamics are deterministic, and under stated conditions both proposals collapse simultaneously.Source: §4.3 · pp. 30–31
• The optimal proposal can have finite intrinsic dimension while the standard proposal has infinite intrinsic dimension, so importance sampling remains well-defined for the former but collapses for the latter.This occurs when observations provide more information about v1 than v0; an explicit example gives τst = ∞ and τop < ∞.Source: §4.3 · p. 31

4.4 Large Nominal Dimension and Singular Parameter Limits

• As observational noise r → 0, the standard proposal degenerates algebraically, whereas the optimal proposal remains stable for fixed signal noise q and can scale well at stationarity even when q ∝ r.In the large-dimensional limit, both proposals can have exponentially growing ρ when the target and proposal are mutually singular, although examples allow finite ρop with exponentially growing ρst.Source: §4.4 · p. 33

• The framework links the second moment of the target-to-proposal density to non-asymptotic particle-error bounds and diverse importance-sampling inputs and outputs.It revisits importance sampling on general state spaces while targeting inverse problems and filtering with high- or infinite-dimensional states and data.Source: §5 · p. 35
• Performance in Bayesian linear regression and ill-posed inversion is governed by intrinsic dimension rather than state-space or data dimension.Intrinsic dimension measures the relative strength of prior and likelihood, not whether the prior is concentrated on a finite-dimensional manifold.Source: §5 · p. 35
• The filtering analysis focuses on one-step importance sampling rather than interacting particles, introducing intrinsic-dimension notions and comparing alternative schemes.Source: §5 · p. 35
• Future work should develop practical algorithm-design recommendations and extend intrinsic-dimension analysis to non-Gaussian priors, nonlinear operators, and unknown hyperparameters.Linearising nonlinear models around a reasonable value, such as the posterior mean, is identified as one possible extension.Source: §5 · p. 35

6.1 Gaussian Measures in Hilbert Space

• A trace-class covariance operator admits a countable eigenbasis, enabling Gaussian draws in an infinite-dimensional separable Hilbert space.The covariance is self-adjoint, positive-definite, and trace class.Source: §6.1 · p. 40
• The Karhunen–Loève expansion represents Gaussian draws as mean shifts plus independent standard-normal coefficients along covariance eigenfunctions.The trace-class assumption ensures the resulting draw lies in the Hilbert space almost surely.Source: §6.1 · p. 40
• Eigenvalue decay controls almost-sure sample regularity: faster decay produces smoother draws, while Brownian-bridge draws have Hölder and Sobolev regularity below one half.This smoothness interpretation depends on the eigenbasis; the Fourier basis links decay to Hölder and Sobolev regularity.Source: §6.1 · p. 40
• Finite-dimensional truncations converge to the Hilbert-space Gaussian, but infinite-dimensional Gaussian measures can be mutually singular despite finite-dimensional equivalence.In finite dimensions, strictly positive covariance Gaussians are equivalent; the infinite-dimensional limit requires stringent conditions.Source: §6.1 · pp. 40–41
• The Cameron–Martin space comprises mean shifts preserving Gaussian equivalence, yet is a compact, measure-zero subset of the Hilbert space under the centered Gaussian measure.For the Brownian bridge, it is the boundary-vanishing Sobolev space with first derivative in H, whereas draws have less than one Sobolev derivative.Source: §6.1 · p. 41
• When the covariance is not trace class, an injective bounded operator can enlarge the state space so the modified covariance becomes trace class.For Gaussian white noise, this construction uses negative Sobolev spaces, while absolute continuity and the Cameron–Martin space remain space-independent.Source: §6.1 · p. 41
• Lemma 6.2 characterizes almost-sure Hilbert-space membership of Gaussian draws through a summability condition on the expansion variances.The lemma treats independent standard-normal coefficients in an orthonormal basis and proves necessity and sufficiency.Source: §6.1 · p. 42

• The inverse problem assumes η ∼ N(0, Γ) and u ∼ N(0, Σ), with Γ and Σ bounded, self-adjoint, positive-definite operators on H.Source: §6.2 · p. 43
• If Γ or Σ is not trace class, the corresponding variable lies almost surely in a larger space Y or X rather than H, with H compactly embedded into these spaces.Source: §6.2 · p. 43
• K is assumed extendable to X so that Ku + η is meaningful in Y; this is automatic for simultaneously diagonalizable operators and can also follow from embeddings between operator-power domains [3, Section 7].Source: §6.2 · p. 43

6.3 Proofs Section 2

• The particle approximation μN is defined from samples drawn from the proposal π.Source: §6.3 · p. 43

6.3.1 Proof of Theorem 2.1

• Theorem 2.1 is proved by decomposing bias and MSE terms, using unbiasedness, |φ| ≤1, Markov’s inequality, and (a + b)^2 ≤2(a^2 + b^2).Source: §6.3.1 · pp. 43–44
• C ≈10.42 replaces C = 12 for the bias when the proof’s indicator threshold is optimized.Source: §6.3.1 · p. 44

6.3.2 Proof of Theorem 2.3

• Theorem 2.3’s MSE proof uses [37, Lemma 2], whose key novelty is introducing θ ∈(0, 1) rather than only bounding φ by its maximum.Source: §6.3.2 · p. 45
• Theorem 2.3 is completed by combining Hölder’s inequality, the Marcinkiewicz-Zygmund inequality, moment decompositions, and Markov’s inequality for the bias.Source: §6.3.2 · pp. 45–46

6.4 Proofs Section 3

• Lemma 6.5 establishes trace-class identities, cyclicity, norm bounds, similarity invariance, and eigenvalue comparisons for bounded and Hilbert-Schmidt operators.These properties underpin the subsequent finite- and infinite-dimensional proofs.Source: §6.4 · p. 47

6.4.1 Proofs of subsection 3.2

• Propositions 3.5–3.7 are proved using trace cyclicity and eigenvalue transformations, with Proposition 3.5 extending to Hilbert spaces under boundedness and positive-definiteness conditions.The Hilbert-space extension requires Lemma 6.5(v) to justify the trace-commutativity steps.Source: §6.4.1 · pp. 48–49

6.4.2 Proofs of subsection 3.3

• Theorem 3.8 is proved by connecting operator trace-class conditions with Gaussian likelihood equivalence and posterior absolute continuity, then recovering the operator condition through Cameron–Martin and spectral arguments.The proof shows the posterior exists almost surely and is absolutely continuous with respect to the prior under the stated conditions.Source: §6.4.2 · pp. 49–50

6.4.3 Proofs of subsection 3.4

• The analysis derives an expression for ρ by rewriting expectations and taking a corresponding ratio, then obtains parameter scalings by comparing positive sums and integrals across dominant regimes.In small-noise regimes, the first sum dominates, while for large d and β approaching 1, the second dominates; joint large-d, small-γ scalings are established similarly.Source: §6.4.3 · pp. 50–52

Proofs Section 4

• A preliminary lemma justifies using the cyclic property of traces in the infinite-dimensional calculations underlying Theorem 4.5.For A = S∗S, the argument rewrites Tr(S∗S) as Tr(SS∗), using boundedness conditions to apply the trace lemma.Source: §6.5 · p. 53
• Using the equivalence in Table 2, τ_st and τ_op admit equivalent expressions.Source: §6.5 · p. 53
• Theorem 4.5 uses positivity of R and semidefiniteness of HQH∗, together with Lemma 6.5(vi), to establish the required inequalities.When Tr(HQH∗R−1) < ∞, an operator norm bound yields the converse direction of the equivalence via Lemma 6.5(vi).Source: §6.5 · p. 53