Publication

Universal Source Polarization and Spare Recovery

Emmanuel Abbé
2010
Conference Papers

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

Official source

https://infoscience.epfl.ch/entities/publication/4d4039a2-3d45-49a4-aa1d-0ec50bfbbbf1

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Emmanuel Abbé
2010
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/4d4039a2-3d45-49a4-aa1d-0ec50bfbbbf1

About this result

Related concepts (32)

Lossless compression

Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistical redundancy. By contrast, lossy compression permits reconstruction only of an approximation of the original data, though usually with greatly improved compression rates (and therefore reduced media sizes).

Data compression

In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression reduces bits by identifying and eliminating statistical redundancy. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information.

Lossy compression

In information technology, lossy compression or irreversible compression is the class of data compression methods that uses inexact approximations and partial data discarding to represent the content. These techniques are used to reduce data size for storing, handling, and transmitting content. The different versions of the photo of the cat on this page show how higher degrees of approximation create coarser images as more details are removed. This is opposed to lossless data compression (reversible data compression) which does not degrade the data.

Related publications (29)

Universal Source Polarization and Spare Recovery

Chat with Graph Search

Tracking the Limits of Knowledge Propagation: How LLMs Fail at Multi-Step Reasoning with Conflicting Knowledge

Grounding imperialism: Zschokke and the construction of the El Kansera Dam in Morocco from 1927-1934

On the Informativeness of Moments in Optimal Stopping