tag:blogger.com,1999:blog-6141980.post8293322887910174978..comments2021-01-13T10:49:25.392-06:00Comments on Nuit Blanche: A stunning development in breaking the Donoho-Tanner phase transition ?Igorhttp://www.blogger.com/profile/17474880327699002140noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-6141980.post-16552184261165681702011-09-24T15:26:34.738-05:002011-09-24T15:26:34.738-05:00I agree with anonymous, but here is where I am a l...I agree with anonymous, but here is where I am a little bit more optimistic:<br /><br />Besides the work of Pfister et al, this is the first time i see an actual phase transition much different than the DT transition. The paper states that they are indeed aware of that result and tweeked it to get better performance by avoiding some "dynamic phase transition"<br /><br />I look forward to somebody's implementation ofIRL1 doing noticeably better than the DT transition, Bob Sturm's computations show over and over that most of these algorithms do not do much better than DT. This is why this algo is qualitatively different from most other attempts I have seen so far.<br /><br />Finally, while a result with the issue of noise will be much welcomed, we have certainly seen folks coming up with well designed measurement matrices and attendant solvers, so I don't think this particularity should be much of a concern for the time being. On the contrary, their measurement matrices seem to be pretty sparse, i.e. It reminds me of the sparse measurement matrices of Indyk and Berinde (and their attendant specifically designed reconstruction solvers).<br /><br />The DT transition really show how far most known polynomial algorithms fare. This new algo is quadratic/polynomial and pushes the boundary up. The NP region seems to now be above k = m.<br /><br />Cheers,<br /><br />Igor.<br /><br />Igor.Igorhttps://www.blogger.com/profile/17474880327699002140noreply@blogger.comtag:blogger.com,1999:blog-6141980.post-10297840486538578642011-09-24T12:11:55.295-05:002011-09-24T12:11:55.295-05:00There seems to be a little bit of confusion here.....There seems to be a little bit of confusion here... <br />When the signals are exactly sparse and there is no noise, the Donoho-Tanner phase transition characterizes the limits of L1 minimization. As it happens that L1 minimization outperforms other reconstruction algorithms (such as SP, CoSaMP, IHT), this phase transition also seems to apply to these algorithms. However, it will not apply to some other algorithms that outperform L1 minimization, like iteratively reweighted L1. <br />We also do know what the limit of compressive sensing is in this noise-free setting. It is 2*s measurements, where s is the number of non-zero coefficients in the signal (note this is independent of signal dimension). Furthermore, there are polynomial time algorithms coming from coding theory that achieve this limit (although they are not stable in the presence of noise). This limit can be loosened to s+1 measurements if reconstruction with probability 1 is acceptable (hence the red line in their phase-transition figures). <br />From what I can tell after skimming through this paper, the authors also follow a coding theory approach: They design their own measurement matrices and reconstruction algorithms <i> for these matrices </i>, and outperform L1 minimization. It seems all their results are on the exact sparse signals with no measurement noise, and they mention that the stability of the algorithm will be studied in further work.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6141980.post-33455118576403333322011-09-24T03:44:49.513-05:002011-09-24T03:44:49.513-05:00Bob,
Good point but I don' t think so. Somewh...Bob,<br /><br />Good point but I don' t think so. Somewhere in that paper there is an additional constraint. I need the authors to identify it more plainly.Igorhttps://www.blogger.com/profile/17474880327699002140noreply@blogger.comtag:blogger.com,1999:blog-6141980.post-5593998328634564342011-09-24T00:59:04.190-05:002011-09-24T00:59:04.190-05:00But wouldn't this mean P=NP?But wouldn't this mean P=NP?Bob et Carlahttps://www.blogger.com/profile/09965549060044467221noreply@blogger.comtag:blogger.com,1999:blog-6141980.post-74392254172021811942011-09-23T11:25:36.765-05:002011-09-23T11:25:36.765-05:00Definitely not sure what to make of this. It's...Definitely not sure what to make of this. It's a very big result if it holds up.Anonymoushttps://www.blogger.com/profile/07835164854514314231noreply@blogger.com