Paper ID: 469
Title: Provable Non-convex Phase Retrieval with Outliers: Median TruncatedWirtinger Flow

Review #1
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): See below.

Clarity - Justification: See below.

Significance - Justification: See below.

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): The paper presents a method for phase retrieval with outliers. In particular, the measurement model is y_i = |< a_i, x >|^2 + \eta_i where \eta_i is non-zero only over a small fraction of observations. The paper studies an iterative method which essentially computes median of the residual and ignores all the measurements beyond certain multiple of the median value.  The paper guarantees exact recovery of x in linear time.   Comments: a. The result is novel and interesting. In particular, analyzing measurements conditioned on them being within certain error range is interesting.  Also, the paper allows for a constant fraction of measurements to be corrupted which is powerful.  b. Only weak point of the paper is the motivation to study such a problem, especially in the setting specified in the paper. Due to initialization scheme etc, the result is restricted to Gaussian measurements which have very limited application in general. Moreover, presence of several outliers for such models is not well motivated.  c. The removal of outlier measurements is similar to the hard thresholding based robust regression algorithm studied in Bhatia et al., NIPS'2015. Hence, it would be useful if authors can discuss the techniques of the two papers and if there is a more unified theoretical analysis.  d. In general, the paper is well-written and is enjoyable to read.  

=====

Review #2
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): This paper considers the problem of phase retrieval (i.e. solving systems of quadratic equations) in the presence of arbitrary, gross perturbations. The problem and its specific instantiation in the present paper is well-formulated and motivated from applications in imaging.  The authors - modify the truncated Wirtinger Flow (TWF) algorithm of Candes and Chen and use sample medians instead of means at both initialization, and cleanup stages to ensure robustness against gross corruptions.  - they prove that, at the logarithmic cost in sample complexity, the proposed median TWF algorithm is robust to linearly many corruptions in observations.  - they provide compelling empirical evidence that the algorithm outperforms previous methods in terms of robustness. - their analysis can hopefully be ported to other settings wherein using sample medians can assist in robust estimation in the presence of outliers.

Clarity - Justification: The paper is well written, motivated and organized. The results are easy to find, stated in a clear fashion and are very interesting.  

Significance - Justification: The paper provides a substantial contribution in terms of solving the problem presented. Moreover, the proof techniques are likely to be of wider interest than the present paper itself. 

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): Minor comments - line 95: m is on the order of n (instead of: m is on the order of O(n)) - related work: gradient descent type algorithms following spectral initialization goes back to work by Keshavan et al for matrix completion 

=====

Review #3
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): This paper presents an extension of the Truncated Wirtinger Flow (TWF) algorithm for phase retrievals with corrupted observations. By replacing the mean with median in the truncation step, the modified TWF algorithm is shown to be robust against a constant fraction of outliers.

Clarity - Justification: I find the presentation of the paper easy to follow.

Significance - Justification: The robust version of the phase retrieval problem is a natural extension of the setting studied in previous paper. The modification of the TWF algorithm is straightforward, and the analysis makes use of the techniques developed in Candes-Li-Soltanolkotabi and Chen-Candes. Achieving robustness against a constant fraction of outliers is also not too surprising given existing results in robust regression and low rank estimation.  The proof does require some new arguments due to the use of the median, including deriving properties of the quantiles as well as an epsilon net argument applied to median related quantities, which I find interesting. 

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): Overall I think the results in this paper is a useful extension to the TWF algorithm for phase retrieval, and some of the proof techniques are interesting.  I do wonder to what extent the results are tied to the Gaussian assumption on the measurement vectors a_i. Does sub-Gaussianity suffice? What about other measurement procedures that are more suitable for actual implementation?  Can we achieve a stronger error bound if one imposes an additional independence assumption on the dense noise w? 

=====