Large-Scale Convex Minimization with a Low-Rank Constraint

Abstract

We address the problem of minimizing a convex function over the space of large matrices with low rank. While this optimization problem is hard in general, we propose an efficient greedy algorithm and derive its formal approximation guarantees. Each iteration of the algorithm involves (approximately) finding the left and right singular vectors corresponding to the largest singular value of a certain matrix, which can be calculated in linear time. This leads to an algorithm which can scale to large matrices arising in several applications such as matrix completion for collaborative filtering and robust low rank matrix approximation.

ICML 2011

References in corpus (3)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion
• A Singular Value Thresholding Algorithm for Matrix Completion

Cited by in corpus (16)

• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• DMFSGD: A Decentralized Matrix Factorization Algorithm for Network Distance Prediction
• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
• Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization
• Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints
• Matrix Completion under Interval Uncertainty
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• Unmixing Incoherent Structures of Big Data by Randomized or Greedy Decomposition
• Improved Regret Bounds for Projection-free Bandit Convex Optimization
• Boosting Frank-Wolfe by Chasing Gradients
• Improved Algorithms for Matrix Recovery from Rank-One Projections
• Low-Rank Methods in Event Detection and Subsampled Point-to-Subspace Proximity Tests
• Solving Variational Inequalities with Monotone Operators on Domains Given by Linear Minimization Oracles
• Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints
• Scalable Nuclear-norm Minimization by Subspace Pursuit Proximal Riemannian Gradient