Answers are grounded in this paper and cite their sources.
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 x ∈ RNsupported on an unknown set S ⊂ {1, ..., N} with |S| ≤ κ, if S has weighted cardinality ω(S) : = Σj∈Sωj2, and if the weights on Scexhibit mild growth, ωj2≥ γlog(j/ω(S)) for j ∈ Scand γ > 0, then the sample complexity for sparse recovery via weighted ℓ1-minimization using weights ωjis linear in the weighted sparsity level, and m = O(ω(S)/γ). This main result is a generalization of special cases including a) the standard sparse recovery setting where all weights ωj≡ 1, and m = O(k log(N/κ)); b) the setting where the support is known a priori, and m = O(κ); and c) the setting of sparse recovery with prior information, and m depends on how well the weights are aligned with the support set S. We further extend the results in case c) to the setting of additive noise. Our results are nonuniform that is they apply for a fixed support, unknown a priori, and the weights on S do not all have to be smaller than the weights on Scfor our recovery results to hold.
No takes yet. Share an insight, caveat, or question.
Bah et al. (2016) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: