Polarization of the Rényi Information Dimension with applications to compressed sensing

Saeid Haghighatshoar, Emmanuel Abbe

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


In this paper, we show that the Hadamard matrix acts as an extractor over the reals of the Rényi Information Dimension (RID), in an analogous way to how it acts as an extractor of the discrete entropy over finite fields. More precisely, we prove that the RID of an i.i.d. sequence of mixture random variables polarizes to the extremal values of 0 and 1 (corresponding to discrete and continuous distributions) when transformed by a Hadamard matrix. Furthermore, we prove that the polarization pattern of the RID admits a closed form expression and follows exactly the Binary Erasure Channel (BEC) polarization pattern in the discrete setting. We discuss the applications of the RID polarization to Compressed Sensing of i.i.d. sources. In particular, we use the RID polarization to construct a family of deterministic ±1-valued sensing matrices for Compressed Sensing. We run numerical simulations to compare the performance of the resulting matrices with that of the random Gaussian and the random Hadamard matrices. The results indicate that the proposed matrices afford competitive performances, while being explicitly constructed.

Original languageEnglish (US)
Article number8017647
Pages (from-to)6858-6868
Number of pages11
JournalIEEE Transactions on Information Theory
Issue number11
StatePublished - Nov 2017

All Science Journal Classification (ASJC) codes

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


  • Compressed Sensing
  • Polarization theory
  • Rényi Information Dimension


Dive into the research topics of 'Polarization of the Rényi Information Dimension with applications to compressed sensing'. Together they form a unique fingerprint.

Cite this