It's been four years since the connection between group testing (all entries on the subject have the grouptesting tag) and compressive sensing/sparse recovery was made clear, see CS: Group Testing and Sparse Signal Recovery, A linear solution to the 12-balls problem and CS: Ain't the Power of Interwebs Great or What ?. I also note that the second blog entry is the starting point of the connection between compressive sensing and computational ghost imaging, wow. Anyhow, to come back to compressive sensing, here is an email exchange with Florent Krzakala:
Dear Igor[ discussion about compressive sensing and group testing ].......Speaking of which, may I point out to a recent work we just put on the arxiv, where we look to a kind of linear group testing problem. Well, what we do is essentially to do CS with O/1 matrix and 0/1 vectors... and use our "magic" matrices...Here is the link:Comments welcomed, as usual!
Thanks Florent !This is interesting on several counts. First this is an 0/1 extension of the sseded matrices that allows one that get beyond the Donoho-Tanner phase transition. and second the matrices are themselves sparse.
Here is the paper: Non-adaptive pooling strategies for detection of rare faulty items by Pan Zhang, Florent Krzakala, Marc Mézard, Lenka Zdeborová. The abstarct reads:
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.
While going over the recent improvements in the group testing fields, I found version 2 of this preprint: Improved Constructions for Non-adaptive Threshold Group Testing by Mahdi Cheraghchi
The basic goal in combinatorial group testing is to identify a set of up to $d$ defective items within a large population of size $n \gg d$ using a pooling strategy. Namely, the items can be grouped together in pools, and a single measurement would reveal whether there are one or more defectives in the pool. The threshold model is a generalization of this idea where a measurement returns positive if the number of defectives in the pool reaches a fixed threshold $u > 0$, negative if this number is no more than a fixed lower threshold $\ell < u$, and may behave arbitrarily otherwise. We study non-adaptive threshold group testing (in a possibly noisy setting) and show that, for this problem, $O(d^{g+2} (\log d) \log(n/d))$ measurements (where $g := u-\ell-1$ and $u$ is any fixed constant) suffice to identify the defectives, and also present almost matching lower bounds. This significantly improves the previously known (non-constructive) upper bound $O(d^{u+1} \log(n/d))$. Moreover, we obtain a framework for explicit construction of measurement schemes using lossless condensers. The number of measurements resulting from this scheme is ideally bounded by $O(d^{g+3} (\log d) \log n)$. Using state-of-the-art constructions of lossless condensers, however, we obtain explicit testing schemes with $O(d^{g+3} (\log d) qpoly(\log n))$ and $O(d^{g+3+\beta} poly(\log n))$ measurements, for arbitrary constant $\beta > 0$.
Let us recall that only four years ago the best pooling was akin to m = O(k^2) deterministic measurement matrices [1]
we now have sparse measurement matrices that have m=k+1 capabilities. One wonders if deterministic construction are not far behind.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment