The sample complexity of weighted sparse approximation

Abstract

For Gaussian sampling matrices, we provide bounds on the minimal number of measurements $m$ required to achieve robust weighted sparse recovery guarantees in terms of how well a given prior model for the sparsity support aligns with the true underlying support. Our main contribution is that for a sparse vector $\mathbf{x}\in {\mathbb{R}}^N$ supported on an unknown set $\mathcal{S}\subset \{1,\dots ,N\}$ with $|\mathcal{S}|\le k$, if $\mathcal{S}$ has \emph{weighted cardinality} $\ddot{I}‰(\mathcal{S}):={\sum }_{j\in \mathcal{S}}\ddot{I}{‰}_j^2$, and if the weights on ${\mathcal{S}}^c$ exhibit mild growth, $\ddot{I}{‰}_j^2\ge {\hat{I}}^3\log (j/\ddot{I}‰(\mathcal{S}))$ for $j\in {\mathcal{S}}^c$ and ${\hat{I}}^3>0$, then the sample complexity for sparse recovery via weighted ${\ell }_1$-minimization using weights $\ddot{I}{‰}_j$ is linear in the weighted sparsity level, and $m=\mathcal{O}(\ddot{I}‰(\mathcal{S})/{\hat{I}}^3)$. This main result is a generalization of special cases including a) the standard sparse recovery setting where all weights $\ddot{I}{‰}_j\equiv 1$, and $m=\mathcal{O}\left(k\log \left(N/k\right)\right)$; b) the setting where the support is known a priori, and $m=\mathcal{O}(k)$; and c) the setting of sparse recovery with prior information, and $m$ depends on how well the weights are aligned with the support set $\mathcal{S}$. We further extend the results in case c) to the setting of additive noise. Our results are {\em nonuniform} that is they apply for a fixed support, unknown a priori, and the weights on $\mathcal{S}$ do not all have to be smaller than the weights on ${\mathcal{S}}^c$ for our recovery results to hold.

21 pages, 12 figures