Source-linked AI summary
Sparse Signal Recovery from Quadratic Measurements via Convex Programming
Xiaodong Li, Vladislav Voroninski
TL;DR
The paper asks whether sparse signals can be recovered from underdetermined quadratic Gaussian measurements despite non-injectivity and whether naive convex relaxations are optimal. It uses a convex program analyzed through approximate dual certificates, proving high-probability recovery in a sparse regime while identifying a stricter necessary regime for exactness. The results expose a gap between measurement injectivity and recovery by this relaxation.
Problem
Underdetermined quadratic measurements are generally non-injective, creating a need to understand sparse recovery and the limits of convex relaxations.
Method
The paper analyzes a sparsity-promoting convex program for Gaussian quadratic measurements using approximate dual certificates and a modified golfing scheme.
Results
The convex program exactly recovers xxT with high probability under Theorem 1.2, while Theorem 1.3 gives a stricter necessary measurement condition for exactness.
Takeaways & Limitations
The results establish a substantial gap between sufficient measurements for injectivity and those required for recovery through this class of natural convex relaxations.
Takeaways & Limitations
The analysis considers recovery modulo phase and leaves the design of a better support-recovery convex program for future research.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies sparse recovery from underdetermined quadratic Gaussian measurements using convex programming, establishing exact recovery guarantees and sharp limitations for a natural relaxation.
- Problem: Underdetermined quadratic measurements are generally non-injective, but k-sparsity can make the system well-posed under suitable measurement conditions.Each quadratic equation is the union of two linear equations, yielding generally 2^m solutions without structural assumptions.
- Well-posedness: 4k − 1 generic real quadratic measurements and 8k − 2 generic complex measurements suffice for recovery modulo phase.Theorem 1.1 establishes these measurement thresholds for sparse real and complex signals.
- Motivation: Injectivity does not guarantee efficient recovery, motivating convex formulations that exploit sparsity for recovery from fewer than n intensity measurements.The paper contrasts well-posedness with algorithmic recovery and introduces a convex program for this purpose.
- Convex recovery: Theorem 1.2 proves exact recovery by the convex program for IID Gaussian measurements under a sparsity condition and suitable λ, with high probability.The theorem assumes a unit-norm k-sparse signal and standard normal measurement vectors; the stated probability and parameter conditions are given in the source passages.
- Limitations: Theorem 1.3 shows a substantial gap between injectivity and exact recovery through this natural convex relaxation, imposing a stricter measurement requirement.The paper characterizes this as a sharp limitation of the relaxation and leaves improved support-recovery formulations open.
2 The proof of Theorem 1.2
The proof establishes exact recovery by reducing optimality to the construction of an approximate dual certificate, then building that certificate using concentration properties and a golfing scheme. Under the stated Gaussian assumptions and measurement conditions, the certificate forces the target xxT to be the unique minimizer.
- Measurement-operator bounds: The proof analyzes the measurement operator on positive symmetric, rank-2, and general symmetric matrices through high-probability concentration events.These operator bounds are established using sub-exponential random variables and standard random-matrix results.
- Certificate-based recovery: An approximate dual certificate is sufficient to prove that xxT uniquely solves the convex program.The argument uses the certificate together with properties of the measurement operator to eliminate every nonzero feasible perturbation.
- Certificate construction: The certificate has the form Y=A*(v) and is constructed from Gaussian quadratic measurements while satisfying the conditions needed by the optimality lemma.The proof verifies that the certificate is orthogonal to feasible perturbations and controls its components relative to the support subspaces.
- Key lemma: The key lemma controls the certificate construction on the support subspace using rank at most 2 and Gaussian concentration.The proof uses eigenvalue decompositions and truncated Gaussian moments, including β2≈0.9707 and β4≈2.6728.
- Golfing scheme: A golfing scheme partitions the random measurement vectors into l=⌊2 log(n)⌋+3 groups and iteratively constructs certificate components.The resulting probability bounds are combined across groups; the construction is available when m≥(2 log n+3)C1k.
3 The proof of Theorem 1.3
The proof derives a necessary optimality condition for xxT through a dual certificate and then shows that random Gaussian measurements violate this condition in the relevant sparsity regime. This yields the stated impossibility result for the class of naive convex relaxations.
- High-probability event: A high-probability event is defined to control all admissible coefficients, matrices, and Gaussian measurement vectors used in the contradiction argument.The proof combines an auxiliary random-matrix lemma with a union-bound-style event construction.
- Gaussian geometry: The Gaussian vectors are completed to an orthonormal basis so that their span can be analyzed through independent components.The first basis vectors depend on one Gaussian family and remain independent of the second family, enabling a chi-square bound.
- Conclusion: Combining the two cases establishes the claimed necessary condition for xxT to be optimal with the stated probability bounds.The conclusion follows after putting Case 1 and Case 2 together.
- Case analysis: The proof partitions the measurements into two groups and studies the resulting spectral decomposition and sign-separated coefficient sets.The partition uses m1 and m2 with m1+m2=m, while the argument separately tracks positive and negative coefficients.
- Necessary optimality condition: Optimality of xxT requires a dual certificate Y satisfying semidefinite and tangent-space conditions.The subgradient condition is rewritten as the existence of Y with S⪯0 and PT(S)=0.
4 Discussion
The paper establishes sharp guarantees for sparse recovery through convex programming, while identifying limitations of a proposed relaxation and leaving improved support-recovery formulations open.
- Theoretical guarantees for sparse-signal recovery from quadratic Gaussian measurements are sharp for a class of recently proposed convex relaxations.
- Unlike classical compressed sensing, naive convex relaxation requires more measurements for recovery than are needed for well-posedness.
- The paper leaves open whether a better convex program can formulate the right support-recovery problem and narrow this gap.
- Theorem 1.3 limits program (1.4) for exact recovery because recovering the support may suffice to recover x through PhaseLift.