On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems

Abstract

We consider the problem of recovering a complex vector $\mathbf{x}\in {\mathbb{C}}^n$ from $m$ quadratic measurements $\{⟨A_i\mathbf{x},\mathbf{x}⟩{\}}_{i=1}^m$. This problem, known as quadratic feasibility, encompasses the well known phase retrieval problem and has applications in a wide range of important areas including power system state estimation and x-ray crystallography. In general, not only is the the quadratic feasibility problem NP-hard to solve, but it may in fact be unidentifiable. In this paper, we establish conditions under which this problem becomes {identifiable}, and further prove isometry properties in the case when the matrices $\{A_i{\}}_{i=1}^m$ are Hermitian matrices sampled from a complex Gaussian distribution. Moreover, we explore a nonconvex {optimization} formulation of this problem, and establish salient features of the associated optimization landscape that enables gradient algorithms with an arbitrary initialization to converge to a \emph{globally optimal} point with a high probability. Our results also reveal sample complexity requirements for successfully identifying a feasible solution in these contexts.

arXiv comment21 pages

References in corpus (6)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Non-convex Optimization for Machine Learning
• Consensus-ADMM for General Quadratically Constrained Quadratic Programming
• A Geometric Analysis of Phase Retrieval
• Concentration of norms and eigenvalues of random matrices
• On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems

Cited by in corpus (1)

• On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems