Structured Signal Recovery From Quadratic Measurements: Breaking Sample Complexity Barriers via Nonconvex Optimization
Structured Signal Recovery From Quadratic Measurements: Breaking Sample Complexity Barriers via Nonconvex Optimization
复制标题
DOI：
10.1109/tit.2019.2891653
复制
发表时间：
2017-02
影响因子：
2.5
通讯作者：
M. Soltanolkotabi
中科院分区：
文献类型：
--
作者：
M. Soltanolkotabi
本文讨论了从$m$的二次测量中恢复一个未知但结构化的信号${x}\ \mathbb {R} ^{n}$的问题，其形式为${y}_{R} = \左|{\langle {a}} {R}，{x}\rangle}\右|^{{2}}$对于${R} ={1},{2},\ldots, {m}$。我们关注的是未确定的设置，其中测量次数明显小于信号的维度（${m}）。我们将恢复问题表述为一个非凸优化问题，其中信号的先验结构信息通过对优化变量的约束来强制执行。我们证明了当在期望信号的邻域初始化时，投影梯度下降以线性速率收敛到未知信号。这些结果适用于任何封闭约束集（凸或非凸），即使目标函数和约束集是非凸的，也提供了对全局最优的收敛保证。此外，这些结果与唯一识别未知信号所需的最小测量数仅相差一个常数因子。我们的研究结果提供了第一个可证明的可处理算法，用于这种数据贫乏的状态，打破了本文中出现的局部样本复杂性障碍。在本文中，我们利用并进一步开发了强大的工具，用于经验过程的一致收敛，这可能对严格理解约束非凸优化启发式具有更广泛的含义。
This paper concerns the problem of recovering an unknown but structured signal ${x}\in \mathbb {R} ^{n}$ from $m$ -quadratic measurements of the form ${y}_{r}= \left |{\langle {a}_{r}, {x}\rangle }\right |^{{2}}$ for ${r}={1},{2},\ldots, {m}$ . We focus on the under-determined setting where the number of measurements is significantly smaller than the dimension of the signal ( ${m} ). 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 the 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 closed constraint set (convex or non-convex) providing convergence guarantees to the global optimum even when the objective function and constraint set are nonconvex. Furthermore, these results hold with a number of measurements that are 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 this paper. In this paper, we utilize and further develop powerful tools for uniform convergence of empirical processes that may have broader implications for rigorous understanding of constrained nonconvex optimization heuristics.