EPFL

Algo+LMA

This shows you the differences between two versions of the page.

— |
en:group:semsem:all:20090114 [2016/06/23 11:26] (current) |
||
---|---|---|---|

Line 1: | Line 1: | ||

+ | |||

+ | ---- dataentry seminar ---- | ||

+ | date_dt : 2009.01.14 | ||

+ | title : Noise-Resilient Group Testing: Limitations and Constructions | ||

+ | speaker : Mahdi Cheraghchi | ||

+ | affiliation : ALGO | ||

+ | time : 16h15-17h15 | ||

+ | room : BC129 | ||

+ | table : seminars | ||

+ | =================== | ||

+ | template:datatemplates:seminar | ||

+ | ----------------------- | ||

+ | |||

+ | |||

+ | ==== abstract ==== | ||

+ | We study combinatorial group testing schemes for learning $d$-sparse boolean vectors using highly unreliable disjunctive measurements. We consider an adversarial noise model that only limits the number of false observations, and show that any noise-resilient scheme in this model can only approximately reconstruct the sparse vector. On the positive side, we take this barrier to our advantage and show that approximate reconstruction (within a satisfactory degree of approximation) allows us to break the information theoretic lower bound of $\Omega(d^{2} \log(n)/\log(d))$ that is known for exact reconstruction of $d$-sparse vectors of length $n$ via non-adaptive measurements, by a multiplicative factor of almost linear in $d$. \\ Specifically, we give simple randomized constructions of non-adaptive measurement schemes, with $m=O(d \log(n))$ measurements, that allow efficient reconstruction of d-sparse vectors up to $O(d)$ false positives even in the presence of $\deltam$ false positives and $O(m/d)$ false negatives within the measurement outcomes, for any constant $\delta < 1$. We show that, information theoretically, none of these parameters can be substantially improved without dramatically affecting the others. Furthermore, we obtain several explicit constructions, in particular one matching the randomized trade-off but using $m = O(d^{1+o(1)}\log(n))$ measurements. We also obtain explicit constructions that allow fast reconstruction in time polynomial in $m$, which would be sublinear in $n$ for sufficiently sparse vectors. \\ An immediate consequence of our result is an adaptive scheme that runs in only two non-adaptive "rounds" and exactly reconstructs any $d$-sparse vector using a total $O(d \log(n))$ measurements, a task that would be impossible in one round and fairly easy in $O(\log(n/d))$ rounds. | ||