Built on

Studies in Linear and Nonlinear Programming
1958
Earlier work this paper cites.
A Unified Algebric Approach to Control Design
1997
Earlier work this paper cites.
Alternating projection algorithms for linear matrix inequalities problems with rank constraints
2000
Earlier work this paper cites.
Fast online svd revisions for lightweight recommender systems
2003
Earlier work this paper cites.
Log-det heuristic for matrix rank minimization with applications to hankel and euclidean distance matrices
——— · 2003
Earlier work this paper cites.
Decoding by linear programming
2005
Earlier work this paper cites.
Recovery of exact sparse representations in the presence of bounded noise
2005
Earlier work this paper cites.
Stable recovery of sparse overcomplete representations in the presence of noise
2006
Earlier work this paper cites.
Sparsity and incoherence in compressive sampling
2007
Earlier work this paper cites.
Scalable collaborative filtering with jointly derived neighborhood interpolation weights
2007
Earlier work this paper cites.

Similar

Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization , 2007
Original
2007
Cited alongside, same era.
A singular value thresholding algorithm for matrix completion , 2008
Original
2008
Cited alongside, same era.
Exact matrix completion via convex optimization , 2008
Original
2008
Cited alongside, same era.
Factorization meets the neighborhood: a multifaceted collaborative filtering model
2008
Cited alongside, same era.
Greedy signal recovery review , 2008
Original
2008
Cited alongside, same era.

Then

Convergence of fixed point continuation algorithms for matrix rank minimization , 2009
Original
2009
Closest in time.
An accelerated gradient method for trace norm minimization
2009
Closest in time.
Matrix completion from a few entries , 2009
Original
2009
Closest in time.
Admira: Atomic decomposition for minimum rank approximation , 2009
Original
2009
Closest in time.
Guaranteed minimum rank approximation from linear observations by nuclear norm minimization with an ellipsoidal constraint , 2009
Original
——— · 2009
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2009

Guaranteed Rank Minimization via Singular Value Projection

Meka, Raghu, Jain, Prateek, Dhillon, Inderjit S.

Understand

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.

Built on

Studies in Linear and Nonlinear Programming
1958
Earlier work this paper cites.
A Unified Algebric Approach to Control Design
1997
Earlier work this paper cites.
Alternating projection algorithms for linear matrix inequalities problems with rank constraints
2000
Earlier work this paper cites.
Fast online svd revisions for lightweight recommender systems
2003
Earlier work this paper cites.
Log-det heuristic for matrix rank minimization with applications to hankel and euclidean distance matrices
——— · 2003
Earlier work this paper cites.
Decoding by linear programming
2005
Earlier work this paper cites.
Recovery of exact sparse representations in the presence of bounded noise
2005
Earlier work this paper cites.
Stable recovery of sparse overcomplete representations in the presence of noise
2006
Earlier work this paper cites.
Sparsity and incoherence in compressive sampling
2007
Earlier work this paper cites.
Scalable collaborative filtering with jointly derived neighborhood interpolation weights
2007
Earlier work this paper cites.