In this section
@article{Bertsimas:2026,
author = {Bertsimas, D and Cory-Wright, R and Lo, S and Pauphilet, J},
journal = {INFORMS Journal on Computing},
title = {Disjunctive branch-and-bound for certifiably optimal low-rank matrix completion},
url = {http://10.0.189.166/arXiv.2305.12292},
year = {2026}
}
TY - JOUR
AB - 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.
AU - Bertsimas,D
AU - Cory-Wright,R
AU - Lo,S
AU - Pauphilet,J
PY - 2026///
SN - 1091-9856
TI - Disjunctive branch-and-bound for certifiably optimal low-rank matrix completion
T2 - INFORMS Journal on Computing
UR - http://10.0.189.166/arXiv.2305.12292
ER -