On sparse interpolation and the design of deterministic interpolation points

DOI10.1137/13094596XzbMATH Open1304.65098arXiv1308.6038MaRDI QIDQ2930008FDOQ2930008

Authors: Zhiqiang Xu, Tao Zhou 

Publication date: 17 November 2014

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: In this paper, we build up a framework for sparse interpolation. We first investigate the theoretical limit of the number of unisolvent points for sparse interpolation under a general setting and try to answer some basic questions of this topic. We also explore the relation between classical interpolation and sparse interpolation. We second consider the design of the interpolation points for the $s$-sparse functions in high dimensional Chebyshev bases, for which the possible applications include uncertainty quantification, numerically solving stochastic or parametric PDEs and compressed sensing. Unlike the traditional random sampling method, we present in this paper a deterministic method to produce the interpolation points, and show its performance with $el{l}_1$ minimization by analyzing the mutual incoherence of the interpolation matrix. Numerical experiments show that the deterministic points have a similar performance with that of the random points.

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

Recommendations

• On the decidability of sparse univariate polynomial interpolation
• Polynomial homotopy method for the sparse interpolation problem. I: Equally spaced sampling
• Sparse interpolation in terms of multivariate Chebyshev polynomials
• On certain configurations of points in \(\mathbb{R}{}^ n\) which are unisolvent for polynomial interpolation
• A scale and shift paradigm for sparse interpolation in one and more dimensions

zbMATH Keywords

uncertainty quantificationnumerical experimentscompressed sensingmultidimensional interpolation\(\ell_1\) minimizationpolynomial approximations

Mathematics Subject Classification ID

Multidimensional problems (41A63) Numerical interpolation (65D05) Interpolation in approximation theory (41A05) Approximation by polynomials (41A10)

Cited In (25)

• Subsampling bias and the best-discrepancy systematic cross validation
• Numerical methods for reinterpreted discrete fracture models with random inputs
• Infinite-dimensional compressed sensing and function interpolation
• Weighted approximate Fekete points: sampling for least-squares polynomial approximation
• A gradient enhanced \(\ell_{1}\)-minimization for sparse approximation of polynomial chaos expansions
• A General Framework of Rotational Sparse Approximation in Uncertainty Quantification
• Stochastic collocation algorithms using \(l_1\)-minimization for Bayesian solution of inverse problems
• A sparse grid stochastic collocation method for elliptic interface problems with random input
• Towards optimal sampling for learning sparse approximation in high dimensions
• The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials
• A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials
• Enhancing sparsity of Hermite polynomial expansions by iterative rotations
• Entropy stable Galerkin methods with suitable quadrature rules for hyperbolic systems with random inputs
• Weighted discrete least-squares polynomial approximation using randomized quadratures
• Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method
• An outlier detection and recovery method based on moving least squares quasi-interpolation scheme and \(\text{ł}_0\)-minimization problem
• Sparse Approximation via Generating Point Sets
• Uncertainty quantification of derivative instruments
• Stochastic Collocation vial₁-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification
• On interpolation approximation: convergence rates for polynomial interpolation for functions of limited regularity
• A POINT BASIS FOR MULTIVARIABLE PIECEWISE LINEAR INTERPOLATION AND DESIGN CENTERING
• An adaptive WENO collocation method for differential equations with random coefficients
• On optimal interpolatory point systems
• On the decidability of sparse univariate polynomial interpolation
• Stochastic collocation methods via \(\ell_1\) minimization using randomized quadratures

This page was built for publication: On sparse interpolation and the design of deterministic interpolation points

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