Phase Retrieval using Alternating Minimization
Phase retrieval problems involve solving linear equations, but with missing sign (or phase, for complex numbers). Over the last two decades, a popular generic empirical approach to the many variants of this problem has been one of alternating minimization; i.e. alternating between estimating the missing phase information, and the candidate solution. In this paper, we show that a simple alternating minimization algorithm geometrically converges to the solution of one such problem -finding a vector x from y, A, where y = |A T x| and |z| denotes a vector of element-wise magnitudes of z -under the assumption that A is Gaussian. Empirically, our algorithm performs similar to recently proposed convex techniques for this variant (which are based on "lifting" to a convex matrix problem) in sample complexity and robustness to noise. However, our algorithm is much more efficient and can scale to large problems. Analytically, we show geometric convergence to the solution, and sample complexity that is off by log factors from obvious lower bounds. We also establish close to optimal scaling for the case when the unknown vector is sparse. Our work represents the only known theoretical guarantee for alternating minimization for any variant of phase retrieval problems in the non-convex setting.
This paper presents a simple modification of the 
      alternating minimization algorithm for phase retrieval and analysis to 
      prove its convergence. In phase retrieval the measurement model is based 
      on a linear system y = A x where the common term y (the measurements) 
      is known up to the sign or phase, A is given and one needs to find x. 
      The modification lies in the initialization. Prior alternating 
      minimization algorithms used a random guess for the reconstructed 
      signal x. The proposed modification is to use the main singular vector 
      of a matrix built with a subset of columns of A and the corresponding 
      entries of the vector y. Then, at each iteration of the alternating 
      minimization a new subset of the columns of A and the corresponding 
      entries of y is used until no columns are left. The analysis shows 
      that this algorithm can converge to the correct solution within a given 
      error with high probability when the measurements y_i are iid standard 
      complex Gaussians random variables. A second result applies to the 
      case of phase retrieval problems where the unknown signal is sparse. 
      The authors propose to first identify the nonzero entries by a greedy 
      algorithm and then suggest to run the previous phase algorithm only on 
      the nonzero entries. They also characterize the probability that the 
      greedy algorithm finds the correct support of the signal. Quality 
      -- I have tried to verify the proofs in the paper, but it is not 
      feasible to review 17 pages of proofs in the supplementary material... 
      this is more than 3 papers in one. I have looked at some proofs, but I 
      can't see how the authors do some steps. For example, in lines 308-9 I 
      could not verify the inequalities. Besides, the sentence in line 311 
      does not make much sense. I also believe that the solution in C at lines 
      190-1 is missing y and the expression for S at line 199 does not match 
      that in Algorithm 1 at line 1. Probably a square of y is missing. 
      Even if all proofs were correct, what is missing to me is how 
      practical this strategy is. Essentially we have a linear system where 
      the phase/sign of the measurements is lost. The idea is to split this 
      (non)linear system into a collection of (non)linear systems such that 
      each system has enough equations to yield a unique solution and then 
      one can use each system sequentially to arrive at the final solution. 
      The question is then: How many equations does one need to achieve a 
      reasonable convergence with reasonably high probability? To guarantee 
      convergence with high probability one needs a very small \eta in Thm 
      4.4 and this constraints the constant c which in turn provides a lower 
      bound for the number of measurements m. The bound is m > c n (log^3 
      n + k) where k depends on the convergence error and n is the number of 
      entries in the unknown signal. Even with modest c and k values the 
      number of equations m might grow very quickly compared to n. In 
      practice this might make the algorithm quite impractical. We can see 
      in sec 6 at lines 428-9 that a modest m = 6n is used. However, do the 
      constant vary much with real data? I would have liked to see a 
      discussion of the authors on this aspect. Clarity -- 
      The paper is generally well-written and makes an effort in explaining 
      the general idea either before or after a result has been presented. 
      However, I have still found it quite heavy. Also, please provide 
      all the information needed to replicate your experiments. 
      Originality -- The proposed analysis is novel in 
      my opinion. The algorithm perhaps not. Significance -- 
      The fact that this simple modification of the alternating minimization 
      algorithm converges might be useful also to similar problems. I 
      suppose that other researchers might try this algorithm on their 
      problems.