Greedy Bilateral (GreB) Paradigm for Large-scale Matrix Completion, Robust PCA and Low-rank Approximation

Our paper “Greedy Bilateral Sketch, Completion and Smoothing” has been accepted by AISIATS 2013. Abstracts reads below, PDF is here, and code will be coming soon.


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 low-rank 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 10000×10000 matrix of rank 500 with SVD accuracy takes 6s; MovieLens10M matrix of size 69878×10677 can be completed in 10s from 30% of 10^7 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.

More good news:

For huge-scale problem or for obtaining faster speed, GreB can be seamlessly and straightforwardly extended to online, stochastic, parallel or divide-and-conquer (D&C) versions by using recent popular methods. In particular, major computations in GreB is  matrix multiplications that can be parallelized; GreB can be invoked as a subroutine for sub-matrix in D&C; greedily selected gradient direction can be replaced by a stochastic one.

Some results:


MovieLens recommendation experiments


Background modeling by robust PCA experiments on surveillance videos.


L-SVD: Lanczos method; R-SVD: randomized SVD; G-SVD: GreB based SVD

About tianyizhou

Research Assistant at University Washington, Seattle, Working on Machine Learning & Statistics in MODE lab leaded by Prof. Carlos Guestrin, and MELODI lab leaded by Prof. Jeff Bilmes.
This entry was posted in Tianyi's work and tagged , , , , , . Bookmark the permalink.

3 Responses to Greedy Bilateral (GreB) Paradigm for Large-scale Matrix Completion, Robust PCA and Low-rank Approximation

  1. Igor Carron says:


    I look forward to the paper and the implementation of it. Do you have a time frame in mind as to when you’d do that ?

    I am sure Cable and I could use to speed up some of our fun CAI blog entries:



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s