TY - GEN

T1 - Local recovery in data compression for general sources

AU - Mazumdar, Arya

AU - Chandar, Venkat

AU - Wornell, Gregory W.

N1 - Publisher Copyright:
© 2015 IEEE.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2015/9/28

Y1 - 2015/9/28

N2 - Source coding is concerned with optimally compressing data, so that it can be reconstructed up to a specified distortion from its compressed representation. Usually, in fixed-length compression, a sequence of n symbols (from some alphabet) is encoded to a sequence of k symbols (bits). The decoder produces an estimate of the original sequence of n symbols from the encoded bits. The rate-distortion function characterizes the optimal possible rate of compression allowing a given distortion in reconstruction as n grows. This function depends on the source probability distribution. In a locally recoverable decoding, to reconstruct a single symbol, only a few compressed bits are accessed. In this paper we find the limits of local recovery for rates near the rate-distortion function. For a wide set of source distributions, we show that, it is possible to compress within ϵ of the rate-distortion function such the local recoverability grows as Ω(log(1/ϵ)); that is, in order to recover one source symbol, at least Ω(log(1/ϵ)) bits of the compressed symbols are queried. We also show order optimal impossibility results. Similar results are provided for lossless source coding as well.

AB - Source coding is concerned with optimally compressing data, so that it can be reconstructed up to a specified distortion from its compressed representation. Usually, in fixed-length compression, a sequence of n symbols (from some alphabet) is encoded to a sequence of k symbols (bits). The decoder produces an estimate of the original sequence of n symbols from the encoded bits. The rate-distortion function characterizes the optimal possible rate of compression allowing a given distortion in reconstruction as n grows. This function depends on the source probability distribution. In a locally recoverable decoding, to reconstruct a single symbol, only a few compressed bits are accessed. In this paper we find the limits of local recovery for rates near the rate-distortion function. For a wide set of source distributions, we show that, it is possible to compress within ϵ of the rate-distortion function such the local recoverability grows as Ω(log(1/ϵ)); that is, in order to recover one source symbol, at least Ω(log(1/ϵ)) bits of the compressed symbols are queried. We also show order optimal impossibility results. Similar results are provided for lossless source coding as well.

UR - http://www.scopus.com/inward/record.url?scp=84969786280&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84969786280&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2015.7283004

DO - 10.1109/ISIT.2015.7283004

M3 - Conference contribution

AN - SCOPUS:84969786280

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2984

EP - 2988

BT - Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - IEEE International Symposium on Information Theory, ISIT 2015

Y2 - 14 June 2015 through 19 June 2015

ER -