Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
Not on the map. Why?
Abstract (arXiv)
In this paper, we propose it underlineRecursive it underlineImportance it underlineSketching algorithm for it underlineRank constrained least squares it underlineOptimization (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 citepmahoney2011randomized,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.
Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). First posted on arXiv 17 Nov 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 5; 2022: 3; 2023: 1; 2024: 1; 2025: 1.
11 papers.
- 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
- 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
- 2021A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samplescited by 13
- 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
- 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 3
- 2021On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimizationcited by 3
- 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 3
- 2024Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimizationcited by 3
- 2022Robust Regularized Low-Rank Matrix Models for Regression and Classificationcited by 2
- 2023Acceleration and Implicit Regularization in Gaussian Phase Retrievalcited by 1
- 2025Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Trainingcited by 1
- 2025Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training6 Nov 2025
- 2024Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization22 Oct 2024
- 2023Acceleration and Implicit Regularization in Gaussian Phase Retrieval21 Nov 2023
- 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective29 Sep 2022
- 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay17 Jun 2022
- 2022Robust Regularized Low-Rank Matrix Models for Regression and Classification14 May 2022
- 2021On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization23 Oct 2021
- 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization3 Aug 2021
- 2021GNMR: A provable one-line algorithm for low rank matrix recovery24 Jun 2021
- 2021A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples3 Jun 2021
- 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence24 Apr 2021