This paper concerns the problem of recovering an unknown but structured
signal $x \in R^n$ from $m$ quadratic measurements of the form
$y_r=|<a_r,x>|^2$ for $r=1,2,...,m$. We focus on the under-determined setting
where the number of measurements is significantly smaller than the dimension of
the signal ($m<<n$). We formulate the recovery problem as a nonconvex
optimization problem where prior structural information about the signal is
enforced through constrains on the optimization variables. We prove that
projected gradient descent, when initialized in a neighborhood of the desired
signal, converges to the unknown signal at a linear rate. These results hold
for any constraint set (convex or nonconvex) providing convergence guarantees
to the global optimum even when the objective function and constraint set is
nonconvex. Furthermore, these results hold with a number of measurements that
is only a constant factor away from the minimal number of measurements required
to uniquely identify the unknown signal. Our results provide the first provably
tractable algorithm for this data-poor regime, breaking local sample complexity
barriers that have emerged in recent literature. In a companion paper we
demonstrate favorable properties for the optimization problem that may enable
similar results to continue to hold more globally (over the entire ambient
space). Collectively these two papers utilize and develop powerful tools for
uniform convergence of empirical processes that may have broader implications
for rigorous understanding of constrained nonconvex optimization heuristics.
The mathematical results in this paper also pave the way for a new generation
of data-driven phase-less imaging systems that can utilize prior information to
significantly reduce acquisition time and enhance image reconstruction,
enabling nano-scale imaging at unprecedented speeds and resolutions.

本文针对 $m<<n$ 的欠定情况，在优化变量上施加先前的结构信息，将恢复问题形式化为非凸优化问题，并证明了在任何不变约束集下，投影梯度下降收敛于未知信号的线性速率，这为此数据贫瘠的场景提供了第一个可证实的算法，为理解约束非凸优化启发了强有力的工具，其数学结果为数据驱动的相位成像系统开辟了一种新的方向。