The matrix sensing problem is an important low-rank optimization problem that has found a wide range of applications, such as matrix completion, phase synchornization/retrieval, robust PCA, and power system state estimation. In this work, we focus on the general matrix sensing problem with linear measurements that are corrupted by random noise. We investigate the scenario where the search rank $r$ is equal to the true rank $r^*$ of the unknown ground truth (the exact parametrized case), as well as the scenario where $r$ is greater than $r^*$ (the overparametrized case). We quantify the role of the restricted isometry property (RIP) in shaping the landscape of the non-convex factorized formulation and assisting with the success of local search algorithms. First, we develop a global guarantee on the maximum distance between an arbitrary local minimizer of the non-convex problem and the ground truth under the assumption that the RIP constant is smaller than $1/(1+\sqrt{r^*/r})$. We then present a local guarantee for problems with an arbitrary RIP constant, which states that any local minimizer is either considerably close to the ground truth or far away from it. More importantly, we prove that this noisy, overparametrized problem exhibits the strict saddle property, which leads to the global convergence of perturbed gradient descent algorithm in polynomial time. The results of this work provide a comprehensive understanding of the geometric landscape of the matrix sensing problem in the noisy and overparametrized regime.
翻译:矩阵感知问题是一个重要的低秩优化问题,并已在矩阵补全、相位同步/检索、鲁棒PCA和电力系统状态估计等领域得到了广泛应用。本文研究线性测量被随机噪声污染的矩阵感知问题。我们探讨搜索秩$r$等于未知真实秩$r^*$(精确参数化情况)以及$r$大于$r^*$(超参数化情况)的情况。我们量化了受限等距性质(RIP)在塑造非凸分解问题的景观和辅助局部搜索算法成功方面的作用。首先,在RIP常数小于$1/(1+\sqrt{r^*/r})$的假设下,我们对任意局部最小化器与基准真值之间的最大距离给出了全局保证。接着我们针对具有任意RIP常数的问题提出了局部保证,即任何局部最小化器要么接近真值,要么偏离真值较远。更重要的是,我们证明了在存在噪声和超参数化的情况下,该问题呈现出严格鞍点特性,这导致了扰动梯度下降算法的全局收敛,且收敛时间为多项式时间。本文的结果提供了矩阵感知问题在噪声和超参数化情况下的几何景观的全面理解。