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} $\omega (\mathcal{S}):={\sum }_{j\in \mathcal{S}}{\omega }_j^2$, and if the weights on ${\mathcal{S}}^c$ exhibit mild growth, ${\omega }_j^2\ge \gamma \log (j/\omega (\mathcal{S}))$ for $j\in {\mathcal{S}}^c$ and $\gamma >0$, then the sample complexity for sparse recovery via weighted ${\ell }_1$-minimization using weights ${\omega }_j$ is linear in the weighted sparsity level, and $m=\mathcal{O}(\omega (\mathcal{S})/\gamma )$. This main result is a generalization of special cases including a) the standard sparse recovery setting where all weights ${\omega }_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

References in corpus (4)

• Weighted ${\ell }_1$ Minimization for Sparse Recovery with Prior Information
• Breaking through the Thresholds: an Analysis for Iterative Reweighted ${\ell }_1$ Minimization via the Grassmann Angle Framework
• Recovery Analysis for Weighted ${\ell }_1$-Minimization Using a Null Space Property
• Weighted-{${\ell }_1$} minimization with multiple weighting sets

Cited by in corpus (7)

• Fitting very flexible models: Linear regression with large numbers of parameters
• exoALMA. VIII. Probabilistic Moment Maps and Data Products using Non-parametric Linear Models
• Infinite-dimensional compressed sensing and function interpolation
• Stable Recovery of Weighted Sparse Signals from Phaseless Measurements via Weighted l1 Minimization
• The greedy side of the LASSO: New algorithms for weighted sparse recovery via loss function-based orthogonal matching pursuit
• RLS Recovery with Asymmetric Penalty: Fundamental Limits and Algorithmic Approaches
• Sparse matrices for weighted sparse recovery