A divide-and-conquer algorithm for binary matrix completion

2019-07-09 · Melanie Beckerleg, Andrew Thompson

We propose an algorithm for low rank matrix completion for matrices with binary entries which obtains explicit binary factors. Our algorithm, which we call TBMC (\emph{Tiling for Binary Matrix Completion}), gives interpretable output in the form of binary factors which represent a decomposition of the matrix into tiles. Our approach is inspired by a popular algorithm from the data mining community called PROXIMUS: it adopts the same recursive partitioning approach while extending to missing data. The algorithm relies upon rank-one approximations of incomplete binary matrices, and we propose a linear programming (LP) approach for solving this subproblem. We also prove a $2$-approximation result for the LP approach which holds for any level of subsampling and for any subsampling pattern. Our numerical experiments show that TBMC outperforms existing methods on recommender systems arising in the context of real datasets.

📄 PDF Abstract BibTeX arXiv:1907.04251

Code (0)

등록된 구현이 없습니다.

Tasks

Low-Rank Matrix CompletionMatrix CompletionRecommendation Systems

Distributed Matrix Completion and Robust Factorization

2011-07-05 · Lester Mackey, Ameet Talwalkar, Michael. I. Jordan

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 Filtering Distributed Computing Matrix Completion

Divide-and-Conquer Matrix Factorization

2011-12-01 · NeurIPS 2011 12 · Lester W. Mackey, Michael. I. Jordan, Ameet Talwalkar

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 subprob…

Collaborative Filtering

A Divide-and-Conquer Method for Scalable Low-Rank Latent Matrix Pursuit

2013-06-01 · CVPR 2013 6 · Yan Pan, Hanjiang Lai, Cong Liu, Shuicheng Yan

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 Detection Object Categorization

Divide-and-conquer based Large-Scale Spectral Clustering

2021-04-30 · Hongmin Li, Xiucai Ye, Akira Imakura, Tetsuya Sakurai

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…

Clustering Image/Document Clustering

A Divide-and-Conquer Method for Sparse Inverse Covariance Estimation

2012-12-01 · NeurIPS 2012 12 · Cho-Jui Hsieh, Arindam Banerjee, Inderjit S. Dhillon, Pradeep K. Ravikumar

In this paper, we consider the $\ell_1$ regularized sparse inverse covariance matrix estimation problem with a very large number of variables. Even in the face of this high dimensionality, and with limited number of samp…

Clustering