  Suppose we wish to recover a signal x in C^n from m intensity measurements of
the form |<x,z_i>|^2, i = 1, 2,..., m; that is, from data in which phase
information is missing. We prove that if the vectors z_i 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 n log n, 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.
