Ensemble Average Analysis of Non-Adaptive Group Testing with Sparse Pooling Graphs

2025/07/27 by Yacoub, Emna Ben, Liva, Gianluigi, Paolini, Enrico +1
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2507.20281

Abstract

A combinatorial analysis of the false alarm (FA) and misdetection (MD) probabilities of non-adaptive group testing with sparse pooling graphs is developed. The analysis targets the combinatorial orthogonal matching pursuit and definite defective detection algorithms in the noiseless, non-quantitative setting. The approach follows an ensemble average perspective, where average FA/MD probabilities are computed for pooling graph ensembles with prescribed degree distributions. The accuracy of the analysis is demonstrated through numerical examples, showing that the proposed technique can be used to characterize the performance of non-adaptive group testing schemes based on sparse pooling graphs.

Citations

• Non-adaptive Quantitative Group Testing Using Irregular Sparse Graph Codes
• Sparse Graph Codes for Non-adaptive Quantitative Group Testing
• SAFFRON: A Fast, Efficient, and Robust Framework for Group Testing based\n on Sparse-Graph Codes
• Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms
• The Detection of Defective Members of Large Populations

Related

• Non-Adaptive Group Testing based on Sparse Pooling Graphs
• A Probably Approximately Correct Analysis of Group Testing Algorithms
• Non-adaptive Quantitative Group Testing Using Irregular Sparse Graph Codes
• The Statistics of Noisy One-Stage Group Testing in Outbreaks
• Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms