SUPER: Sparse signals with Unknown Phases Efficiently Recovered

Suppose $\mathbf{x}$ is any exactly $k$-sparse vector in ${\mathbb{C}}^n$. We present a class of phase measurement matrix $A$ in ${\mathbb{C}}^{m\times n}$, and a corresponding algorithm, called SUPER, that can resolve $\mathbf{x}$ up to a global phase from intensity measurements $\mathrm{\mid }A\mathbf{x}\mathrm{\mid }$ with high probability over $A$. Here $\mathrm{\mid }A\mathbf{x}\mathrm{\mid }$ is a vector of component-wise magnitudes of $A{\bf x}$. The SUPER algorithm is the first to simultaneously have the following properties: (a) it requires only $\mathcal{O}(k)$ (order-optimal) measurements, (b) the computational complexity of decoding is $\mathcal{O}(k\log k)$ (near order-optimal) arithmetic operations.