SUPER: Sparse signals with Unknown Phases Efficiently Recovered

Abstract

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 $|A\mathbf{x}|$ with high probability over $A$. Here $|A\mathbf{x}|$ is a vector of component-wise magnitudes of $A\mathbf{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.

19 pages