Universal Source Polarization and Spare Recovery

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 1 i−1 n→∞ distribution. While this result does not extend to q-ary sources, n|{i:H(Ui|U )>1−δ}| −→ H(p), (2) 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.