New Non-Asymptotic Bounds on Numbers of Codewords for the Fixed-Length Lossy Compression

Tetsunao MATSUTA  Tomohiko UYEMATSU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.12   pp.2116-2129
Publication Date: 2016/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.2116
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Source Coding and Data Compression
finite blocklength,  non-asymptotic bound,  rate-distortion function,  source coding,  

Full Text: PDF>>
Buy this Article

In this paper, we deal with the fixed-length lossy compression, where a fixed-length sequence emitted from the information source is encoded into a codeword, and the source sequence is reproduced from the codeword with a certain distortion. We give lower and upper bounds on the minimum number of codewords such that the probability of exceeding a given distortion level is less than a given probability. These bounds are characterized by using the α-mutual information of order infinity. Further, for i.i.d. binary sources, we provide numerical examples of tight upper bounds which are computable in polynomial time in the blocklength.