Computer Science – Information Theory
Scientific paper
2010-12-02
Computer Science
Information Theory
Scientific paper
This paper investigates universal polar coding schemes. In particular, a notion of ordering (called convolutional path) is introduced between probability distributions to determine when a polar compression (or communication) scheme designed for one distribution can also succeed for another one. The original polar decoding algorithm is also generalized to an algorithm allowing to learn information about the source distribution using the idea of checkers. These tools are used to construct a universal compression algorithm for binary sources, operating at the lowest achievable rate (entropy), with low complexity and with guaranteed small error probability. In a second part of the paper, the problem of sketching high dimensional discrete signals which are sparse is approached via the polarization technique. It is shown that the number of measurements required for perfect recovery is competitive with the $O(k \log (n/k))$ bound (with optimal constant for binary signals), meanwhile affording a deterministic low complexity measurement matrix.
No associations
LandOfFree
Universal polar coding and sparse recovery does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Universal polar coding and sparse recovery, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Universal polar coding and sparse recovery will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-603221