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

Abstract

In this paper, we propose {\it \underline{R}ecursive} {\it \underline{I}mportance} {\it \underline{S}ketching} algorithm for {\it \underline{R}ank} constrained least squares {\it \underline{O}ptimization} (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 \citep{mahoney2011randomized,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.

arXiv commentAccepted by Operations Research

References in corpus (19)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Fast approximation of matrix coherence and statistical leverage
• Global Optimality in Low-rank Matrix Optimization
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Matrix Completion from a Few Entries
• The Non-convex Geometry of Low-rank Matrix Optimization
• Phaseless Rcovery using Gauss-Newton Method
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Asymptotics for Sketching in Least Squares Regression
• Blind Deconvolution using Convex Programming
• Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery
• Convergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number
• A Schatten-$q$ Low-rank Matrix Perturbation Analysis via Perturbation Projection Error Bound

Cited by in corpus (4)

• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization