Title
Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions
Abstract
Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible and has numerous applications, including product recommendation. Unfortunately, existing methods for solving low-rank matrix completion are heuristics that typically identify high-quality solutions, but without any optimality guarantees. We reexamine matrix completion with an optimality-oriented eye, by reformulating low-rank problems as convex problems over the non-convex set of projection matrices and implementing a disjunctive branch-and-bound scheme that solves them to certifiable optimality. Further, we derive a novel and often tight class of convex relaxations by decomposing a low-rank matrix as a sum of rank-one matrices and incentivizing, via a Shor relaxation, that each two-by-two minor in each rank-one matrix has determinant zero. Across a suite of numerical experiments, our new convex relaxations decrease the optimality gap by two orders of magnitude compared to existing attempts. Moreover, we showcase the performance of our disjunctive branch-and-bound scheme and demonstrate that it solves matrix completion problems over 150×150 matrices to certifiable optimality in hours, constituting an order of magnitude improvement on the state-of-the-art.
This is joint work with Jean Pauphilet (LBS), Sean Lo (MIT), and Dimitris Bertsimas (MIT) and a preprint is available here: https://arxiv.org/abs/2305.12292
Bio
Ryan Cory-Wright is an Assistant Professor in the Analytics and Operations Group at Imperial College Business School, affiliated with the Imperial-X initiative on interdisciplinary AI/ML. His research interests lie at the intersection of optimization, machine learning, and statistics, and their applications in business analytics and renewable energy. He is particularly interested in building bridges between different areas of Operations Research, and using these bridges to facilitate solving previously intractable problems. He is also interested in using Operations Research to facilitate a rapid and economically viable transition to a low-carbon economy.
Prior to joining Imperial in July 2023, Ryan was a Herman Goldstine postdoctoral fellow at IBM Research, and holds a PhD in Operations Research from MIT and a BE (Hons) in Engineering Science from The University of Auckland. He has research articles published in Operations Research, Mathematical Programming, SIAM Journal on Optimization, and the Journal of Machine Learning Research. He is a recipient of the INFORMS Nicholson Prize, the Pierskalla Award, and the INFORMS Computing Society Student Paper Award.