论文标题
递归的重要性素描针对秩限制的最小二乘：算法和高阶收敛性
Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
论文作者
论文摘要
在本文中，我们提出{\ it \下划线{r} ecursive} {\ it \下划线{i} mportance} {\ it \ it \ usewissline {s} ketching} algorithm for {\ useverline {r} ank} bline {r} ank} bline { （risro）。 Risro的关键步骤是递归重要性草图，这是一个基于确定性设计的递归投影的新素描框架，它与文献中的随机素描\ Citep {Mahoney2011 randomized，Woodruff2014sketching}明显不同。在这个新的素描框架下，可以重新解释文献中的几种现有算法，而Risro比它们具有明显的优势。 Risro易于实现和计算高效，其中每次迭代中的核心过程是解决降低尺寸最小二乘问题的问题。我们在某些轻度条件下建立了Risro的局部二次线性和二次收敛速率。我们还发现了Risro与固定级矩阵上的Riemannian高斯 - 纽顿算法的密切联系。在机器学习和统计数据中的两个应用中，证明了RISRO的有效性：低率矩阵痕量回归和相位检索。仿真研究表明了Risro的优异数值性能。
In this paper, we propose {\it \underline{R}ecursive} {\it \underline{I}mportance} {\it \underline{S}ketching} algorithm for {\it \underline{R}ank} constrained least squares {\it \underline{O}ptimization} (RISRO). The key step of RISRO is recursive importance sketching, a new sketching framework based on deterministically designed recursive projections, which significantly differs from the randomized sketching in the literature \citep{mahoney2011randomized,woodruff2014sketching}. Several existing algorithms in the literature can be reinterpreted under this new sketching framework and RISRO offers clear advantages over them. RISRO is easy to implement and computationally efficient, where the core procedure in each iteration is to solve a dimension-reduced least squares problem. We establish the local quadratic-linear and quadratic rate of convergence for RISRO under some mild conditions. We also discover a deep connection of RISRO to the Riemannian Gauss-Newton algorithm on fixed rank matrices. The effectiveness of RISRO is demonstrated in two applications in machine learning and statistics: low-rank matrix trace regression and phase retrieval. Simulation studies demonstrate the superior numerical performance of RISRO.
