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

arXiv: https://arxiv.org/abs/2011.08360 · HTML: https://mlsanity.com/paper/2011.08360/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2020.

## Built on by (most cited first, 11 of 11)

- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)
- [On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization](https://mlsanity.com/paper/2110.12121/) (2021)
- [Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization](https://mlsanity.com/paper/2410.16982/) (2024)
- [Robust Regularized Low-Rank Matrix Models for Regression and Classification](https://mlsanity.com/paper/2205.07106/) (2022)
- [Acceleration and Implicit Regularization in Gaussian Phase Retrieval](https://mlsanity.com/paper/2311.12888/) (2023)
- [Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training](https://mlsanity.com/paper/2511.04485/) (2025)

## 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.