J. Phys. Soc. Jpn. 74 (2005) pp. 488-497  |Next Article|  |Table of Contents|
|Full Text PDF (175K)| |Buy This Article|

Statistical Mechanical Approach to Error Exponents of Lossy Data Compression

Tadaaki Hosaka and Yoshiyuki Kabashima

(Received September 24, 2004)

We present a scheme to accurately evaluate the error exponents of a lossy data compression problem, which characterize average probabilities over a code ensemble of compression failure and success above or below a critical compression rate, respectively, utilizing the replica method (RM). Although the existing method used in information theory (IT) is, in practice, limited to ensembles of randomly constructed codes, the proposed RM-based approach can be applied to a wider class of ensembles. This approach reproduces the optimal expressions of the error exponents achieved by the random code ensembles, which are known in IT. In addition, the proposed framework is used to show that codes composed of non-monotonic perceptrons of a specific type can provide the optimal exponents in most cases, which is supported by numerical experiments. ©2005 The Physical Society of Japan

KEYWORDS: error exponent, lossy data compression, replica method, random code ensemble, perceptron
URL: http://jpsj.ipap.jp/link?JPSJ/74/488/
DOI: 10.1143/JPSJ.74.488

References | Citing Articles (8)

1. H. Nishimori: Statistical Physics of Spin Glasses and Information Processing (Oxford University Press, Oxford, 2001).
2. Y. Kabashima, K. Nakamura and J van Mourik: Phys. Rev. E 66 (2002) 036125[APS].
3. N. Skanzos, J van Mourik, D. Saad and Y. Kabashima: J. Phys. A 36 (2003) 11131[IoP STACKS].
4. K. Marton: IEEE Trans. Inf. Theory 20 (1974) 197.
5. I. Csiszár and J. Körner: Information Theory, Coding Theorems for Discrete Memoryless Systems (Academic Press, New York, 1981) p. 158.
6. R. G. Gallager: Information Theory and Reliable Communication (Wiley, New York, 1968).
7. A. J. Viterbi and J. K. Omura: Principles of Digital Communication and Coding (McGraw-Hill Kogakusha, Tokyo, 1979).
8. J. R. L. de Almeida and D. J. Thouless: J. Phys. A 11 (1977) 983[IoP STACKS].
9. D. J. Gross and M. Mézard: Nucl. Phys. B 240 (1984) 431[CrossRef].
10. T. M. Cover and J. A. Thomas: Elements of Information Theory (Wiley, New York, 1991).
11. C. E. Shannon: IRE Natl. Conv. Rec. Part 4 (1959) 142.
12. S. Arimoto: IEEE Trans. Inf. Theory 18 (1972) 14.
13. R. E. Blahut: IEEE Trans. Inf. Theory 18 (1972) 460.
14. K. Ogure and Y. Kabashima: Prog. Theor. Phys. 111 (2004) 661[IPAP].
15. T. Hosaka, Y. Kabashima and H. Nishimori: Phys. Rev. E 66 (2002) 066126[APS].
16. A. Engel and C. P. L. van den Broeck: Statistical Mechanics of Learning (Cambridge University Press, Cambridge, 2001).