Towards optimal sampling for learning sparse approximation in high dimensions
From MaRDI portal
Abstract: In this chapter, we discuss recent work on learning sparse approximations to high-dimensional functions on data, where the target functions may be scalar-, vector- or even Hilbert space-valued. Our main objective is to study how the sampling strategy affects the sample complexity -- that is, the number of samples that suffice for accurate and stable recovery -- and to use this insight to obtain optimal or near-optimal sampling procedures. We consider two settings. First, when a target sparse representation is known, in which case we present a near-complete answer based on drawing independent random samples from carefully-designed probability measures. Second, we consider the more challenging scenario when such representation is unknown. In this case, while not giving a full answer, we describe a general construction of sampling measures that improves over standard Monte Carlo sampling. We present examples using algebraic and trigonometric polynomials, and for the former, we also introduce a new procedure for function approximation on irregular (i.e., nontensorial) domains. The effectiveness of this procedure is shown through numerical examples. Finally, we discuss a number of structured sparsity models, and how they may lead to better approximations.
Recommendations
- On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples
- Learning functions of few arbitrary linear parameters in high dimensions
- Correcting for unknown errors in sparse high-dimensional function approximation
- Learning general sparse additive models from point queries in high dimensions
- Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements
Cites work
- A Christoffel function weighted least squares algorithm for collocation approximations
- A class of null space conditions for sparse recovery via nonconvex, non-separable minimizations
- A compressed sensing approach for partial differential equations with random input data
- A GENERAL FRAMEWORK FOR ENHANCING SPARSITY OF GENERALIZED POLYNOMIAL CHAOS EXPANSIONS
- A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions
- A gradient enhanced \(\ell_{1}\)-minimization for sparse approximation of polynomial chaos expansions
- A mixed ℓ1 regularization approach for sparse simultaneous approximation of parameterized PDEs
- A near-optimal sampling strategy for sparse recovery of polynomial chaos expansions
- A non-adapted sparse approximation of PDEs with stochastic inputs
- A weighted _1-minimization approach for sparse polynomial chaos expansions
- Adaptive approximation by optimal weighted least-squares methods
- Adaptive sparse polynomial chaos expansion based on least angle regression
- An efficient sampling method for regression-based polynomial chaos expansion
- An introduction to frames and Riesz bases
- Analysis of discrete L^2 projection on polynomial spaces with random evaluations
- Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets
- Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients
- Analytic regularity and nonlinear approximation of a class of parametric semilinear elliptic PDEs
- Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE's
- APPROXIMATING SMOOTH, MULTIVARIATE FUNCTIONS ON IRREGULAR DOMAINS
- Approximation of high-dimensional parametric PDEs
- Basis adaptive sample efficient polynomial chaos (BASE-PC)
- Boosted optimal weighted least-squares
- Breaking the curse of dimensionality in sparse polynomial approximation of parametric PDEs
- Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression
- Compressed sensing with sparse corruptions: fault-tolerant sparse collocation approximations
- Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements
- Compressive imaging: structure, sampling, learning. With contributions by Vegard Antun
- Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies
- Compressive sensing adaptation for polynomial chaos expansions
- Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations
- Computation of induced orthogonal polynomial distributions
- Constructing least-squares polynomial approximations
- Correcting data corruption errors for multivariate function approximation
- Correcting for unknown errors in sparse high-dimensional function approximation
- Discrete least squares polynomial approximation with random evaluations - application to parametric and stochastic elliptic PDEs
- Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension
- Divide and conquer: an incremental sparsity promoting compressive sampling approach for polynomial chaos expansions
- Enhancing \(\ell_1\)-minimization estimates of polynomial chaos expansions using basis selection
- Enhancing sparsity of Hermite polynomial expansions by iterative rotations
- Handbook of uncertainty quantification. In 2 volumes
- High-dimensional adaptive sparse polynomial interpolation and applications to parametric PDEs
- Hyperbolic cross approximation. Lecture notes given at the courses on constructive approximation and harmonic analysis, Barcelona, Spain, May 30 -- June 3, 2016
- Infinite-dimensional \(\ell ^1\) minimization and function approximation from pointwise data
- Infinite-dimensional compressed sensing and function interpolation
- Interpolation via weighted \(\ell_{1}\) minimization
- Introduction to uncertainty quantification
- Least squares polynomial chaos expansion: a review of sampling strategies
- Multivariate approximation
- Multivariate approximation in downward closed polynomial spaces
- Multivariate approximation of functions on irregular domains by weighted least-squares methods
- Multivariate discrete least-squares approximations with a new type of collocation grid
- Near-optimal sampling strategies for multivariate function approximation on general domains
- Nonadaptive quasi-optimal points selection for least squares linear regression
- Numerical Fourier analysis
- On Discrete Least-Squares Projection in Unbounded Domain with Random Evaluations and its Application to Parametric Uncertainty Quantification
- On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization
- On sparse interpolation and the design of deterministic interpolation points
- On the convergence of generalized polynomial chaos expansions
- On the stability and accuracy of least squares approximations
- Optimal pointwise sampling for \(L^2\) approximation
- Optimal sampling and Christoffel functions on general domains
- Optimal weighted least-squares methods
- Physical Systems with Random Uncertainties: Chaos Representations with Arbitrary Probability Measure
- Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
- Polynomial chaos expansions for dependent random variables
- Recovery guarantees for polynomial coefficients from weakly dependent data with outliers
- Regularity and generalized polynomial chaos approximation of parametric and random second-order hyperbolic partial differential equations
- Reweighted \(\ell_1\) minimization method for stochastic elliptic differential equations
- Sequential Design of Experiment for Sparse Polynomial Chaos Expansions
- Sequential sampling for optimal weighted least squares approximations in hierarchical spaces
- Sliced-Inverse-Regression--Aided Rotated Compressive Sensing Method for Uncertainty Quantification
- Sparse adaptive Taylor approximation algorithms for parametric and stochastic elliptic PDEs
- Sparse approximation of multivariate functions from small datasets via weighted orthogonal matching pursuit
- Sparse approximation using _1-_2 minimization and its application to stochastic collocation
- Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
- Sparse Legendre expansions via _1-minimization
- Sparse Polynomial Approximation of High-Dimensional Functions
- Sparse polynomial chaos expansions via compressed sensing and D-optimal design
- Sparse polynomial chaos expansions: literature survey and benchmark
- Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
- Sparse Recovery via ℓq-Minimization for Polynomial Chaos Expansions
- Spectral Methods for Uncertainty Quantification
- Stochastic collocation algorithms using _1-minimization
- Stochastic collocation methods via \(\ell_1\) minimization using randomized quadratures
- Stochastic collocation on unstructured multivariate meshes
- Stochastic Collocation vial1-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification
- Stochastic Spectral Galerkin and Collocation Methods for PDEs with Random Coefficients: A Numerical Comparison
- Subsampled Gauss quadrature nodes for estimating polynomial chaos expansions
- User-friendly tail bounds for sums of random matrices
- Weighted discrete least-squares polynomial approximation using randomized quadratures
Cited in
(5)- On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples
- Sample complexity bounds for the local convergence of least squares approximation
- Signal reconstruction using determinantal sampling
- Optimal sampling for least-squares approximation
- Convergence and near-optimal sampling for multivariate function approximations in irregular domains via Vandermonde with Arnoldi
This page was built for publication: Towards optimal sampling for learning sparse approximation in high dimensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6390185)
