Volkan,
Congrats on the SODA acceptance!
I wrote a small blurb on it on Nuit Blanche today as regards to previous work. Since group testing is exceptionnally important and as a consequence is seen from many different angles and communities, I have made a similar comment to the one I made of Kannan's recent preprint, i.e. if I am coming from the outside, which I really am, I am wondering how the 2007 paper of Mezart or the more recent paper of Krzakala et al fit with your analysis. I used to underestimate the physicists within the context of CS and related fields but since 2011 I think it is important to pay particular attention to their findings.
Cheers,
Igor.
Dear Igor,
We are quite excited about the SODA acceptance. Thanks also a lot for the mention.
You discuss the 2007 paper by Mezard, and the more recent one by Zhang, Krzakala and others in the blog. We think that the more relevant paper in the context of our work is the former, since the latter, among other things, focuses on linear group testing instead of Boolean group testing (as mentioned in the response by Kannan Ramchandran to your earlier blog post).
We actually already found out about Mezard's paper some time after we wrote the initial version, and we will cite it in the final version.
The goals of our paper and Mezard's are similar, seeking sharp thresholds on the number of measurements above which the error probability vanishes, but below which the error probability tends to one. However, the analysis techniques are different, and as we outline below, there is actually very little overlap in terms of results.
Perhaps the main difference is in the relevant regimes of theta (the value such that #defectives ~ (#items)^theta) - we get phase transitions only for sufficiently small theta, whereas Mezard gets phase transitions only for sufficiently large theta. Note that Mezard's beta corresponds to our 1-theta, but the description below use our own convention.
Mezard's analysis uses a few heuristic arguments that are not verified for all theta - in particular, see the comments on short loops just after (9), before (19), and after (29). They give arguments (some rigorous and some heuristic) revealing for which choices of beta this "short loops" assumption should be valid, and it appears that the best they get is $beta < 1/6$ ($ theta > 5/6 $) rigorously, and $ beta < 1/3 $ ($ theta > 2/3 $) non-rigorously. In fact, on Page 10 they give numerical simulations showing that the assumption is *invalid* for beta = 2/3 (theta = 1/3). There is also mention of "replica symmetry" just before (35) - this technique has been used a fair bit in information-theoretic studies, and while we are not quite familiar with it ourselves, our understanding is that it is known to be rigorous in some cases but not others.
In contrast, the main outcome of our analysis is a rigorous phase transition for $ theta < 1/3 $, which does not overlap with the regime where Mezard's analysis is rigorous. To the best of our judgement, Mezard's analysis does not recover our thresholds in this regime, even heuristically. Our results reveal that Bernoulli matrix designs are asymptotically optimal in this regime, even matching the optimal thresholds for adaptive measurements. In contrast, the discussion around (43) in Mezard's paper suggests that different designs (the ones they call R-R and R-P) are better for large theta (small beta). It might be interesting to see if such designs can also be handled in our framework.
We also briefly mention two additional contributions in our paper: Sharp thresholds for a noisy setting, and nearly-sharp bounds for the case of partial recovery.
We hope that this response is useful.
Jon & Volkan
-------
Prof. Volkan Cevher
Laboratory for Information and Inference Systemshttp://lions.epfl.ch
Credits: NASA/JHUAPL/SwRI)
Closer Look: Majestic Mountains and Frozen Plains:
Just 15 minutes after its closest approach to Pluto on July 14, 2015,
NASA’s New Horizons spacecraft looked back toward the sun and captured
this near-sunset view of the rugged, icy mountains and flat ice plains
extending to Pluto’s horizon. The smooth expanse of the informally named
Sputnik Planum (right) is flanked to the west (left) by rugged
mountains up to 11,000 feet (3,500 meters) high, including the
informally named Norgay Montes in the foreground and Hillary Montes on
the skyline. The backlighting highlights more than a dozen layers of
haze in Pluto’s tenuous but distended atmosphere. The image was taken
from a distance of 11,000 miles (18,000 kilometers) to Pluto; the scene
is 230 miles (380 kilometers) across.
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