Weighted ${\ell }_1$ Minimization for Sparse Recovery with Prior Information

Abstract

In this paper we study the compressed sensing problem of recovering a sparse signal from a system of underdetermined linear equations when we have prior information about the probability of each entry of the unknown signal being nonzero. In particular, we focus on a model where the entries of the unknown vector fall into two sets, each with a different probability of being nonzero. We propose a weighted ${\ell }_1$ minimization recovery algorithm and analyze its performance using a Grassman angle approach. We compute explicitly the relationship between the system parameters (the weights, the number of measurements, the size of the two sets, the probabilities of being non-zero) so that an iid random Gaussian measurement matrix along with weighted ${\ell }_1$ minimization recovers almost all such sparse signals with overwhelming probability as the problem dimension increases. This allows us to compute the optimal weights. We also provide simulations to demonstrate the advantages of the method over conventional ${\ell }_1$ optimization.

5 Pages, Submitted to ISIT 2009

Cited by in corpus (8)

• An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
• Recursive Recovery of Sparse Signal Sequences from Compressive Measurements: A Review
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Dynamic Filtering of Time-Varying Sparse Signals via l1 Minimization
• Block-length dependent thresholds in block-sparse compressed sensing
• The sample complexity of weighted sparse approximation
• Heterogeneous Networked Data Recovery from Compressive Measurements Using a Copula Prior
• Compressive Sampling with Known Spectral Energy Density