Reviews: Learning without the Phase: Regularized PhaseMax Achieves Optimal Sample Complexity

This paper presents a sharp asymptotic analysis of the regularized phase-max estimator for structured phase retrieval (PR) problems. The phase-max algorithm is a recently proposed Linear Programming based estimator for PR. The finite sample as well as the sharp asymptotic performance of phase-max for unstructured phase retrieval was well understood from prior work. The authors propose a natural modification by penalizing the usual phase-max objective with a regularizer f . For structured PR, prior work showed that for a k -sparse signal vector, L1-penalized phase-max recovers the signal with m O(klog(n/k)) samples given a good enough initialization.