Interpolation via weighted $l_1$ minimization

Abstract

Functions of interest are often smooth and sparse in some sense, and both priors should be taken into account when interpolating sampled data. Classical linear interpolation methods are effective under strong regularity assumptions, but cannot incorporate nonlinear sparsity structure. At the same time, nonlinear methods such as $l_1$ minimization can reconstruct sparse functions from very few samples, but do not necessarily encourage smoothness. Here we show that weighted $l_1$ minimization effectively merges the two approaches, promoting both sparsity and smoothness in reconstruction. More precisely, we provide specific choices of weights in the $l_1$ objective to achieve rates for functions with coefficient sequences in weighted $l_p$ spaces, $p<=1$. We consider the implications of these results for spherical harmonic and polynomial interpolation, in the univariate and multivariate setting. Along the way, we extend concepts from compressive sensing such as the restricted isometry property and null space property to accommodate weighted sparse expansions; these developments should be of independent interest in the study of structured sparse approximations and continuous-time compressive sensing problems.

32 pages, 3 figures

References in corpus (4)

• A weighted L1-minimization approach for sparse polynomial chaos expansions
• Iterative Hard Thresholding for Weighted Sparse Approximation
• Approximation of mixed order Sobolev functions on the $d$-torus -- Asymptotics, preasymptotics and $d$-dependence
• Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations

Cited by in corpus (9)

• On Polynomial Chaos Expansion via Gradient-enhanced ${\ell }_1$-minimization
• A gradient enhanced ${\ell }_1$-minimization for sparse approximation of polynomial chaos expansions
• The sample complexity of weighted sparse approximation
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• Infinite-dimensional ${\ell }^1$ minimization and function approximation from pointwise data
• Iterative Hard Thresholding for Weighted Sparse Approximation
• Infinite-dimensional compressed sensing and function interpolation
• Compressive Sensing with Redundant Dictionaries and Structured Measurements
• Multichannel group sparsity methods for compressive channel estimation in doubly selective multicarrier MIMO systems (extended version)