Fast recovery of n-component vector from O(n log n) random magnitude measurements

You need to know: Set of complex numbers ${\mathbb C}$ , absolute value $|z|$ of $z \in {\mathbb C}$ , set ${\mathbb C}^n$ of vectors with n complex coordinates, inner product $(x,y)=\sum\limits_{i=1}^n x_iy_i$ in ${\mathbb C}^n$ , unit sphere in ${\mathbb C}^n$ , polynomial-time algorithm, probability, sampling independently and uniformly from a set, big O notation.

Background: Let $x \in {\mathbb C}^n$ , and let $z_1, \dots z_m$ be vectors independently and uniformly sampled from the unit sphere in ${\mathbb C}^n$ . Numbers $b_i=|(x,z_i)|^2, \, i=1,2,\dots,m$ are called magnitude measurements of x.

The Theorem: In September 2011, Emmanuel Candes, Thomas Strohmer, and Vladislav Voroninski submitted to Communications on Pure and Applied Mathematics a paper in which they proved the existence of positive constants $c_0$ and $\gamma$ such that an arbitrary $x \in {\mathbb C}^n$ can be exactly recovered from $m \geq c_0 n \log n$ magnitude measurements in polynomial time with probability at least $1-3e^{-\gamma m/n}$ .

Short context: In applications, x represents a signal, and $(x,z_i)$ represent measurements. In many applications, only the absolute value of $(x,z_i)$ can be measured – this is called “magnitude measurements”. If vectors $z_i$ are fixed and given, the problem of recovering x from $b_i$ may be computationally infeasible. The Theorem states, however, that we can select $z_i$ at random, and recover x efficiently with high probability after the number of measurements not much higher than the dimension.