1303.0167 (Stephen Becker et al.)

Randomized Singular Value Projection    [PDF]

Stephen Becker, Volkan Cevher, Anastasios Kyrillidis

Affine rank minimization algorithms typically rely on calculating the gradient of a data error followed by singular value decompositions at every iteration. Because these two steps are expensive, heuristics are often used. In this paper, we propose one recovery scheme that merges the two steps and show that it actually admits provable recovery guarantees while operating on space proportional to the degrees of freedom in the problem.

View original: http://arxiv.org/abs/1303.0167