The Sample Complexity of Weighted Sparse Approximation

摘要

For Gaussian sampling matrices, we provide bounds on the minimal number of measurements 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 supported on an unknown set with , if has weighted cardinality , and if the weights on exhibit mild growth, for and , then the sample complexity for sparse recovery via weighted -minimization using weights is linear in the weighted sparsity level, and . This main result is a generalization of special cases including a) the standard sparse recovery setting where all weights , and ; b) the setting where the support is known a priori, and ; and c) the setting of sparse recovery with prior information, and depends on how well the weights are aligned with the support set . 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 do not all have to be smaller than the weights on for our recovery results to hold.