Source-linked AI summary
Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies
Jerrad Hampton, Alireza Doostan
TL;DR
Sparse Polynomial Chaos recovery requires sampling strategies with controlled coherence, especially for high-dimensional or high-order approximations. The paper derives Hermite and Legendre coherence bounds, proposes coherence-optimal Markov Chain Monte Carlo sampling, and reports similar or improved reconstruction accuracy in differential-equation examples.
Problem
The paper addresses how to recover sparse Polynomial Chaos coefficients with convergence guarantees when approximating quantities of interest from sampled uncertain-input models.
Method
The paper bounds coherence for Hermite and Legendre bases, identifies importance sampling distributions, and proposes coherence-optimal Markov Chain Monte Carlo sampling for general orthonormal bases.
Results
The coherence-optimal sampling method produced positive results and demonstrated improved Polynomial Chaos reconstructions across the reported examples.
Takeaways & Limitations
Coherence-optimal sampling provides a general sampling scheme for reconstructing sparse Hermite and Legendre Polynomial Chaos expansions and may extend to other orthogonal bases.
Takeaways & Limitations
The asymptotic sampling analysis is loose compared with known high-order behavior of Hermite polynomials.
Abstract
from arXiv · showhide
Sampling orthogonal polynomial bases via Monte Carlo is of interest for uncertainty quantification of models with high-dimensional random inputs, using Polynomial Chaos (PC) expansions. It is known that bounding a probabilistic parameter, referred to as {\it coherence}, yields a bound on the number of samples necessary to identify coefficients in a sparse PC expansion via solution to an $\ell_1$-minimization problem. Utilizing asymptotic results for orthogonal polynomials, we bound the coherence parameter for polynomials of Hermite and Legendre type under the respective natural sampling distribution. In both polynomial bases we identify an importance sampling distribution which yields a bound with weaker dependence on the order of the approximation. For more general orthonormal bases, we propose the {\it coherence-optimal} sampling: a Markov Chain Monte Carlo sampling, which directly uses the basis functions under consideration to achieve a statistical optimality among all sampling schemes with identical support. We demonstrate these different sampling strategies numerically in both high-order and high-dimensional, manufactured PC expansions. In addition, the quality of each sampling method is compared in the identification of solutions to two differential equations, one with a high-dimensional random input and the other with a high-order PC expansion. In both cases the coherence-optimal sampling scheme leads to similar or considerably improved accuracy.
1. Introduction
The paper studies sparse Polynomial Chaos approximations recovered from non-intrusive samples, focusing on convergence guarantees and sampling strategies that control coherence. It develops Hermite- and Legendre-specific analyses and a general coherence-optimal sampler, with numerical evidence of improved reconstruction accuracy.
- Motivation and setup: Polynomial Chaos represents a finite-variance quantity of interest as a linear combination of multivariate orthogonal polynomials in uncertain inputs.The basis is orthogonal with respect to the input probability measure, including Legendre-type and Hermite-type choices for uniform and Gaussian inputs.
- Motivation and setup: Sparse representations allow accurate reconstruction from relatively few basis polynomials and samples when the active index set has few elements.The paper connects this sparsity to stable and convergent coefficient recovery with fewer samples than basis terms.
- Recovery framework: The coefficient-identification problem is solved non-intrusively through sampling and Basis Pursuit Denoising, with truncation error represented by a tolerance.A weighted system is used, where the diagonal weighting depends on the sampling strategy.
- Contributions: The analysis bounds coherence and the number of samples sufficient for successful sparse recovery, including Hermite results described as first of their type.The framework adapts sparse-function recovery results to sparse PC expansions and derives Legendre recovery bounds from a different analysis.
- Sampling strategies: Importance sampling distributions for Hermite and Legendre bases weaken the dependence of recovery bounds on approximation order.For Hermite polynomials, the paper analyzes uniform sampling over a dimension-dependent ball rather than the standard Gaussian measure and provides analytic and numerical support.
- Sampling strategies: Coherence-optimal sampling uses basis functions directly in a Markov Chain Monte Carlo scheme and extends to general orthonormal bases.The method is presented as statistically optimal among sampling schemes with identical support and is demonstrated for sparse Hermite and Legendre expansions.
2. Problem Statement and Solution Approach
The paper formulates reconstruction of a quantity of interest from random-input samples as sparse coefficient recovery in a truncated polynomial basis. It assumes independent identically distributed inputs, defines total-order bases, and uses sparsity to justify recovery from fewer samples than basis terms.
- Random inputs: The random input Ξ is modeled on a product probability space with independent, identically distributed components having distribution function f(ξ).The construction identifies the sample space with R^d under the stated assumptions.
- Physical model: The physical system is represented by operators L, B, and I on a bounded Lipschitz domain, with the solution satisfying the associated problem formulation.The recovery methods are independent of the underlying physical problem, although the examples depend on space or time.
- Solution approach: The recovery formulation uses sampled basis evaluations and solution values to construct Ψc = u, then applies sparse-recovery theory to estimate c.The paper adapts existing convergence theorems to sparse PC expansions using properties of orthogonal polynomials.
- Problem statement: The objective is to reconstruct u(x0, t0, Ξ) for fixed spatial and temporal points using sampled evaluations of the governing physical problem.The sampling-based approach does not require modifying the deterministic solver.
- Polynomial basis: The polynomial basis contains multivariate orthogonal polynomials indexed by multi-indices with total order ||k||1 ≤ p.The approximation may use either scalar indexing from 1 to P or multi-index notation.
- Approximately sparse PCE: If coefficients decay rapidly or selected dimensions dominate, the truncated expansion is approximately sparse with s := |C| ≪ P active terms.This sparsity supports stable and convergent coefficient recovery from N < P random samples.
3. Definitions and Background
The paper defines coherence as a basis-dependent quantity that controls sample requirements for sparse recovery, then uses it to motivate sampling distributions designed to reduce coherence.
- Sampling definitions: The basis envelope B(ξ) bounds the largest basis-polynomial magnitude, and G(ξ) is chosen as an upper bound used to construct sampling distributions.Taking G(ξ)=B(ξ) yields an optimally minimal coherence when the bound is attained.
- Sampling definitions: The sampling distribution is supported on a subset S, with truncation conditions intended to limit the effect of restricting the original sample space on orthogonality.The subset is selected to capture regions where the basis envelope is large while controlling orthogonality error.
- Sampling definitions: Importance sampling changes the weights so that weighted basis products remain approximately orthogonal after sampling from the selected distribution.The deviation from orthogonality is bounded by ε_i,j through the weighting function w(Y).
- Coherence and recovery: Coherence bounds the number of samples needed to recover sparse or compressible coefficient vectors through weighted ℓ1-minimization.The convergence results connect bounds on μ(Y) with recovery guarantees.
- Convergence theorems: The convergence theorems cover exact sparse recovery and regularized recovery with truncation error.The regularized formulation includes a weighted truncation-error scale σ_w and parameter ν.
some ¯s, let
The convergence results translate coherence bounds into high-probability sample bounds for recovering sparse or approximately sparse coefficient vectors, subject to truncation-error conditions.
- Recovery implications: When ∥Ψ^T W^2 z∥∞ cannot be bounded by a finite ν, the stated recovery guarantee cannot be directly applied.The analysis separately tracks truncation through the weighted error.
- Recovery implications: A coherence bound on μ(Y) yields a bound on the number of samples required to recover a solution vector.This provides the theoretical justification for seeking sampling distributions with smaller coherence.
4. Sampling Methods
The paper compares standard, asymptotic, and coherence-optimal sampling for Hermite and Legendre polynomial bases, deriving lower-coherence alternatives to natural sampling.
- Standard sampling: Standard sampling uses the orthogonality measure: uniform samples on [−1, 1]^d for Legendre and independent standard normal samples for Hermite.These are the natural sampling distributions for the two bases.
- Coherence-optimal sampling: The coherence-optimal distribution uses G(ξ)=B(ξ) and is introduced to minimize the coherence parameter among sampling choices with the same support.For general orthonormal bases, the paper proposes implementing this distribution with Markov Chain Monte Carlo.
- Standard sampling: Standard Hermite sampling requires a coherence bound implying exponentially growing sample requirements with total approximation order.The theorem assumes d=o(p) and N=O(P^k).
- Standard sampling: For standard Legendre sampling, the coherence bound depends on the relation between dimension d and total order p, with a sharper dimension-dependent bound available when p>d.For p<d, the bound may improve to μ(Ξ)≤3^p≈exp(1.1p).
- Asymptotic sampling: Asymptotic sampling selects distributions based on asymptotic envelopes of the orthogonal polynomials, weakening coherence dependence on p for Hermite and Legendre bases.The Hermite choice uses uniform sampling in a d-dimensional ball, while the Legendre choice corresponds to Chebyshev sampling.
mon case that N ≤P. Let V (r, d) = (r√
For Hermite polynomials in the case N≤P, the alternative sampling construction uses uniform sampling within a d-dimensional ball.
- Hermite sampling: Hermite sampling is analyzed using a uniform distribution over a d-dimensional ball of radius r.The construction samples directions from normalized Gaussian vectors and radii according to the uniform-ball law.
dimensional ball of radius
The section develops sampling distributions for Hermite and Legendre polynomial bases, including asymptotically motivated schemes and coherence-optimal sampling based on the basis envelope. The proposed envelope-based distribution is sampled with MCMC when its normalizing constant is difficult to compute.
- Legendre sampling: Chebyshev sampling for Legendre polynomials has coherence independent of the approximation order.This motivates an importance-sampling distribution with weaker dependence on p.
- Legendre sampling: Uniform sampling is suggested when d > p, whereas Chebyshev sampling is suggested when d < p for Legendre polynomials.The recommendation combines the bounds from Theorems 4.2 and 4.4.
- Coherence-optimal sampling: MCMC sampling avoids computing the normalizing constant c by using point-wise evaluations of B(ξ).The method uses Metropolis-Hastings and permits evaluation of w(ξ) from realized samples.
- MCMC implementation: For p > d, the proposed proposals are uniform on a d-dimensional ball for Hermite polynomials and Chebyshev for Legendre polynomials; for p ≤ d, they switch to standard normal and uniform sampling, respectively.Each proposal covers the full support, and approximate proposal-target matching gives high acceptance with limited burn-in.
- MCMC implementation: The theoretical proofs require independent samples, although the practical implementation may discard intermediate MCMC samples to reduce serial dependence.The paper also identifies better proposal distributions as an open direction.
- Coherence-optimal sampling: Coherence-optimal sampling uses a distribution proportional to f(ξ)B^2(ξ), with weights proportional to w(ξ) = 1/B(ξ).The envelope B(ξ) is constructed from the basis functions and yields minimal coherence among distributions with identical support.
5. Numerical Examples
Numerical experiments compare standard, asymptotically motivated, and coherence-optimal sampling across coherence estimation, sparse recovery, and differential-equation applications. Coherence-optimal sampling performs well across regimes, while the relative performance of standard and asymptotic schemes depends on dimension and order.
- Experimental design: The experiments cover coherence estimates, manufactured sparse PC functions, an elliptic PDE, and an adsorption-model quantity of interest.These tests span high-dimensional and high-order settings.
- Computed coherence: Standard sampling tends to perform poorly at high orders, while asymptotic sampling tends to perform poorly for high-dimensional problems.Coherence-optimal sampling performs well in all tested regimes.
- Manufactured sparse functions: The recovery diagrams show a phase transition in ℓ1-minimization, with success at sufficiently high sparsity and failure at low sparsity.Sampling choices mainly differentiate recovery quality in the transition region.
- Manufactured sparse functions: Across the tested cases, MCMC sampling produces recovery similar to the other schemes or considerable improvements.The result holds for both Hermite and Legendre recovery experiments.
- Elliptic PDE with random input: Standard and coherence-optimal sampling improve accuracy and robustness over Chebyshev sampling at similar sample sizes for the elliptic PDE.The result agrees with the coherence comparison showing smaller coherence for uniform sampling when d > p and smallest coherence for coherence-optimal sampling.
- Elliptic PDE with random input: For the elliptic PDE, standard sampling fails to converge, whereas uniform and coherence-optimal sampling converge as N increases.The comparison uses repeated realizations and evaluates relative root-mean-squared error.
- Application results: The Hermite application confirms that standard sampling is not suited for high-order problems.The observed behavior is consistent with the coherence estimates and high-order recovery experiments.
6. Proofs
The proofs bound Hermite-polynomial behavior by separating oscillatory, monotonic, and boundary regions, then extend the analysis to multidimensional tensor-product bases. These bounds support coherence estimates and sampling-radius choices.
- Hermite asymptotics: The Hermite analysis divides the one-dimensional domain into oscillatory, monotonic, and boundary regions.The oscillatory region contains the zeros of all ψk with k ≤ p, while the boundary separates oscillatory and monotonic behavior.
- Hermite asymptotics: For multidimensional Hermite polynomials, the selected domain fully contains the oscillatory and boundary regions and partially contains the monotonic region.The included monotonic-region size is chosen to satisfy the coherence conditions while bounding |ψk(ξ)|.
- Hermite sampling radius: The Hermite sampling domain is a d-dimensional ball S = {ξ : ∥ξ∥2 ≤ rp}, with radius rp growing asymptotically like 2√p.The radius determines the region used for uniform sampling.
- Multidimensional extension: Tensor-product structure extends one-dimensional polynomial bounds to arbitrary dimension for total order at most p.The multi-index satisfies ∥k∥1 ≤ p, and the basis function is a tensor product of univariate orthogonal polynomials.
- Coherence bounds: The proofs bound exp(−ξ^2/2)ψk(ξ) in the relevant Hermite regions and use these bounds to control the coherence parameter.The resulting domain selection provides an upper bound on minimal coherence.
Further,
The remaining arguments derive coherence bounds for different dimension-order regimes and establish the optimality of the envelope-based sampling distribution. The proofs compare alternative envelope functions through their induced coherence.
- Hermite coherence regimes: When p ≤ d, the Hermite coherence bound uses the fact that at most p dimensions can contain non-constant polynomials.A separate bound is derived for p > d, with the resulting third bound noted to be loose for small d.
- Legendre coherence: Chebyshev sampling for Legendre polynomials yields a coherence bound independent of p.This provides the theoretical basis for the order-robust Legendre sampling strategy.
- Coherence optimality: Theorem 4.5 shows that sampling proportional to f(ξ)B^2(ξ) with weights proportional to 1/B(ξ) achieves the minimal coherence under the stated support conditions.Any alternative envelope differing on a set of non-zero measure produces a larger coherence parameter.
- Coherence optimality: The optimality argument treats the envelope-based scheme as attaining the coherence lower bound through equality across the selected support.The normalizing constant converts f(ξ)B^2(ξ) into a probability distribution on S.
7. Conclusions
The paper derives coherence-based recovery guarantees and alternative sampling schemes for sparse Hermite and Legendre polynomial chaos expansions. Numerical tests, including a 20-dimensional elliptic problem and a high-order Hermite expansion for a nonlinear ODE, report positive or improved reconstruction results for coherence-optimal sampling.
- The analysis bounds a coherence parameter and gives recovery guarantees for sparse polynomial chaos expansions reconstructed via ℓ1-minimization.
- Alternative random sampling schemes provide sharper guarantees than sampling from the bases’ orthogonality measures.The alternatives are derived from properties of Hermite and Legendre polynomials.
- Markov Chain Monte Carlo sampling minimizes the coherence parameter and is called coherence-optimal sampling.The method generates samples for the sampling framework considered in the paper.
- The sampling methods were compared on arbitrary manufactured stochastic functions and tested for identifying differential-equation solutions.
- Positive results were attained for coherence-optimal sampling in a 20-dimensional elliptic boundary value problem.
- Positive results were also observed for a nonlinear ordinary differential equation requiring a high-order Hermite polynomial chaos expansion for accurate solution approximation.
Appendix A: Proof of Lemma 6.1
The appendix proves asymptotic properties used in the Hermite-polynomial analysis. The proof establishes positivity and monotonicity conditions under sufficiently large-index assumptions, relying on approximation formulas and a differential-difference equation.
- The proof rewrites the target relation and identifies conditions on ξ that establish the required inequalities.
- A sequence ε_k → 0 is chosen so that X_ξ is positive, yielding the needed sign and monotonicity conclusions.
- The proof uses a differential-difference equation for orthonormal Hermite polynomials to analyze the relevant derivative behavior.
- For sufficiently large k, the approximation to ψ_k becomes arbitrarily accurate and supports the subsequent differentiated estimates.
- The argument simplifies by setting ε_k = ε_{k+1} = 0 after noting that sufficiently small values do not affect the comparisons.
- The lemma is completed when k_1 and k_0 exceed a sufficiently large K ensuring approximation accuracy and a sufficiently large gap.