Support recovery with sparsely sampled free random matrices

Antonia M. Tulino, Giuseppe Caire, Sergio Verdu, Shlomo Shamai

Research output: Contribution to journalArticlepeer-review

103 Scopus citations


Consider a Bernoulli-Gaussian complex n-vector whose components are V i = Xi Bi, with Xi ∼ CN (0, Px) and binary Bi mutually independent and iid across i. This random q-sparse vector is multiplied by a square random matrix bf U, and a randomly chosen subset, of average size np, p ε[0,1], of the resulting vector components is then observed in additive Gaussian noise. We extend the scope of conventional noisy compressive sampling models where U is typically a matrix with iid components, to allow U satisfying a certain freeness condition. This class of matrices encompasses Haar matrices and other unitarily invariant matrices. We use the replica method and the decoupling principle of Guo and Verdú, as well as a number of information-theoretic bounds, to study the input-output mutual information and the support recovery error rate in the limit of n → ∞. We also extend the scope of the large deviation approach of Rangan and characterize the performance of a class of estimators encompassing thresholded linear MMSE and l1 relaxation.

Original languageEnglish (US)
Article number6472315
Pages (from-to)4243-4271
Number of pages29
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - 2013

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Compressed sensing
  • free probability
  • random matrices
  • rate-distortion theory
  • sparse models
  • support recovery


Dive into the research topics of 'Support recovery with sparsely sampled free random matrices'. Together they form a unique fingerprint.

Cite this