FoCM 2014 conference

Workshop A2 - Computational Harmonic Analysis, Image and Signal Processing - Semi-plenary talk

December 12, 18:05 ~ 18:55 - Room C21

Weighted sparsity for function approximation and interpolation

Rachel Ward

University of Texas at Austin, USA   -

Functions of interest are often smooth and sparse in some sense, and both priors should be taken into account when interpolating sampled data. Linear interpolation methods are effective under strong regularity assumptions, but do not 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 encourage smoothness without adding weights. We argue that weighted $\ell_1$ minimization effectively merges the two approaches, promoting both sparsity and smoothness in reconstruction. Along the way, we introduce a notion of weighted sparsity and extend concepts from compressive sensing such as the restricted isometry property and null space property to accommodate weighted sparse expansions. We expect these developments to be of independent interest in the study of structured sparse approximations and continuous-time compressive sensing problems.

Joint work with Holger Rauhut (Aachen University).

View abstract PDF