Support Recovery from Noisy Random Measurements via Weighted ℓ-1 Minimization

Jun Zhang, Urbashi Mitra, Kuan Wen Huang, Nicolo Michelusi

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


Herein, the sample complexity of general weighted ℓ-1 minimization in terms of support recovery from noisy underdetermined measurements is analyzed. This analysis generalizes prior work on ℓ-1 minimization by considering arbitrary weighting. The explicit relationship between the weights and the sample complexity is stated such that for random matrices with i.i.d. Gaussian entries, the weighted ℓ-1 minimization recovers the support of the underlying signal with high probability as the problem dimension increases. This result provides a measure that is predictive of relative performance of different algorithms. Motivated by the analysis, a new iterative reweighted strategy is proposed for binary signal recovery. In the binary sparsity-Promoting Reweighted ℓ-1 minimization (bPRL1) algorithm, a sequence of weighted ℓ-1 minimization problems are solved where partial support recovery is used to prune the optimization; furthermore, the weights used for the next iteration are updated by the current estimate. bPRL1 is compared to other weighted algorithms through the proposed measure and numerical results are shown to provide superior performance for a spectrum occupancy estimation problem motivated by cognitive radio.

Original languageEnglish (US)
Article number8362965
Pages (from-to)4527-4540
Number of pages14
JournalIEEE Transactions on Signal Processing
Issue number17
StatePublished - Sep 1 2018
Externally publishedYes


  • Weighted ℓ-1 minimization
  • cognitive radio
  • partial support recovery
  • sample complexity
  • support recovery

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Support Recovery from Noisy Random Measurements via Weighted ℓ-1 Minimization'. Together they form a unique fingerprint.

Cite this