Interpolation via weighted l₁ minimization

2013/08/03 by Holger Rauhut, Rachel Ward, Rauhut, Holger +1 · 2 citations
Engineering · Mathematics · #41A10 #42C05 #6008 #65F35 #FOS: Mathematics #Functional Analysis (math.FA) #Microwave Imaging and Scattering Analysis #Numerical Analysis (math.NA) #Numerical methods in inverse problems #Probability (math.PR) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1308.0759

openalex publication_date 2013/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₁ minimization can reconstruct sparse functions from very few samples, but do not necessarily encourage smoothness. Here we show that weighted l₁ minimization effectively merges the two approaches, promoting both sparsity and smoothness in reconstruction. More precisely, we provide specific choices of weights in the l₁ 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.

Citations

• Recovering Compressively Sampled Signals Using Partial Support Information
• Compressive sensing Petrov-Galerkin approximation of high-dimensional\n parametric operator equations
• Iterative hard thresholding for compressed sensing

Cited by

• Iterative Hard Thresholding for Weighted Sparse Approximation
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class

Related

• Infinite-dimensional compressed sensing and function interpolation
• Enhancing Sparsity by Reweighted L1 Minimization
• Exact Recovery for Sparse Signal via Weighted l₁ Minimization
• Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements
• A signal recovery guarantee with Restricted Isometry Property and Null Space Property for weighted ℓ₁ minimization