Thouless-Anderson-Palmer approach for lossy compression

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 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 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.