Interpretable Matrix Completion: A Discrete Optimization Approach
This addresses the need for interpretable matrix completion in applications requiring insights from side information, representing an incremental improvement with a novel method for a known bottleneck.
The paper tackles the problem of interpretable matrix completion by introducing a method that provides meaningful insights using side information, reformulating it as a binary convex optimization problem. It reports that OptComplete scales efficiently to matrices of size up to 10^6 x 10^6 and shows favorable accuracy compared to state-of-the-art methods.
We consider the problem of matrix completion on an $n \times 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 a binary convex optimization problem. We design 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 report experiments on both synthetic and real-world datasets 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.