We consider the problem of recovering a complex vector x ∈ ℂn from m quadratic measurements $left{ {leftlangle {{A_i}{mathbf{x}},{mathbf{x}}} ightangle } ight}_{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 $left{ {{A_i}} ight}_{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 globally optimal point with a high probability. Our results also reveal sample complexity requirements for successfully identifying a feasible solution in these contexts.
展开▼
机译：我们考虑恢复复矢量x∈problem的问题
n
从m个二次测量中$ \ left \ {{\ left \ langle {{A_i} {\ mathbf {x}}，{\ mathbf {x}}} \ right \ rangle} \ right \} _ {i = 1} ^ m $。这个问题被称为二次可行性，涵盖了众所周知的相位恢复问题，并在包括电力系统状态估计和X射线晶体学在内的许多重要领域中得到了应用。一般而言，二次可行性问题NP不仅难以解决，而且实际上可能无法确定。在本文中，我们建立了可识别此问题的条件，并进一步证明了当矩阵$ \ left \ {{{{A_i}} \ right \} _ {i = 1} ^ m $是Hermitian时的等距特性从复杂的高斯分布中采样的矩阵。此外，我们探索了此问题的非凸优化公式，并建立了相关优化景观的显着特征，该特征使具有任意初始化的梯度算法能够以很高的概率收敛到全局最优点。我们的结果还揭示了在这些情况下成功识别可行解决方案的示例复杂性要求。
展开▼
