Sparse Signal Recovery from Quadratic Measurements via Convex Programming

2012/09/21 by Xiaodong Li, Vladislav Voroninski, Li, Xiaodong +1 · 6 citations
Engineering · Medicine · #Advanced MRI Techniques and Applications #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Microwave Imaging and Scattering Analysis #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1209.4785

openalex publication_date 2012/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we consider a system of quadratic equations ||² = b_j, j = 1, ..., m, where x in Rⁿ 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.

Cited by

• Recovery Performance of PhaseLift for Phase Retrieval from Coded Diffraction Patterns
• Simultaneously Structured Models with Application to Sparse and Low-rank\n Matrices
• A convex lifting approach for the Calderón problem
• Phase retrieval with rank d measurements -- descending algorithms phase transitions
• Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view
• Phase transition of descending phase retrieval algorithms

Related

• The local convexity of solving systems of quadratic equations
• Sparse linear regression with compressed and low-precision data via\n concave quadratic programming
• Simple Bounds for Recovering Low-complexity Models
• Convex recovery of a structured signal from independent random linear measurements
• Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization