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

Yuetian Luo (), Wen Huang (), Xudong Li () and Anru Zhang ()
Additional contact information
Yuetian Luo: Data Science Institute, University of Chicago, Chicago, Illinois 60637
Wen Huang: School of Mathematical Sciences, Xiamen University, Xiamen 361005, China
Xudong Li: School of Data Science, Fudan University, Shanghai 200433, China
Anru Zhang: Department of Biostatistics & Bioinformatics, Duke University, Durham, North Carolina 27710

Operations Research, 2024, vol. 72, issue 1, 237-256

Abstract: 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.

Keywords: Machine Learning and Data Science; rank-constrained least squares; sketching; quadratic convergence; Riemannian manifold optimization; low-rank matrix recovery; nonconvex optimization (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.2445 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:1:p:237-256

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().