Boolean Compressed Sensing and Noisy Group Testing

被引:182
作者
Atia, George K. [1 ]
Saligrama, Venkatesh [2 ]
机构
[1] Univ Illinois, Dept Elect & Comp Engn, Coordinated Sci Lab, Urbana, IL 61801 USA
[2] Boston Univ, Informat Syst & Sci Lab, Dept Elect & Comp Engn, Boston, MA 02215 USA
基金
美国国家科学基金会;
关键词
Compressed sensing (CS); group testing; ML decoding; sparse models;
D O I
10.1109/TIT.2011.2178156
中图分类号
TP [自动化技术、计算机技术];
学科分类号
080201 [机械制造及其自动化];
摘要
The fundamental task of group testing is to recover a small distinguished subset of items from a large population while efficiently reducing the total number of tests (measurements). The key contribution of this paper is in adopting a new information-theoretic perspective on group testing problems. We formulate the group testing problem as a channel coding/decoding problem and derive a single-letter characterization for the total number of tests used to identify the defective set. Although the focus of this paper is primarily on group testing, our main result is generally applicable to other compressive sensing models. The single-letter characterization is shown to be order-wise tight for many interesting noisy group testing scenarios. Specifically, we consider an additive Bernoulli(q) noise model where we show that, for N items and K defectives, the number of tests T is O (K log N/1-q) for arbitrarily small average error probability and O (K-2 log N/1-q) for a worst-case error criterion. We also consider dilution effects whereby a defective item in a positive pool might get diluted with probability u and potentially missed. In this case, it is shown that T is O (K log N/(1-u)(2)) and O (K-2 log N/(1-u)(2)) for the average and the worst-case error criteria, respectively. Furthermore, our bounds allow us to verify existing known bounds for noiseless group testing including the deterministic noise-free case and approximate reconstruction with bounded distortion. Our proof of achievability is based on random coding and the analysis of a maximum likelihood detector, and our information theoretic lower bound is based on Fano's inequality.
引用
收藏
页码:1880 / 1901
页数:22
相关论文
共 29 条
[1]
Information Theoretic Bounds for Compressed Sensing [J].
Aeron, Shuchin ;
Saligrama, Venkatesh ;
Zhao, Manqi .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 56 (10) :5111-5130
[2]
[Anonymous], AS C SIGN SYST COMP
[3]
[Anonymous], LECT DES SCREEN EXP
[4]
[Anonymous], ALL C COMM CONTR COM
[5]
[Anonymous], BOOLEAN COMPRESSED S
[6]
[Anonymous], P IEEE DYN SPECTR AC
[7]
Atia G., 2011, 38 INT C AUT LANG PR
[8]
NOISY GROUP TESTING: AN INFORMATION THEORETIC PERSPECTIVE [J].
Atia, George ;
Saligrama, Venkatesh .
2009 47TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING, VOLS 1 AND 2, 2009, :355-362
[9]
Asymptotic efficiency of two-stage disjunctive testing [J].
Berger, T ;
Levenshtein, VI .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2002, 48 (07) :1741-1749
[10]
Stable signal recovery from incomplete and inaccurate measurements [J].
Candes, Emmanuel J. ;
Romberg, Justin K. ;
Tao, Terence .
COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2006, 59 (08) :1207-1223