Simple Codes and Sparse Recovery with Fast Decoding
Simple Codes and Sparse Recovery with Fast Decoding
复制标题
简单的代码和稀疏恢复与快速解码
DOI：
10.1137/21m1465354
复制
发表时间：
2023
影响因子：
0.8
通讯作者：
Ribeiro, João
中科院分区：
文献类型：
--
作者：
Cheraghchi, Mahdi;Ribeiro, João
构造具有指定最小距离参数的纠错码是编码理论中的一个核心问题。在这项工作中，我们研究了一种非常简单的二元线性码的构造，它可以纠正给定数量的错误。此外，我们还为该码设计了一个简单的、接近最优的伴随式译码器。解码器的运行时间在码块长度上只是对数，在差错数目上几乎是线性的。该解码器可以应用于任何域上的精确全稀疏恢复，在相同测量次数的情况下改进了以前的结果。此外，根据接收字的校正子的计算可以在块长度上以几乎线性的时间完成。我们还展示了这些技术在非自适应群体测试中的应用，并构造了简单的显式测量方案，该方案带有测试和恢复时间，用于在一个大小的种群中识别最多的缺陷。
Construction of error-correcting codes achieving a designated minimum distance parameter is a central problem in coding theory. In this work, we study a very simple construction of binary linear codes that correct a given number of errors. Moreover, we design a simple, nearly optimal syndrome decoder for the code as well. The running time of the decoder is only logarithmic in the block length of the code and nearly linear in the number of errors. This decoder can be applied to exact for-all sparse recovery over any field, improving upon previous results with the same number of measurements. Furthermore, computation of the syndrome from a received word can be done in nearly linear time in the block length. We also demonstrate an application of these techniques in nonadaptive group testing and construct simple explicit measurement schemes withtests andrecovery time for identifying up todefectives in a population of size.
在接近最佳的时间内实现所有稀疏恢复
DOI：
--
发表时间：
2014
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
A. Gilbert;Yi Li;E. Porat;M. Strauss
通讯作者：
M. Strauss
稀疏 Walsh-Hadamard 变换的近乎最优确定性算法
DOI：
10.1145/3029050
发表时间：
2015
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Mahdi Cheraghchi;P. Indyk
通讯作者：
P. Indyk