TY - JOUR

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

AU - Haghighatshoar, Saeid

AU - Abbe, Emmanuel

N1 - Funding Information:
Manuscript received April 7, 2016; revised August 10, 2017; accepted August 21, 2017. Date of publication August 29, 2017; date of current version October 18, 2017. E. Abbe was supported by NSF under Grant CCF-1319299. This paper was presented at the 2013 IEEE International Symposium on Information Theory [1].
Publisher Copyright:
© 2017 IEEE.

PY - 2017/11

Y1 - 2017/11

N2 - 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.

AB - 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.

KW - Compressed Sensing

KW - Polarization theory

KW - Rényi Information Dimension

UR - http://www.scopus.com/inward/record.url?scp=85028716172&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028716172&partnerID=8YFLogxK

U2 - 10.1109/TIT.2017.2746103

DO - 10.1109/TIT.2017.2746103

M3 - Article

AN - SCOPUS:85028716172

SN - 0018-9448

VL - 63

SP - 6858

EP - 6868

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 11

M1 - 8017647

ER -