Simple Codes and Sparse Recovery with Fast Decoding

DOI10.1137/21M1465354MaRDI QIDQ6101016zbMATH OpenOpenAlexFDO

Authors Mahdi Cheraghchi, João L. Ribeiro

Publication date 31 May 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.02852

zbMATH Keywords

group testingsparse recoverysublinear-time algorithmssyndrome decoding

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Combinatorial codes (94B25)

Abstract: 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 $K$. 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 $K$. 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 non-adaptive group testing, and construct simple explicit measurement schemes with $O(K^{2}lo{g}^{2}N)$ tests and $O(K^{3}lo{g}^{2}N)$ recovery time for identifying up to $K$ defectives in a population of size $N$.

Recommendations

• Codes for exact support recovery of sparse vectors from inaccurate linear measurements and their decoding
• scientific article; zbMATH DE number 57521
• Efficiently decodable compressed sensing by list-recoverable codes and recursion
• Sparsity-Aware Sphere Decoding: Algorithms and Complexity Analysis
• Fast Decoding of Codes in the Rank, Subspace, and Sum-Rank Metric
• Fast Decoding of Expander Codes
• scientific article; zbMATH DE number 3924676
• scientific article; zbMATH DE number 177859
• Fast maximum likelihood decoding of Reed-Muller codes
• Fast maximum likelihood decoding of Reed-Muller codes

Cites work

• Advances in Cryptology - EUROCRYPT 2004
• Combinatorial Algorithms for Compressed Sensing
• Efficient and Robust Compressed Sensing Using Optimized Expander Graphs
• Efficiently decodable error-correcting list disjunct matrices and applications (extended abstract)
• Efficiently decodable non-adaptive group testing
• Expander codes
• Explicit Non-adaptive Combinatorial Group Testing Schemes
• scientific article; zbMATH DE number 5485456 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3801449 (Why is no real title available?)
• Lossless condensers, unbalanced expanders, and extractors
• Noise-resilient group testing: limitations and constructions
• Polynomial multiplication over finite fields in time O(n n)
• Randomness conductors and constant-degree lossless expanders
• SAFFRON: A Fast, Efficient, and Robust Framework for Group Testing Based on Sparse-Graph Codes
• Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes

Cited in

(1)

• Codes for exact support recovery of sparse vectors from inaccurate linear measurements and their decoding

This page was built for publication: Simple Codes and Sparse Recovery with Fast Decoding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6101016)