Sparse plus low rank matrix decomposition: a discrete optimization approach
File(s)
Published version
Author(s)
Bertsimas, Dimitris
Cory-Wright, Ryan
Johnson, Nicholas
Type
Journal Article
Abstract
We study the Sparse Plus Low-Rank decomposition problem (SLR), which is the problem of decomposing a corrupted data matrix into a sparse matrix of perturbations plus a low-rank matrix containing the ground truth. SLR is a fundamental problem in Operations Research and Machine Learning which arises in various applications, including data compression, latent semantic indexing, collaborative filtering, and medical imaging. We introduce a novel
formulation for SLR that directly models its underlying discreteness. For this formulation, we develop an alternating minimization heuristic that computes high-quality solutions and a novel semidefinite relaxation that provides meaningful bounds for the solutions returned by our heuristic. We also develop a custom branch-and-bound algorithm that leverages our heuristic and convex relaxations to solve small instances of SLR to certifiable (near) optimality. Given an input n-by-n matrix, our heuristic scales to solve instances where n = 10000 in minutes, our relaxation scales to instances where n = 200 in hours, and our branch-and-bound algorithm scales to instances where n = 25 in minutes. Our numerical results demonstrate that our approach outperforms existing state-of-the-art approaches in terms of rank, sparsity, and mean-square error while maintaining a comparable runtime.
formulation for SLR that directly models its underlying discreteness. For this formulation, we develop an alternating minimization heuristic that computes high-quality solutions and a novel semidefinite relaxation that provides meaningful bounds for the solutions returned by our heuristic. We also develop a custom branch-and-bound algorithm that leverages our heuristic and convex relaxations to solve small instances of SLR to certifiable (near) optimality. Given an input n-by-n matrix, our heuristic scales to solve instances where n = 10000 in minutes, our relaxation scales to instances where n = 200 in hours, and our branch-and-bound algorithm scales to instances where n = 25 in minutes. Our numerical results demonstrate that our approach outperforms existing state-of-the-art approaches in terms of rank, sparsity, and mean-square error while maintaining a comparable runtime.
Date Issued
2023
Date Acceptance
2023-10-01
Citation
Journal of Machine Learning Research, 2023, 24, pp.1-51
ISSN
1532-4435
Publisher
Microtome Publishing
Start Page
1
End Page
51
Journal / Book Title
Journal of Machine Learning Research
Volume
24
Copyright Statement
©2023 Dimitris Bertsimas, Ryan Cory-Wright, and Nicholas A. G. Johnson. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided
at http://jmlr.org/papers/v24/21-1130.html.
at http://jmlr.org/papers/v24/21-1130.html.
License URL
Identifier
https://jmlr.org/papers/v24/21-1130.html
Publication Status
Published
Article Number
267
Date Publish Online
2023-10