Publications
Publications
- September–October 2023
- INFORMS Journal on Computing
Interpretable Matrix Completion: A Discrete Optimization Approach
By: Dimitris Bertsimas and Michael Lingzhi Li
Abstract
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 = 106 and m = 106. 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.
Keywords
Citation
Bertsimas, Dimitris, and Michael Lingzhi Li. "Interpretable Matrix Completion: A Discrete Optimization Approach." INFORMS Journal on Computing 35, no. 5 (September–October 2023): 952–965.