论文标题
关于二次可行性问题的样品复杂性和优化景观
On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems
论文作者
论文摘要
我们考虑从$ m $ m $ quadratic测量$ \ {\ langle a_i \ mathbf {x}，\ mathbf {x} \ rangle \ rangle \ rangle \} _ = 1}的问题，要恢复复杂的向量$ \ mathbf {x} \ in \ mathbb {c}^n $从$ m $ m $ quadratic测量中$ \ {\ langle a_i \ mathbf {x}，\ mathbf {x} \ rangle \ rangle \} \ rangle \}这个问题称为二次可行性，涵盖了众所周知的相位检索问题，并在包括电力系统状态估计和X射线晶体学（包括电力系统状态估算）的广泛领域中应用。通常，不仅要解决的二次可行性问题np-hard，而且实际上可能是无法识别的。在本文中，我们确定了该问题变为{可识别}的条件，并且在矩阵$ \ {a_i \} _ {i = 1}^m $的情况下，进一步证明了等轴测属性。此外，我们探索了此问题的非convex {优化}公式，并建立了相关优化景观的显着特征，该格局可以使具有任意初始化的梯度算法融合到具有很高概率的\ emph {全球最佳}点。我们的结果还揭示了在这些情况下成功识别可行解决方案的样本复杂性要求。
We consider the problem of recovering a complex vector $\mathbf{x}\in \mathbb{C}^n$ from $m$ quadratic measurements $\{\langle A_i\mathbf{x}, \mathbf{x}\rangle\}_{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.
