Solving Quadratic Equations via PhaseLift When There Are About as Many Equations as Unknowns

This note shows that we can recover any complex vector exactly from on the order of n quadratic equations of the form |aOE (c) a (i) ,x (0)>|(2)=b (i) , i=1,aEuro broken vertical bar,m, by using a semidefinite program known as PhaseLift. This improves upon earlier bounds in CandSs et al. (Commun. Pure Appl. Math. 66:1241-1274, 2013), which required the number of equations to be at least on the order of nlogn. Further, we show that exact recovery holds for all input vectors simultaneously, and also demonstrate optimal recovery results from noisy quadratic measurements; these results are much sharper than previously known results.