Fast Low-Rank Matrix Estimation without the Condition Number

Abstract

In this paper, we study the general problem of optimizing a convex function $F(L)$ over the set of $p\times p$ matrices, subject to rank constraints on $L$. However, existing first-order methods for solving such problems either are too slow to converge, or require multiple invocations of singular value decompositions. On the other hand, factorization-based non-convex algorithms, while being much faster, require stringent assumptions on the \emph{condition number} of the optimum. In this paper, we provide a novel algorithmic framework that achieves the best of both worlds: asymptotically as fast as factorization methods, while requiring no dependency on the condition number. We instantiate our general framework for three important matrix estimation problems that impact several practical applications; (i) a \emph{nonlinear} variant of affine rank minimization, (ii) logistic PCA, and (iii) precision matrix estimation in probabilistic graphical model learning. We then derive explicit bounds on the sample complexity as well as the running time of our approach, and show that it achieves the best possible bounds for both cases. We also provide an extensive range of experimental results, and demonstrate that our algorithm provides a very attractive tradeoff between estimation accuracy and running time.

References in corpus (19)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• An overview of low-rank matrix recovery from incomplete observations
• Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation
• Global Optimality of Local Search for Low Rank Matrix Recovery
• 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
• A Field Guide to Forward-Backward Splitting with a FASTA Implementation
• Fast Algorithms for Robust PCA via Gradient Descent
• Prediction and Clustering in Signed Networks: A Local to Global Perspective
• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
• A Tight Bound of Hard Thresholding
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• Sparse Nonlinear Regression: Parameter Estimation and Asymptotic Inference
• Estimating sparse precision matrices
• Randomized Low-Memory Singular Value Projection
• Large-Scale Low-Rank Matrix Learning with Nonconvex Regularizers
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery

Cited by in corpus (3)

• On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Low-rank Matrix Optimization Using Polynomial-filtered Subspace Extraction