We introduce Divide-Factor-Combine (DFC), a scalable divide-and-conquer
framework for noisy matrix factorization. DFC divides a large-scale matrix
factorization task into smaller subproblems, solves each subproblem in
parallel
using an arbitrary base matrix factorization algorithm, and combines the
sub-problem solutions using techniques from randomized matrix approximation.
Our experiments with collaborative filtering, video background modeling,
subspace segmentation, graph-based semi-supervised learning and simulated data
demonstrate the near-linear to super-linear speed-ups attainable with this
approach. Moreover, our analysis shows that DFC enjoys high-probability
recovery
guarantees comparable to those of its base algorithm.