Sparse Signal Recovery from Quadratic Measurements via Convex Programming

Abstract

In this paper we consider a system of quadratic equations |<z_j, x>|^2 = b_j, j = 1, ..., m, where x in R^n is unknown while normal random vectors z_j in R_n and quadratic measurements b_j in 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 non-zero, then by solving a convex optimization program, we can solve for x up to a multiplicative constant with high probability, provided that k <= O((m/log n)^(1/2)). On the other hand, we prove that k <= O(log n (m)^(1/2)) is necessary for a class of naive convex relaxations to be exact.

References in corpus (1)

• On signal reconstruction without noisy phase

Cited by in corpus (13)

• Self-Calibration and Biconvex Compressive Sensing
• Convex Optimization Approaches for Blind Sensor Calibration using Sparsity
• Sparse Phase Retrieval: Convex Algorithms and Limitations
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• Denoising Poisson Phaseless Measurements via Orthogonal Dictionary Learning
• New Conditions for Sparse Phase Retrieval
• Near-optimal phase retrieval of sparse vectors
• On Conditions for Uniqueness in Sparse Phase Retrieval
• Conditions for Existence of Dual Certificates in Rank-One Semidefinite Problems
• Fast and Robust Compressive Phase Retrieval with Sparse-Graph Codes
• Fast Compressive Phase Retrieval from Fourier Measurements
• One-Dimensional Phase Retrieval: Regularization, Box Relaxation and Uniqueness
• Balancing Sparsity and Rank Constraints in Quadratic Basis Pursuit