Stochastic Systems Group  

Nathan Srebro
Doctoral Student, EECS, MIT
We study the common problem of approximating a target matrix with a matrix of low rank. Lowrank approximation with respect to the Frobenius norm (i.e. when one seeks to minimizing the sum squared difference from the target) is widely studied and used, and can be easily solved using a singular value decomposition. For many applications, however, a different loss function is appropriate.
We first consider generalizing the loss function to a weighted Frobenius norm, with a distinct weight given for each entry in the target matrix. While this is conceptually straightforward and arises naturally in several contexts, the standard approach for the unweighted case (using SVD) does not carry over to the weighted case. We show how the fundamental structure of the problem and its solution breaks when weights are introduced, present efficient optimization methods for finding a weighted low rank approximation, and demonstrate the utility of introducing weights in reconstructing an underlying low rank representation.
We further generalize the setting and motivate other loss functions. These include nonGaussian noise models, unknown parametric noise models, and logistic models appropriate for classification (rather than realvalued) matrices and for collaborative filtering. We show how weighted lowrank approximation can be applied as a subroutine for solving these more general lowrank problems.
Joint work with Tommi Jaakkola
Problems with this site should be emailed to jonesb@mit.edu