Non-adaptive pooling strategies for detection of rare faulty items
arXiv:1302.0189 · doi:10.1109/ICCW.2013.6649458
Abstract
We study non-adaptive pooling strategies for detection of rare faulty items. Given a binary sparse N-dimensional signal x, how to construct a sparse binary MxN pooling matrix F such that the signal can be reconstructed from the smallest possible number M of measurements y=Fx? We show that a very low number of measurements is possible for random spatially coupled design of pools F. Our design might find application in genetic screening or compressed genotyping. We show that our results are robust with respect to the uncertainty in the matrix F when some elements are mistaken.
arXiv comment5 pages
References in corpus (11)
- Message Passing Algorithms for Compressed Sensing
- Boolean Compressed Sensing and Noisy Group Testing
- Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
- Statistical physics-based reconstruction in compressed sensing
- Compressed Genotyping
- Non-adaptive Group Testing: Explicit bounds and novel algorithms
- Sparsely-spread CDMA - a statistical mechanics based analysis
- Compressed Sensing under Matrix Uncertainty: Optimum Thresholds and Robust Approximate Message Passing
- Compressed Sensing of Approximately-Sparse Signals: Phase Transitions and Optimal Reconstruction
- Rare-Allele Detection Using Compressed Se(que)nsing
- Compressed sensing with sparse, structured matrices