Infinite-dimensional compressed sensing and function interpolation

Abstract

We introduce and analyze a framework for function interpolation using compressed sensing. This framework - which is based on weighted ${\ell }^1$ minimization - does not require a priori bounds on the expansion tail in either its implementation or its theoretical guarantees, and in the absence of noise leads to genuinely interpolatory approximations. We also establish a new recovery guarantee for compressed sensing with weighted ${\ell }^1$ minimization based on this framework. This guarantee has several key benefits. First, unlike existing results, it is sharp (up to constants and log factors) for large classes of functions regardless of the choice of weights. Second, by examining the measurement condition in the recovery guarantee, we are able to suggest a good overall strategy for selecting the weights. In particular, when applied to the important case of multivariate approximation with orthogonal polynomials, this weighting strategy leads to provably optimal estimates on the number of measurements required, whenever the support set of the significant coefficients is a so-called lower set. Finally, this guarantee can also be used to theoretically confirm the benefits of alternative weighting strategies where the weights are chosen based on prior support information. This provides a theoretical basis for a number of recent numerical studies showing the effectiveness of such approaches.

References in corpus (10)

• Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Compressed Sensing and Parallel Acquisition
• A Christoffel function weighted least squares algorithm for collocation approximations
• A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions
• Stochastic collocation on unstructured multivariate meshes
• The sample complexity of weighted sparse approximation
• Infinite-dimensional ${\ell }^1$ minimization and function approximation from pointwise data
• Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients
• Optimal sampling rates for approximating analytic functions from pointwise samples

Cited by in corpus (2)

• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Sparse matrices for weighted sparse recovery