A number of data sets are naturally described in matrix form. Examples range from microarrays to collaborative filtering data, to the set of pairwise distances of a cloud of points. In many of these examples, singular value decomposition (SVD) provides an efficient way to construct a low-rank approximation thus achievieng both dimensionality reduction, and effective denoising. SVD is also an important tool in the design of approximate linear algebra algorithms for massive data sets.
It is a recent discovery that –for important classes of matrices–SVD is sub-optimal, and can be significantly improved upon. There has been considerable progress on this topic over the last two years, partly spurred by interest in the Netflix challenge. I will overview this progress, and describe recent results on several specific problems, as well as outstanting challenges.