NIPS 2018
Sun Dec 2nd through Sat the 8th, 2018 at Palais des Congrès de Montréal
Paper ID: 2671 How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?

### Reviewer 1

Post rebuttal comment: I have read the authors feedback. I recommend the authors to add the discussion about the sharpness of the results to the manuscript in a new section. This is a crucial part which improves the manuscript clarity. ======= There are many existing results in the literature that many recovery problems behave "nice" under restricted isometry property (RIP). This paper has an interesting view of looking at the problem in the other direction, i.e., how much RIP is needed so that all local optima be globally optimal. The paper shows that the RIP is necessary by providing examples that the nice property does not hold for moderate RIP levels. In the reviewer's opinion, the paper tackles an important questions. However, the following concerns prevents the reviewer from giving higher ratings to the paper: -- Many relevant works, e.g. G. Tang et al., is missed and the paper should be placed with respect to these existing results. -- It is not clear whether the RIP levels provided in this work are the optimal sharp bounds.