Grassmannian Rank-One Update Subspace Estimation (GROUSE), is an online algorithm for subspace identification and tracking when data vectors are incomplete. See our page on GROUSE for details about the algorithm. GROUSE can be used for matrix completion; download grouse.m for the Matlab function and rungrouse.m to see how to run it.

Edit September 24, 2018:

For a long time I’ve had an updated version of the code with our various new step-size schemes, but finally I am putting it online! Download grouse2.m for the new Matlab function, and rungrouse2.m to see how to run it.

Relevant new publications are Dejiao Zhang’s AIStats paper with the greedy step-size scheme for full data and our ongoing submission on arxiv that has the same step size for missing/compressed data and even further analysis. The AIStats submission includes a noisy scheme that is NOT included in the code here. It currently requires an accurate estimate of the noise bounds, but we hope to develop a technique for estimating the noise variance online, and we will update this post again when we do!