Compressing sparse sequences under local decodability constraints
Compressing sparse sequences under local decodability constraints
复制标题
在局部可解码性约束下压缩稀疏序列
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
T. Courtade
中科院分区：
文献类型：
--
作者：
A. Pananjady;T. Courtade
我们考虑一个受局部可解码性约束的变长信源编码问题。特别地，我们研究在任何信源比特最多通过探测\(d\)个码字比特就能被正确解码的约束下，\(r\)-稀疏二进制序列编码所能达到的块长缩放行为。我们考虑了自适应和非自适应访问模型，并推导出了通常在常数因子范围内一致的上界和下界。值得注意的是，尽管进行了大量研究工作，但我们这个问题的固定块长类似情况的特征仍然未知。还简要讨论了与通信复杂性的联系。
We consider a variable-length source coding problem subject to local decodability constraints. In particular, we investigate the blocklength scaling behavior attainable by encodings of r-sparse binary sequences, under the constraint that any source bit can be correctly decoded upon probing at most d codeword bits. We consider both adaptive and non-adaptive access models, and derive upper and lower bounds that often coincide up to constant factors. Notably, such a characterization for the fixed-blocklength analog of our problem remains unknown, despite considerable research efforts. Connections to communication complexity are also briefly discussed.