Interpretable Matrix Completion: A Discrete Optimization Approach

Dimitris Bertsimas () and Michael Lingzhi Li ()
Additional contact information
Dimitris Bertsimas: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Michael Lingzhi Li: Technology and Operations Management, Harvard Business School, Boston, Massachusetts 02163

INFORMS Journal on Computing, 2023, vol. 35, issue 5, 952-965

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 = 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.

Keywords: matrix completion; mixed-integer optimization; stochastic approximation; interpretability (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0022 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:5:p:952-965

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().