A divide-and-conquer algorithm for binary matrix completion
  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.
