Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization
  Approach
  We study the Sparse Plus Low Rank decomposition problem (SLR), which is the
problem of decomposing a corrupted data matrix $\mathbf{D}$ into a sparse
matrix $\mathbf{Y}$ containing the perturbations plus a low rank matrix
$\mathbf{X}$. SLR is a fundamental problem in Operations Research and Machine
Learning arising in many applications such as data compression, latent semantic
indexing, collaborative filtering and medical imaging. We introduce a novel
formulation for SLR that directly models the underlying discreteness of the
problem. For this formulation, we develop an alternating minimization heuristic
to compute high quality solutions and a novel semidefinite relaxation that
provides meaningful bounds for the solutions returned by our heuristic. We
further develop a custom branch and bound routine that leverages our heuristic
and convex relaxation that solves small instances of SLR to certifiable
near-optimality. Our heuristic can scale to $n=10000$ in hours, our relaxation
can scale to $n=200$ in hours, and our branch and bound algorithm can scale to
$n=25$ in minutes. Our numerical results demonstrate that our approach
outperforms existing state-of-the-art approaches in terms of the MSE of the low
rank matrix and that of the sparse matrix.
