Sparse Signal Recovery from Quadratic Measurements via Convex Programming

In this paper we consider a system of quadratic equations | zⱼ, x|²=bⱼ, j=1,…,m, where x ∈ Rⁿ is unknown while normal random vectors zⱼ ∈ Rⁿ and quadratic measurements bⱼ ∈ R are known. The system is assumed to be underdetermined, i.e., $m<n$. We prove that if there exists a sparse solution x, i.e., at most k components of x are nonzero, then by solving a convex optimization program, we can solve for x up to a multiplicative constant with high probability, provided that k≤ O(√mlog n). On the other hand, we prove that k ≤ O(log n√m) is necessary for a class of natural convex relaxations to be exact.