Large Alphabet Source Coding Using Independent Component Analysis

DOI10.1109/TIT.2017.2728017MaRDI QIDQ4566507zbMATH OpenOpenAlexFDO

Authors Amichai Painsky, Saharon Rosset, Meir Feder

Publication date 27 June 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.07003

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Source coding (94A29)

Abstract: Large alphabet source coding is a basic and well-studied problem in data compression. It has many applications such as compression of natural language text, speech and images. The classic perception of most commonly used methods is that a source is best described over an alphabet which is at least as large as the observed alphabet. In this work we challenge this approach and introduce a conceptual framework in which a large alphabet source is decomposed into "as statistically independent as possible" components. This decomposition allows us to apply entropy encoding to each component separately, while benefiting from their reduced alphabet size. We show that in many cases, such decomposition results in a sum of marginal entropies which is only slightly greater than the entropy of the source. Our suggested algorithm, based on a generalization of the Binary Independent Component Analysis, is applicable for a variety of large alphabet source coding setups. This includes the classical lossless compression, universal compression and high-dimensional vector quantization. In each of these setups, our suggested approach outperforms most commonly used methods. Moreover, our proposed framework is significantly easier to implement in most of these cases.

Recommendations

• Generalized Independent Component Analysis Over Finite Alphabets
• Adaptive Coding and Prediction of Sources With Large and Infinite Alphabets
• Efficient method of adaptive arithmetic coding for sources with large alphabets
• Coding for the Large-Alphabet Adversarial Channel
• A New Code for Encoding All Monotone Sources With a Fixed Large Alphabet Size
• Multi-alphabet universal coding of memoryless sources
• Huffman Redundancy for Large Alphabet Sources
• On the MDL principle for i.i.d. sources with large alphabets
• Source coding, large deviations, and approximate pattern matching
• Coding for a binary independent piecewise-identically-distributed source

Cited in

(2)

• On the MDL principle for i.i.d. sources with large alphabets
• Coding for the Large-Alphabet Adversarial Channel

This page was built for publication: Large Alphabet Source Coding Using Independent Component Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566507)