### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 2984-2988 |

Number of pages | 5 |

ISBN (Electronic) | 9781467377041 |

DOIs | |

State | Published - Sep 28 2015 |

Event | IEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong Duration: Jun 14 2015 → Jun 19 2015 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

Volume | 2015-June |

ISSN (Print) | 2157-8095 |

### Other

Other | IEEE International Symposium on Information Theory, ISIT 2015 |
---|---|

Country | Hong Kong |

City | Hong Kong |

Period | 6/14/15 → 6/19/15 |

## Fingerprint Dive into the research topics of 'Local recovery in data compression for general sources'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015*(pp. 2984-2988). [7283004] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2015.7283004