Interpolation via weighted ℓ₁ minimization

详细信息    查看全文

• 作者：Holger Rauhut^a ; ^{rauhut@mathc.rwth-aachen.de" class="auth_mail" title="E-mail the corresponding author} ; Rachel Ward^b ; ^{rward@math.utexas.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Bounded orthonormal systems ; Compressive sensing ; Interpolation ; Weighted sparsity ; ℓ_{1ℓ1 minimization}
• 刊名：Applied and Computational Harmonic Analysis
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：40
• 期：2
• 页码：321-351
• 全文大小：8280 K

文摘

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 ℓ₁${\ell }_1$ minimization can reconstruct sparse functions from very few samples, but do not necessarily encourage smoothness. Here we show that weighted  ℓ₁${\ell }_1$ minimization effectively merges the two approaches, promoting both sparsity and smoothness in reconstruction. More precisely, we provide specific choices of weights in the ℓ₁${\ell }_1$ objective to achieve approximation rates for functions with coefficient sequences in weighted ℓ_p${\ell }_p$ spaces with p≤1$p\le 1$. We consider 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.