  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.
