Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies

DOI10.1016/J.JCP.2014.09.019zbMATH Open1349.94110arXiv1408.4157OpenAlexW1965093639MaRDI QIDQ349724FDOQ349724

Authors: Jerrad Hampton, Alireza Doostan 

Publication date: 5 December 2016

Published in: Journal of Computational Physics (Search for Journal in Brave)

Abstract: 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 $el{l}_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.

Full work available at URL: https://arxiv.org/abs/1408.4157

Recommendations

• Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression
• A near-optimal sampling strategy for sparse recovery of polynomial chaos expansions
• Least squares polynomial chaos expansion: a review of sampling strategies
• Sparse polynomial chaos expansions via compressed sensing and D-optimal design
• A hybrid sequential sampling strategy for sparse polynomial chaos expansion based on compressive sampling and Bayesian experimental design

zbMATH Keywords

Markov chain Monte Carlosparse approximationLegendre polynomialsuncertainty quantificationHermite polynomialsstochastic PDEspolynomial chaoscompressive sampling\(\ell_1\)-minimization

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.) (33C45) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35) Sampling theory in information and communication theory (94A20)

Cites Work

• Automated solution of differential equations by the finite element method. The FEniCS book
• Probing the Pareto frontier for basis pursuit solutions
• NIST handbook of mathematical functions
• A survey of cross-validation procedures for model selection
• Atomic Decomposition by Basis Pursuit
• Title not available (Why is that?)
• Title not available (Why is that?)
• Monte Carlo sampling methods using Markov chains and their applications
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sparse and redundant representations. From theory to applications in signal and image processing.
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Compressed sensing
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• Sparse Legendre expansions via \(\ell_1\)-minimization
• A Probabilistic and RIPless Theory of Compressed Sensing
• Title not available (Why is that?)
• The Wiener--Askey Polynomial Chaos for Stochastic Differential Equations
• Numerical methods for stochastic computations. A spectral method approach.
• Spectral Methods for Uncertainty Quantification
• Title not available (Why is that?)
• Atomic decomposition by basis pursuit
• Asymptotic analysis of the Hermite polynomials from their differential–difference equation
• Stochastic collocation algorithms using \(\ell_1\)-minimization
• A non-adapted sparse approximation of PDEs with stochastic inputs
• Mean Convergence of Expansions in Laguerre and Hermite Series
• Asymptotic Forms for Laguerre Polynomials
• Compressive sensing and structured random matrices
• Adaptive sparse polynomial chaos expansion based on least angle regression
• A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions
• Sparse multiresolution regression for uncertainty propagation
• Uniform Bounds for Bessel Functions
• Reweighted \(\ell_1\) minimization method for stochastic elliptic differential equations
• Selection of polynomial chaos bases via Bayesian model uncertainty methods with applications to sparse approximation of PDEs with stochastic inputs
• Generalized Jacobi Weights, Christoffel Functions, and Jacobi Polynomials
• A compressed sensing approach for partial differential equations with random input data
• Physical Systems with Random Uncertainties: Chaos Representations with Arbitrary Probability Measure
• Dimensionality reduction for complex models via Bayesian compressive sensing
• Multi-resolution analysis of Wiener-type uncertainty propagation schemes

Cited In (95)

• Projection methods for stochastic dynamic systems: a frequency domain approach
• Sparsity-promoting elastic net method with rotations for high-dimensional nonlinear inverse problem
• A data-driven framework for sparsity-enhanced surrogates with arbitrary mutually dependent randomness
• A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions
• Probabilistic modeling and global sensitivity analysis for CO\(_2\) storage in geological formations: a spectral approach
• Tight bounds on the mutual coherence of sensing matrices for Wigner d-functions on regular grids
• Orbit uncertainty propagation and sensitivity analysis with separated representations
• Sparse polynomial chaos expansions: literature survey and benchmark
• A preconditioning approach for improved estimation of sparse polynomial chaos expansions
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• PLS-based adaptation for efficient PCE representation in high dimensions
• Divide and conquer: an incremental sparsity promoting compressive sampling approach for polynomial chaos expansions
• Some greedy algorithms for sparse polynomial chaos expansions
• M-PCM-OFFD: an effective output statistics estimation method for systems of high dimensional uncertainties subject to low-order parameter interactions
• An efficient multifidelity \(\ell_1\)-minimization method for sparse polynomial chaos
• Multivariate approximation in downward closed polynomial spaces
• On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization
• Infinite-dimensional compressed sensing and function interpolation
• A gradient enhanced \(\ell_{1}\)-minimization for sparse approximation of polynomial chaos expansions
• An efficient non-intrusive reduced basis model for high dimensional stochastic problems in CFD
• Subsampled Gauss quadrature nodes for estimating polynomial chaos expansions
• Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations
• Data-driven polynomial ridge approximation using variable projection
• Practical error bounds for a non-intrusive bi-fidelity approach to parametric/stochastic model reduction
• Efficient reliability analysis with a CDA-based dimension-reduction model and polynomial chaos expansion
• Sensitivity-enhanced generalized polynomial chaos for efficient uncertainty quantification
• Infinite-dimensional \(\ell ^1\) minimization and function approximation from pointwise data
• A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials
• Enhancing sparsity of Hermite polynomial expansions by iterative rotations
• Sparse identification of nonlinear dynamical systems via reweighted \(\ell_1\)-regularized least squares
• Sparse polynomial chaos expansions via compressed sensing and D-optimal design
• Efficient uncertainty quantification of stochastic CFD problems using sparse polynomial chaos and compressed sensing
• Intrusive generalized polynomial chaos with asynchronous time integration for the solution of the unsteady Navier-Stokes equations
• Optimal Bayesian experimental design for subsurface flow problems
• Weighted discrete least-squares polynomial approximation using randomized quadratures
• Constructing least-squares polynomial approximations
• Adaptive sparse polynomial dimensional decomposition for derivative-based sensitivity
• A low-rank control variate for multilevel Monte Carlo simulation of high-dimensional uncertain systems
• Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression
• A rapid and efficient isogeometric design space exploration framework with application to structural mechanics
• Sequential Design of Experiment for Sparse Polynomial Chaos Expansions
• A randomized algorithm for multivariate function approximation
• Near-optimal sampling strategies for multivariate function approximation on general domains
• A robust and efficient stepwise regression method for building sparse polynomial chaos expansions
• A mixed ℓ₁ regularization approach for sparse simultaneous approximation of parameterized PDEs
• Sparse polynomial chaos expansions using variational relevance vector machines
• Stochastic Collocation vial₁-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification
• Least squares polynomial chaos expansion: a review of sampling strategies
• A novel sparse polynomial chaos expansion technique with high adaptiveness for surrogate modelling
• Adaboost-based ensemble of polynomial chaos expansion with adaptive sampling
• Basis adaptive sample efficient polynomial chaos (BASE-PC)
• Gaussian process regression and conditional polynomial chaos for parameter estimation
• A multi-fidelity polynomial chaos-greedy Kaczmarz approach for resource-efficient uncertainty quantification on limited budget
• Efficient Bayesian experimentation using an expected information gain lower bound
• Train flow chaos analysis based on an improved cellular automata model
• A near-optimal sampling strategy for sparse recovery of polynomial chaos expansions
• An efficient and robust adaptive sampling method for polynomial chaos expansion in sparse Bayesian learning framework
• Compressive sensing with redundant dictionaries and structured measurements
• Reduced basis methods for uncertainty quantification
• An adaptive WENO collocation method for differential equations with random coefficients
• Variance-based adaptive sequential sampling for polynomial chaos expansion
• Adaptive weighted least-squares polynomial chaos expansion with basis adaptivity and sequential adaptive sampling
• Multi-level multi-fidelity sparse polynomial chaos expansion based on Gaussian process regression
• Compressive sensing with cross-validation and stop-sampling for sparse polynomial chaos expansions
• Stochastic collocation methods via \(\ell_1\) minimization using randomized quadratures
• Effectively subsampled quadratures for least squares polynomial approximations
• Active learning polynomial chaos expansion for reliability analysis by maximizing expected indicator function prediction error
• Sparse identification of nonlinear dynamical systems via non-convex penalty least squares
• Weighted approximate Fekete points: sampling for least-squares polynomial approximation
• Bi-fidelity reduced polynomial chaos expansion for uncertainty quantification
• Bi-fidelity approximation for uncertainty quantification and sensitivity analysis of irradiated particle-laden turbulence
• Analysis of geometric uncertainties in CFD problems solved by RBF-FD meshless method
• Algorithm 1040: the Sparse Grids Matlab Kit -- a Matlab implementation of sparse grids for high-dimensional function approximation and uncertainty quantification
• Towards optimal sampling for learning sparse approximation in high dimensions
• A hybrid sequential sampling strategy for sparse polynomial chaos expansion based on compressive sampling and Bayesian experimental design
• A general framework of rotational sparse approximation in uncertainty quantification
• SeAr PC: sensitivity enhanced arbitrary polynomial chaos
• Comparison of the performance and reliability between improved sampling strategies for polynomial chaos expansion
• Importance sampling in signal processing applications
• A massively parallel implementation of multilevel Monte Carlo for finite element models
• Polynomial chaos expansion vs. Monte Carlo simulation in a stochastic analysis of wave propagation
• A stochastic Galerkin method with adaptive time-stepping for the Navier-Stokes equations
• Bi-fidelity variational auto-encoder for uncertainty quantification
• Analysis of sparse recovery for Legendre expansions using envelope bound
• Sliced-Inverse-Regression--Aided Rotated Compressive Sensing Method for Uncertainty Quantification
• A reduced-basis polynomial-chaos approach with a multi-parametric truncation scheme for problems with uncertainties
• Projection pursuit adaptation on polynomial chaos expansions
• Physics-informed polynomial chaos expansions
• Sparse Approximation of Data-Driven Polynomial Chaos Expansions: An Induced Sampling Approach
• Data-driven projection pursuit adaptation of polynomial chaos expansions for dependent high-dimensional parameters
• Compressed sensing with sparse corruptions: fault-tolerant sparse collocation approximations
• An active sparse polynomial chaos expansion approach based on sequential relevance vector machine
• Classifier-based adaptive polynomial chaos expansion for high-dimensional uncertainty quantification
• Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements
• Polynomial chaos expansions for dependent random variables

Uses Software

• Digital Library of Mathematical Functions
• FEniCS
• PDCO
• SPGL1
• SparseLab

This page was built for publication: Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q349724)