Divide-and-Conquer Matrix Factorization
This work introduces Divide-Factor-Combine (DFC), a parallel 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 subproblem solutions using techniques from randomized matrix approximation. Our experiments with collaborative filtering, video background modeling, 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Collaborative FilteringSimilar Papers 제목 키워드 기반
Distributed Matrix Completion and Robust Factorization
If learning methods are to scale to the massive sizes of modern datasets, it is essential for the field of machine learning to embrace parallel and distributed computing. Inspired by the recent development of matrix fact…
Collaborative FilteringDistributed ComputingMatrix CompletionAccurate and Scalable Matrix Mechanisms via Divide and Conquer
Matrix mechanisms are often used to provide unbiased differentially private query answers when publishing statistics or creating synthetic data. Recent work has developed matrix mechanisms, such as ResidualPlanner and We…
Statistically Guided Divide-and-Conquer for Sparse Factorization of Large Matrix
The sparse factorization of a large matrix is fundamental in modern statistical learning. In particular, the sparse singular value decomposition and its variants have been utilized in multivariate regression, factor anal…
Computational EfficiencyregressionTime Series AnalysisDivide-and-conquer based Large-Scale Spectral Clustering
Spectral clustering is one of the most popular clustering methods. However, how to balance the efficiency and effectiveness of the large-scale spectral clustering with limited computing resources has not been properly so…
ClusteringImage/Document ClusteringA Divide-and-Conquer Method for Scalable Low-Rank Latent Matrix Pursuit
Data fusion, which effectively fuses multiple prediction lists from different kinds of features to obtain an accurate model, is a crucial component in various computer vision applications. Robust late fusion (RLF) is a r…
Event DetectionObject Categorization