Interpretable Matrix Completion: A Discrete Optimization Approach

We consider the problem of matrix completion on an n × m matrix. We introduce the problem of interpretable matrix completion that aims to provide meaningful insights for the low-rank matrix using side information. We show that the problem can be reformulated as an optimization problem with a convex objective and binary variables. We design an algorithm called OptComplete, based on a novel concept of stochastic cutting planes to enable efficient scaling of the algorithm up to matrices of sizes n = 10 6 and m = 10 6 . We prove that OptComplete converges to an optimal solution of the interpretable matrix completion problem with exponentially vanishing failure probability. We report experiments on both synthetic and real-world data sets that show that OptComplete has favorable scaling behavior and accuracy when compared with state-of-the-art methods for other types of matrix completion while providing insight on the factors that affect the matrix. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Supplemental Material: The online appendices are available at https://doi.org/10.1287/ijoc.2022.0022 .