On the matrix square root via geometric optimization
On the matrix square root via geometric optimization
复制标题
通过几何优化求矩阵平方根
DOI：
10.13001/1081-3810.3196
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Sra
中科院分区：
文献类型：
--
作者：
S. Sra
本文是由Jain等人（\textit{\textcolor{blue}{arXiv:1507.05854}}）的预印本“\emph{通过非凸局部搜索计算矩阵}平方根”引发的，该预印本分析了计算正定矩阵平方根的梯度下降法。与\citet{jain2015}的说法相反，我们的实验表明，类似牛顿的方法可以快速可靠地计算矩阵平方根，即使对于高度病态的矩阵，也不需要交换性。我们观察到梯度下降法的收敛速度很慢，主要是由于步长很小和条件不良。我们推导了一种基于测地线凸性的替代一阶方法：我们的方法允许透明的收敛分析（$< 1$页面），获得线性速率，并且即使对秩缺乏问题也显示可靠的收敛。虽然我们的方法优于梯度下降法，但最终也优于著名的缩放牛顿法。然而，我们工作的主要价值在于它的概念价值：它表明，对于导出基于梯度的矩阵平方根方法，\emph{正定矩阵的流形几何视图可能比欧几里得视图更有利}。
This paper is triggered by the preprint "\emph{Computing Matrix Squareroot via Non Convex Local Search}" by Jain et al. (\textit{\textcolor{blue}{arXiv:1507.05854}}), which analyzes gradient-descent for computing the square root of a positive definite matrix. Contrary to claims of~\citet{jain2015}, our experiments reveal that Newton-like methods compute matrix square roots rapidly and reliably, even for highly ill-conditioned matrices and without requiring commutativity. We observe that gradient-descent converges very slowly primarily due to tiny step-sizes and ill-conditioning. We derive an alternative first-order method based on geodesic convexity: our method admits a transparent convergence analysis ($< 1$ page), attains linear rate, and displays reliable convergence even for rank deficient problems. Though superior to gradient-descent, ultimately our method is also outperformed by a well-known scaled Newton method. Nevertheless, the primary value of our work is its conceptual value: it shows that for deriving gradient based methods for the matrix square root, \emph{the manifold geometric view of positive definite matrices can be much more advantageous than the Euclidean view}.