Greedy bilateral sketch, completion & smoothing
- Publication Type:
- Conference Proceeding
- Citation:
- Journal of Machine Learning Research, 2013, 31 pp. 650 - 658
- Issue Date:
- 2013-01-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Copyright 2013 by the authors. Recovering a large low-rank matrix from highly corrupted, incomplete or sparse outlier over- whelmed observations is the crux of various in- triguing 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 up- dates the left and right factors in a mutually adap- tive and greedy incremental manner. We de- tail how to model and solve low-rank approx- imation, matrix completion and robust PCA in GreB's paradigm. On their MATLAB implemen- tations, approximating a noisy 104 × 104 matrix of rank 500 with SVD accuracy takes 6s; Movie- Lens10M 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 back- ground 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.
Please use this identifier to cite or link to this item: