A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions

Abstract

In this paper we propose an algorithm for recovering sparse orthogonal polynomials using stochastic collocation. Our approach is motivated by the desire to use generalized polynomial chaos expansions (PCE) to quantify uncertainty in models subject to uncertain input parameters. The standard sampling approach for recovering sparse polynomials is to use Monte Carlo (MC) sampling of the density of orthogonality. However MC methods result in poor function recovery when the polynomial degree is high. Here we propose a general algorithm that can be applied to any admissible weight function on a bounded domain and a wide class of exponential weight functions defined on unbounded domains. Our proposed algorithm samples with respect to the weighted equilibrium measure of the parametric domain, and subsequently solves a preconditioned ${\ell }^1$-minimization problem, where the weights of the diagonal preconditioning matrix are given by evaluations of the Christoffel function. We present theoretical analysis to motivate the algorithm, and numerical results that show our method is superior to standard Monte Carlo methods in many situations of interest. Numerical examples are also provided that demonstrate that our proposed Christoffel Sparse Approximation algorithm leads to comparable or improved accuracy even when compared with Legendre and Hermite specific algorithms.

32 pages, 10 figures

References in corpus (2)

• Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies
• Bergman kernels for weighted polynomials and weighted equilibrium measures of C^n

Cited by in corpus (20)

• Sparse Polynomial Chaos Expansions: Literature Survey and Benchmark
• Sparse Polynomial Chaos Expansions via Compressed Sensing and D-optimal Design
• Polynomial chaos expansions for dependent random variables
• Compressed sensing with sparse corruptions: Fault-tolerant sparse collocation approximations
• A gradient enhanced ${\ell }_1$-minimization for sparse approximation of polynomial chaos expansions
• Compressive Sensing with Cross-Validation and Stop-Sampling for Sparse Polynomial Chaos Expansions
• A non-intrusive reduced-order modeling method using polynomial chaos expansion
• Sparse Polynomial Chaos expansions using Variational Relevance Vector Machines
• Data-driven polynomial chaos expansions: a weighted least-square approximation
• A Near-Optimal Sampling Strategy for Sparse Recovery of Polynomial Chaos Expansions
• A preconditioning approach for improved estimation of sparse polynomial chaos expansions
• A mixed ${\ell }_1$ regularization approach for sparse simultaneous approximation of parameterized PDEs
• Time and Frequency Domain Methods for Basis Selection in Random Linear Dynamical Systems
• Second order hierarchical partial least squares regression-polynomial chaos expansion for global sensitivity and reliability analyses of high-dimensional models
• Stochastic collocation methods via $L_1$ minimization using randomized quadratures
• Stochastic collocation methods via minimization of Transformed $L_1$ penalty
• A general framework of rotational sparse approximation in uncertainty quantification
• Rank adaptive tensor recovery based model reduction for partial differential equations with high-dimensional random inputs
• A survey of unsupervised learning methods for high-dimensional uncertainty quantification in black-box-type problems
• Weighted approximate Fekete points: Sampling for least-squares polynomial approximation