Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-Order Convergence

• 成果类型: Article
• 署名作者: Luo, Yuetian; Huang, Wen; Li, Xudong; Zhang, Anru
• 署名单位: University of Chicago; Xiamen University; Fudan University; Duke University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.2445
• 发表日期: 2024
• 关键词: matrix recovery; Riemannian Optimization; blind deconvolution; phase retrieval; critical-points; approximation; factorization; REPRESENTATION; completion; projection

摘要

In this paper, we propose a recursive importance sketching algorithm for rank constrained least squares optimization (RISRO). The key step of RISRO is recursive importance sketching, a new sketching framework based on deterministically designed recursive projections, and it significantly differs from the randomized sketching in the literature. 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, and 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.