Universal source polarization and sparse recovery

Emmanuel Abbe

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

Polar codes allow to perform lossless compression of i.i.d. sources at the lowest rate with low encoding and decoding complexity. In this paper, it is shown that for binary sources, there exist universal polar codes which can compress any source of low enough entropy, without requiring knowledge of the source distribution. While this result does not extend to q-ary sources, it is shown how it extends to q-ary sources which belong to a restricted family. An analogy between this family and BECs in channel polarization is discussed. Finally, an application of the universal source polarization results to sparse data recovery is proposed.

Original languageEnglish (US)
Title of host publication2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings
DOIs
StatePublished - 2010
Event2010 IEEE Information Theory Workshop, ITW 2010 - Dublin, Ireland
Duration: Aug 30 2010Sep 3 2010

Publication series

Name2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings

Other

Other2010 IEEE Information Theory Workshop, ITW 2010
Country/TerritoryIreland
CityDublin
Period8/30/109/3/10

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Universal source polarization and sparse recovery'. Together they form a unique fingerprint.

Cite this