Thursday, July 31, 2014

GreBsmo: Greedy Bilateral Sketch, Completion & Smoothing - implementation -

In CAI: Cable And Igor's Adventures in Matrix Factorization, Cable and I used the GoDec algorithm of Tianyi Zhou to play with several Youtube videos. There are all here. Kyle Kastner did a similar undertaking using Python and IPython. it is all here.

Today, we have an even faster version of GoDecin GreBsmo as featured in Greedy Bilateral Sketch, Completion & Smoothing by Tianyi Zhou, Dacheng Tao
Recovering a large low-rank matrix from highly corrupted, incomplete or sparse outlier overwhelmed observations is the crux of various intriguing statistical problems. We explore the power of “greedy bilateral (GreB)” paradigm in reducing both time and sample complexities for solving these problems. GreB models a lowrank variable as a bilateral factorization, and updates the left and right factors in a mutually adaptive and greedy incremental manner. We detail how to model and solve low-rank approximation, matrix completion and robust PCA in GreB’s paradigm. On their MATLAB implementations, approximating a noisy 104 × 104 matrix of rank 500 with SVD accuracy takes 6s; MovieLens10M matrix of size 69878 × 10677 can be completed in 10s from 30% of 107 ratings with RMSE 0.86 on the rest 70%; the low-rank background and sparse moving outliers in a 120×160 video of 500 frames are accurately separated in 1s. This brings 30 to 100 times acceleration in solving these popular statistical problems.
The attendant code is here.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

No comments: