Skip to main content

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

Author(s): Haghighatshoar, S; Abbe, Emmanuel

To refer to this page use:
Abstract: 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.
Publication Date: 2017
Citation: Haghighatshoar, S, Abbe, E. (2017). Polarization of the Rényi Information Dimension with applications to compressed sensing. IEEE Transactions on Information Theory, 63 (6858 - 6868. doi:10.1109/TIT.2017.2746103
DOI: doi:10.1109/TIT.2017.2746103
Pages: 6858 - 6868
Type of Material: Journal Article
Journal/Proceeding Title: IEEE Transactions on Information Theory
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.