Lossy Data Compression with Random Gates
- 14 July 2005
- journal article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 95 (3) , 038701
- https://doi.org/10.1103/physrevlett.95.038701
Abstract
We introduce a new protocol for a lossy data compression algorithm which is based on constraint satisfaction gates. We show that the theoretical capacity of algorithms built from standard parity-check gates converges exponentially fast to the Shannon's bound when the number of variables seen by each gate increases. We then generalize this approach by introducing random gates. They have theoretical performances nearly as good as parity checks, but they offer the great advantage that the encoding can be done in linear time using the survey inspired decimation algorithm, a powerful algorithm for constraint satisfaction problems derived from statistical physics.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Passing Messages Between DisciplinesScience, 2003
- On the nature of the low-temperature phase in discontinuous mean-field spin glassesZeitschrift für Physik B Condensed Matter, 2003
- Rigorous Decimation-Based Construction of Ground Pure States for Spin-Glass Models on Random LatticesPhysical Review Letters, 2003
- Two Solutions to Diluted p-Spin Models and XORSAT ProblemsJournal of Statistical Physics, 2003
- Random-satisfiability problem: From an analytic solution to an efficient algorithmPhysical Review E, 2002
- Analytic and Algorithmic Solution of Random Satisfiability ProblemsScience, 2002
- EditorialTheoretical Computer Science, 2001
- A variational description of the ground state structure in random satisfiability problemsZeitschrift für Physik B Condensed Matter, 2000
- Determining computational complexity from characteristic ‘phase transitions’Nature, 1999
- Information Theory and Reliable CommunicationPublished by Springer Nature ,1972