# Interpretable Matrix Completion: A Discrete Optimization Approach

arXiv: https://arxiv.org/abs/1812.06647 · HTML: https://mlsanity.com/paper/1812.06647/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2018.

## Built on by (most cited first, 5 of 5)

- [Principal Component Hierarchy for Sparse Quadratic Programs](https://mlsanity.com/paper/2105.12022/) (2021)
- [Stochastic Cutting Planes for Data-Driven Optimization](https://mlsanity.com/paper/2103.02506/) (2021)
- [Tensor Completion Leveraging Graph Information: A Dynamic Regularization Approach with Statistical Guarantees](https://mlsanity.com/paper/2310.02543/) (2023)
- [Towards Reliable Recommender Systems for Rating Data](https://mlsanity.com/paper/2412.20802/) (2024)
- [Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach](https://mlsanity.com/paper/2502.08536/) (2025)

## Abstract (arXiv)

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 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=106 and m=106. 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.