Sparse matrices for weighted sparse recovery

Abstract

We derived the first sparse recovery guarantees for weighted ${\ell }_1$ minimization with sparse random matrices and the class of weighted sparse signals, using a weighted versions of the null space property to derive these guarantees. These sparse matrices from expender graphs can be applied very fast and have other better computational complexities than their dense counterparts. In addition we show that, using such sparse matrices, weighted sparse recovery with weighted ${\ell }_1$ minimization leads to sample complexities that are linear in the weighted sparsity of the signal and these sampling rates can be smaller than those of standard sparse recovery. Moreover, these results reduce to known results in standard sparse recovery and sparse recovery with prior information and the results are supported by numerical experiments.

19 pages, 4 figures

References in corpus (5)

• The sample complexity of weighted sparse approximation
• Recovery Analysis for Weighted ${\ell }_1$-Minimization Using a Null Space Property
• Infinite-dimensional ${\ell }^1$ minimization and function approximation from pointwise data
• The sum of the r'th roots of first n natural numbers and new formula for factorial
• Infinite-dimensional compressed sensing and function interpolation