Statistical Mechanical Approach to Lossy Data Compression:Theory and Practice
arXiv:cs/0509086 · doi:10.1016/j.physa.2006.01.013
Abstract
The encoder and decoder for lossy data compression of binary memoryless sources are developed on the basis of a specific-type nonmonotonic perceptron. Statistical mechanical analysis indicates that the potential ability of the perceptron-based code saturates the theoretically achievable limit in most cases although exactly performing the compression is computationally difficult. To resolve this difficulty, we provide a computationally tractable approximation algorithm using belief propagation (BP), which is a current standard algorithm of probabilistic inference. Introducing several approximations and heuristics, the BP-based algorithm exhibits performance that is close to the achievable limit in a practical time scale in optimal cases.
10 pages, 2 figures, REVTEX preprint
References in corpus (3)
Cited by in corpus (9)
- Learning by message-passing in networks of discrete synapses
- Efficient LDPC Codes over GF(q) for Lossy Data Compression
- Statistical mechanics of lossy compression for non-monotonic multilayer perceptrons
- Efficient data compression from statistical physics of codes over finite fields
- Linear Complexity Lossy Compressor for Binary Redundant Memoryless Sources
- Belief Propagation for Error Correcting Codes and Lossy Compression Using Multilayer Perceptrons
- Parallel dynamics of continuous Hopfield model revisited
- Error correcting code using tree-like multilayer perceptron
- A statistical-mechanical view on source coding: physical compression and data compression