Phase Retrieval via Reweighted Amplitude Flow

This paper deals with finding an n-dimensional solution x to a system of quadratic equations of the form y _i = |〈a _i , x〉| ² for 1 ≤ i ≤ m, which is also known as the generalized phase retrieval problem. For this NP-hard problem, a novel approach is developed for minimizing the amplitude-based leastsquares empirical loss, which starts with a weighted maximal correlation initialization obtainable through a few power or Lanczos iterations, followed by successive refinements based on a sequence of iteratively reweighted gradient iterations. The two stages (initialization and gradient flow) distinguish themselves from prior contributions by the inclusion of a fresh (re)weighting regularization procedure. For certain random measurement models, the novel scheme is shown to be able to recover the true solution x in time proportional to reading the data {(a _i ; y _i )} ₁ ≤i≤m. This holds with high probability and without extra assumption on the signal vector x to be recovered, provided that the number m of equations is some constant c > 0 times the number n of unknowns in the signal vector, namely m > cn. Empirically, the upshots of this contribution are: first, (almost) 100% perfect signal recovery in the high-dimensional (say n ≥ 2000) regime given only an information-theoretic limit number of noiseless equations, namely m = 2n - 1, in the real Gaussian case; and second, (nearly) optimal statistical accuracy in the presence of additive noise of bounded support. Finally, substantial numerical tests using both synthetic data and real images corroborate markedly improved recovery performance and computational efficiency of the novel scheme relative to the state-of-the-art approaches.