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

2020/11/17 by Yuetian Luo, Luo, Yuetian, Wen Huang +5 · 2 citations
Computer Science · Engineering · Physics and Astronomy · #Computation (stat.CO) #Electromagnetic Scattering and Analysis #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2011.08360

openalex publication_date 2020/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Phase Retrieval with Application to Optical Imaging: A contemporary overview
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Fast approximation of matrix coherence and statistical leverage
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified\n Geometric Analysis
• Nuclear norm penalization and optimal rates for noisy low rank matrix\n completion
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Numerical optimization
• A Schatten-q Low-rank Matrix Perturbation Analysis via Perturbation Projection Error Bound

Cited by

• Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence

Related

• Learning the Positions in CountSketch
• Exploiting the Structure via Sketched Gradient Algorithms
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization
• Tensor-structured sketching for constrained least squares
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares