Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-Order Convergence
提出递归重要性素描算法（RISRO）求解秩约束最小二乘问题，将问题分解为更小的子问题，证明在温和条件下具有二次-线性及二次收敛速度，模拟显示性能优越。
Solving Rank Constrained Least Squares via Recursive Importance Sketching In statistics and machine learning, we sometimes run into the rank-constrained least squares problems, for which we need to find the best low-rank fit between sets of data, such as trying to figure out what factors are affecting the data, filling in missing information, or finding connections between different sets of data. This paper introduces a new method for solving this problem called the recursive importance sketching algorithm (RISRO), in which the central idea is to break the problem down into smaller, easier parts using a unique technique called “recursive importance sketching.” This new method is not only easy to use, but it is also very efficient and gives accurate results. We prove that RISRO converges in a local quadratic-linear and quadratic rate under some mild conditions. Simulation studies also demonstrate the superior performance of RISRO.