Back to Search
Start Over
Interpretable Matrix Completion: A Discrete Optimization Approach.
- Source :
-
INFORMS Journal on Computing . Sep/Oct2023, Vol. 35 Issue 5, p952-965. 14p. - Publication Year :
- 2023
-
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. 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *LOW-rank matrices
*MATRICES (Mathematics)
*STOCHASTIC approximation
Subjects
Details
- Language :
- English
- ISSN :
- 10919856
- Volume :
- 35
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- INFORMS Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 172829187
- Full Text :
- https://doi.org/10.1287/ijoc.2022.0022