Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
复制标题
DOI：
--
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Dejiao Zhang;L. Balzano
中科院分区：
文献类型：
--
作者：
Dejiao Zhang;L. Balzano
在各种情况下已经观察到，梯度下降方法在解决低阶矩阵因式分解问题方面取得了巨大的成功，尽管相关问题的表述是非凸的。我们处理这个场景的一个特定实例，其中我们寻找由流数据矩阵跨越的$d$维子空间。我们应用自然一阶增量梯度下降法，将梯度法约束到Grassmanian。在本文中，我们提出了一种自适应步长方案，它对于无噪声的情况是贪婪的，在每个数据索引$t$处最大化我们的收敛度量的改善，并且对于有噪声的情况产生预期的改善。我们证明了，在无噪声数据的情况下，该方法从任意随机初始化收敛到问题的全局最小值。对于有噪声的数据，我们给出了该算法每次迭代的期望收敛速度。
It has been observed in a variety of contexts that gradient descent methods have great success in solving low-rank matrix factorization problems, despite the relevant problem formulation being non-convex. We tackle a particular instance of this scenario, where we seek the $d$-dimensional subspace spanned by a streaming data matrix. We apply the natural first order incremental gradient descent method, constraining the gradient method to the Grassmannian. In this paper, we propose an adaptive step size scheme that is greedy for the noiseless case, that maximizes the improvement of our metric of convergence at each data index $t$, and yields an expected improvement for the noisy case. We show that, with noise-free data, this method converges from any random initialization to the global minimum of the problem. For noisy data, we provide the expected convergence rate of the proposed algorithm per iteration.