Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow.

This paper presents a new algorithm, termed truncated amplitude flow (TAF), to recover an unknown vector x from a system of quadratic equations of the form yi = |〈ai, x〉|2, where ai's are given random measurement vectors. This problem is known to be NP-hard in general. We prove that as soon as the number of equations is on the order of the number of unknowns, TAF recovers the solution exactly (up ...