Local recovery in data compression for general sources
Local recovery in data compression for general sources
复制标题
通用源数据压缩的本地恢复
DOI：
10.1109/isit.2015.7283004
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
G. Wornell
中科院分区：
文献类型：
--
作者：
A. Mazumdar;V. Chandar;G. Wornell
信源编码关注的是对数据进行最优压缩，以便能够从其压缩表示中在特定失真范围内进行重构。通常，在定长压缩中，来自某个字母表的\(n\)个符号序列被编码为\(k\)个符号（比特）序列。解码器从编码比特中生成对原始\(n\)个符号序列的估计。当\(n\)增大时，率失真函数描述了在重构中允许给定失真的最优可能压缩率。该函数取决于信源概率分布。在局部可恢复解码中，为了重构单个符号，只需访问少量压缩比特。在本文中，我们找出了在接近率失真函数的速率下局部恢复的极限。对于一大类信源分布，我们表明，可以在率失真函数的\(\varepsilon\)范围内进行压缩，使得局部可恢复性以\(\Omega(\log(1 / \varepsilon))\)增长；也就是说，为了恢复一个信源符号，至少要查询\(\Omega(\log(1 / \varepsilon))\)个压缩符号的比特。我们还展示了阶最优不可能性结果。对于无损信源编码也提供了类似结果。
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.