Group testing with prior statistics
| Autor: | Tongxin Li, Tarik Kaced, Chun Lam Chan, Sidharth Jaggi, Wenhao Huang |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
FOS: Computer and information sciences
Discrete mathematics Independent and identically distributed random variables A priori probability Physical constant Information Theory (cs.IT) Computer Science - Information Theory Principle of maximum entropy Binary number Huffman coding Upper and lower bounds Group testing symbols.namesake symbols Mathematics |
| Zdroj: | ISIT |
| Popis: | We consider a new group testing model wherein each item is a binary random variable defined by an a priori probability of being defective. We assume that each probability is small and that items are independent, but not necessarily identically distributed. The goal of group testing algorithms is to identify with high probability the subset of defectives via non-linear (disjunctive) binary measurements. Our main contributions are two classes of algorithms: (1) adaptive algorithms with tests based either on a maximum entropy principle, or on a Shannon-Fano/Huffman code; (2) non-adaptive algorithms. Under loose assumptions and with high probability, our algorithms only need a number of measurements that is close to the information-theoretic lower bound, up to an explicitly-calculated universal constant factor. We provide simulations to support our results. 23 pages, 12 figures, presented in ISIT 2014, Honolulu |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|