Thouless-Anderson-Palmer approach for lossy compression
Author:
- 31 March 2004
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 69 (3) , 035105
Abstract
We study an ill-posed linear inverse problem, where a binary sequence will be reproduced using a sparse 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 -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 approach. Numerical results show that the algorithm can empirically saturate the theoretical limit for the sparse construction of our codes, which is also very close to the rate-distortion function.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- A coding theorem for lossy data compression by LDPC codesIEEE Transactions on Information Theory, 2003
- The capacity of low-density parity-check codes under message-passing decodingIEEE Transactions on Information Theory, 2001
- Statistical mechanics of error-correcting codesEurophysics Letters, 1999
- Belief propagation vs. TAP for decoding corrupted messagesEurophysics Letters, 1998
- Spin-glass models as error-correcting codesNature, 1989
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948