Randomized recovery for boolean compressed sensing

We consider the problem of boolean compressed sensing, which is alternatively known as group testing. The goal is to recover a small number of defective items in a large set from a few collective binary tests. This problem can be formulated as a binary linear program, which is NP hard in general. To overcome the computational burden, it was recently proposed to relax the binary constraint on the variables, and apply a rounding to the solution of the relaxed linear program. In this paper, we introduce a ran- domized algorithm to replace the rounding procedure. We show that the proposed algorithm considerably improves the success rate by slightly increasing the computational cost.


Presented at:
IEEE International Symposium on Information Theory (ISIT), Istanbul, Turkey, 2013
Year:
2013
Keywords:
Laboratories:




 Record created 2013-02-18, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)