# Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 42 references that are in the map.
- First posted on arXiv 20 May 2023.

## Builds on (most cited first, 15 of 15)

- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Interactive Supercomputing on 40,000 Cores for Machine Learning and Data Analysis](https://mlsanity.com/paper/1807.07814/) (2018)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [Generalized Low Rank Models](https://mlsanity.com/paper/1410.0342/) (2014)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints](https://mlsanity.com/paper/2009.10395/) (2020)
- [Defining and identifying Sleeping Beauties in science](https://mlsanity.com/paper/1505.06454/) (2015)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [On the Burer-Monteiro method for general semidefinite programs](https://mlsanity.com/paper/1904.07147/) (2019)
- [Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms](https://mlsanity.com/paper/1801.08227/) (2018)
- [On the Partial Convexification for Low-Rank Spectral Optimization: Rank Bounds and Algorithms](https://mlsanity.com/paper/2305.07638/) (2023)
- [Solving rank-constrained semidefinite programs in exact arithmetic](https://mlsanity.com/paper/1602.00431/) (2016)
- [Matrix Minor Reformulation and SOCP-based Spatial Branch-and-Cut Method for the AC Optimal Power Flow Problem](https://mlsanity.com/paper/1703.03050/) (2017)
- [On the strength of recursive McCormick relaxations for binary polynomial optimization](https://mlsanity.com/paper/2209.13034/) (2022)

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

- [Weighted Low-rank Approximation via Stochastic Gradient Descent on Manifolds](https://mlsanity.com/paper/2502.14174/) (2025)
- [Adaptive Stochastic Gradient Descents on Manifolds with an Application on Weighted Low-Rank Approximation](https://mlsanity.com/paper/2503.11833/) (2025)

## Abstract (arXiv)

Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible. Unfortunately, existing methods for matrix completion are heuristics that, while highly scalable and often identifying high-quality solutions, do not provide an instance-wise certificate of optimality. We reexamine matrix completion with an optimality-oriented eye. We reformulate low-rank matrix completion problems as convex problems over the non-convex set of projection matrices and implement a disjunctive branch-and-bound scheme that solves them to certifiable optimality. Further, we derive a novel and often near-exact class of convex relaxations by decomposing a low-rank matrix as a sum of rank-one matrices and incentivizing that two-by-two minors in each rank-one matrix have determinant zero. In numerical experiments, our new convex relaxations decrease the optimality gap by two orders of magnitude compared to existing attempts, and our disjunctive branch-and-bound scheme solves n × m rank-k matrix completion problems to certifiable optimality or near optimality in hours for max m, n ≤ 2500 and k ≤ 5. Moreover, this reduction in the training error translates into an average 2%--50% reduction in the test set error compared with alternating minimization-based methods.