Thouless-Anderson-Palmer Approach for Lossy Compression
arXiv:cond-mat/0310440 · doi:10.1103/PhysRevE.69.035105
Abstract
We study an ill-posed linear inverse problem, where a binary sequence will be reproduced using a sparce matrix. According to the previous study, this model can theoretically provide an optimal compression scheme for an arbitrary distortion level, though the encoding procedure remains an NP-complete problem. In this paper, we focus on the consistency condition for a dynamics model of Markov-type to derive an iterative algorithm, following the steps of Thouless-Anderson-Palmer's. Numerical results show that the algorithm can empirically saturate the theoretical limit for the sparse construction of our codes, which also is very close to the rate-distortion function.
10 pages, 3 figures
Cited by in corpus (27)
- Learning by message-passing in networks of discrete synapses
- Binary quantization using Belief Propagation with decimation over factor graphs of LDGM codes
- Channel Coding and Lossy Source Coding Using a Constrained Random Number Generator
- Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
- Analysis of LDGM and compound codes for lossy compression and binning
- Encoding for the Blackwell Channel with Reinforced Belief Propagation
- Statistical mechanics of lossy compression using multilayer perceptrons
- Low density codes achieve the rate-distortion bound
- The theoretical capacity of the Parity Source Coder
- Statistical Mechanical Approach to Lossy Data Compression:Theory and Practice
- Polar Codes are Optimal for Lossy Source Coding
- Efficient LDPC Codes over GF(q) for Lossy Data Compression
- Low-density graph codes that are optimal for source/channel coding and binning
- Statistical mechanics of lossy compression for non-monotonic multilayer perceptrons
- Efficient data compression from statistical physics of codes over finite fields
- Typical Performance of Irregular Low-Density Generator-Matrix Codes for Lossy Compression
- Universal Behavior in Large-scale Aggregation of Independent Noisy Observations
- Approaching the Rate-Distortion Limit with Spatial Coupling, Belief propagation and Decimation
- 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
- Low-density constructions can achieve the Wyner-Ziv and Gelfand-Pinsker bounds
- Rate Distortion Theorem and the Multicritical Point of Spin Glass
- Error correcting code using tree-like multilayer perceptron
- Lower Bounds on the Rate-Distortion Function of LDGM Codes
- A statistical-mechanical view on source coding: physical compression and data compression
- Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes