Guaranteed Rank Minimization via Singular Value Projection

Abstract

Minimizing the rank of a matrix subject to affine constraints is a fundamental problem with many important applications in machine learning and statistics. In this paper we propose a simple and fast algorithm SVP (Singular Value Projection) for rank minimization with affine constraints (ARMP) and show that SVP recovers the minimum rank solution for affine constraints that satisfy the "restricted isometry property" and show robustness of our method to noise. Our results improve upon a recent breakthrough by Recht, Fazel and Parillo (RFP07) and Lee and Bresler (LB09) in three significant ways: 1) our method (SVP) is significantly simpler to analyze and easier to implement, 2) we give recovery guarantees under strictly weaker isometry assumptions 3) we give geometric convergence guarantees for SVP even in presense of noise and, as demonstrated empirically, SVP is significantly faster on real-world and synthetic problems. In addition, we address the practically important problem of low-rank matrix completion (MCP), which can be seen as a special case of ARMP. We empirically demonstrate that our algorithm recovers low-rank incoherent matrices from an almost optimal number of uniformly sampled entries. We make partial progress towards proving exact recovery and provide some intuition for the strong performance of SVP applied to matrix completion by showing a more restricted isometry property. Our algorithm outperforms existing methods, such as those of \cite{RFP07,CR08,CT09,CCS08,KOM09,LB09}, for ARMP and the matrix-completion problem by an order of magnitude and is also significantly more robust to noise.

An earlier version of this paper was submitted to NIPS-2009 on June 5, 2009

References in corpus (10)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Sparsity and Incoherence in Compressive Sampling
• Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices
• Matrix Completion from a Few Entries
• Matrix Completion With Noise
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• Greedy Signal Recovery Review
• A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions

Cited by in corpus (24)

• A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
• Joint CSIT Acquisition Based on Low-Rank Matrix Completion for FDD Massive MIMO Systems
• Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion
• A Riemannian geometry for low-rank matrix completion
• Rank Minimization over Finite Fields: Fundamental Limits and Coding-Theoretic Interpretations
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Optimal Sparse Output Feedback Control Design: a Rank Constrained Optimization Approach
• Provable Tensor-Train Format Tensor Completion by Riemannian Optimization
• Modelling Competitive Sports: Bradley-Terry-Élő Models for Supervised and On-Line Learning of Paired Competition Outcomes
• Low-rank optimization with trace norm penalty
• Gradient descent with nonconvex constraints: local concavity determines convergence
• Low-rank Matrix Completion with Noisy Observations: a Quantitative Comparison
• Learning Non-Parametric Basis Independent Models from Point Queries via Low-Rank Methods
• Sufficient Conditions for Low-rank Matrix Recovery, Translated from Sparse Signal Recovery
• Algebraic-Combinatorial Methods for Low-Rank Matrix Completion with Application to Athletic Performance Prediction
• A Geometric Approach to Low-Rank Matrix Completion
• Sample Efficient Linear Meta-Learning by Alternating Minimization
• Global hard thresholding algorithms for joint sparse image representation and denoising
• Decomposition Approach for Low-rank Matrix Completion
• Non-convexly constrained linear inverse problems