TY - GEN
T1 - Universal source polarization and sparse recovery
AU - Abbe, Emmanuel
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=80051923901&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80051923901&partnerID=8YFLogxK
U2 - 10.1109/CIG.2010.5592875
DO - 10.1109/CIG.2010.5592875
M3 - Conference contribution
AN - SCOPUS:80051923901
SN - 9781424482641
T3 - 2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings
BT - 2010 IEEE Information Theory Workshop, ITW 2010 - Proceedings
T2 - 2010 IEEE Information Theory Workshop, ITW 2010
Y2 - 30 August 2010 through 3 September 2010
ER -