The problem of phase retrieval is revisited and studied from a fresh perspective. In particular, we establish a connection between the phase retrieval problem and the sensor network localization problem, which allows us to utilize the vast theoretical and algorithmic literature on the latter to tackle the former. Leveraging this connection, we develop a two-stage algorithm for phase retrieval that can provably recover the desired signal. In both sparse and dense settings, our proposed algorithm improves upon prior approaches simultaneously in the number of required measurements for recovery and the reconstruction time. We present numerical results to corroborate our theory and to demonstrate the efficiency of the proposed algorithm. As a side result, we propose a new form of phase retrieval problem and connect it to the complex rigidity theory proposed by Gortler and Thurston.
Another recent approach is based on semidefinite programming and convex relaxation. The basic idea of this approach is to interpret quadratic measurements as linear measurements of a rank-one matrix @math . Then, the phase retrieval problem can be equivalently rewritten as a rank-minimization problem. Subsequently, by using a convex surrogate such as the trace norm to replace the rank function, we obtain a semidefinite program that can be solved in polynomial-time by off-the-shelf solvers. PhaseLift proposed by Cand @cite_7 and PhaseCut by @cite_22 are examples of such an approach. The drawback of this approach is its high computational complexity. Indeed, the complexities of PhaseLift and PhaseCut to return a solution of @math accuracy are @math and @math , respectively. Both methods use an ensemble of @math i.i.d. standard @math -dimensional Gaussian random vectors. Assuming the signal @math is @math -sparse (i.e., @math has at most @math non-zero components), the @math -regularized version of PhaseLift @cite_11 improves the number of required Gaussian measurements to @math . Nonetheless, this algorithm again requires solving a semidefinite program and hence has a similar computational complexity as PhaseLift and PhaseCut. Therefore, this approach is not applicable to large-scale phase retrieval problems in practice.
@cite_22 @cite_7 @cite_11
2078397124 2963855280
Suppose we wish to recover a signal amssym @math from m intensity measurements of the form , ; that is, from data in which phase information is missing. We prove that if the vectors are sampled independently and uniformly at random on the unit sphere, then the signal x can be recovered exactly (up to a global phase factor) by solving a convenient semidefinite program–-a trace-norm minimization problem; this holds with large probability provided that m is on the order of , and without any assumption about the signal whatsoever. This novel result demonstrates that in some instances, the combinatorial phase retrieval problem can be solved by convex programming techniques. Finally, we also prove that our methodology is robust vis-a-vis additive noise. © 2012 Wiley Periodicals, Inc. In this paper we consider a system of quadratic equations @math , where @math is unknown while normal random vectors @math and quadratic measurements @math are known. The system is assumed to be underdetermined, i.e., @math . We prove that if there exists a sparse solution @math , i.e., at most @math components of @math are nonzero, then by solving a convex optimization program, we can solve for @math up to a multiplicative constant with high probability, provided that @math . On the other hand, we prove that @math is necessary for a class of natural convex relaxations to be exact.