Sparse Signal Recovery from Quadratic Measurements via Convex Programming

Source abstract

In this paper we consider a system of quadratic equations $|\langle \bm{z_j}, \bm{x}\rangle|^2=b_j, j=1,\ldots,m$, where $\bm{x} \in \mathbb{R}^n$ is unknown while normal random vectors $\bm{z_j} \in \mathbb{R}^n$ and quadratic measurements $b_j \in \mathbb{R}$ are known. The system is assumed to be underdetermined, i.e., $m<n$. We prove that if there exists a sparse solution $\bm{x}$, i.e., at most $k$ components of $\bm{x}$ are nonzero, then by solving a convex optimization program, we can solve for $\bm{x}$ up to a multiplicative constant with high probability, provided that $k\leq O(\sqrt{m\over{\log n}})$. On the other hand, we prove that $k \leq O(\log n\sqrt{m})$ is necessary for a class of natural convex relaxations to be exact.