|
GROUSE is a subspace estimation and tracking algorithm developed and
studied by Laura
Balzano, Ben Recht, and Rob Nowak.
The matlab file for the function GROUSE applied to matrix completion can be downloaded here, grouse.m, and you can see how to run it with rungrouse.m. Our paper describing GROUSE can be downloaded here. Laura's slides describing GROUSE can be downloaded here. |
|
|
GROUSE, or Grassmannian Rank-One Update Subspace Estimation, is an online subspace identification and tracking algorithm that works even when the measurement vectors are highly incomplete. This is useful in situations where data are being collected in large complex systems and data often get lost. It is also useful in recommender systems like Netflix and Match.com, where models are built in order to predict the interests of their users. Those models must be built based on an incomplete picture of what the user is interested in (no user has seen every movie on Netflix thus far!); not only that but the models must be updated incrementally as new users join or old users add ratings. Not only does GROUSE work with missing ratings, but because it is an online and incremental algorithm, it can easily and quickly do subspace model updates. GROUSE was inspired by our our paper at ISIT 2010 which showed that the prediction residual on a vector's observed entries only is an excellent indicator of whether or not a vector fits the predictive model. Following the lead of the Matrix Completion theory in OPT-Space, and using the excellent paper referenced there, The Geometry of Algorithms with Orthogonality Constraints, we developed a stochastic gradient algorithm that operates on the Grassmannian, the space of all d-dimensional subspaces. The GROUSE algorithm requires very few simple steps, and it is super easy to implement. Its per-iteration complexity is O(nd), where n is the ambient dimension and d the intrinsic dimension, and from our simulations we see that it is very very fast. |