# Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 69 references that are in the map.
- First posted on arXiv 26 Sep 2021.

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

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Interactive Supercomputing on 40,000 Cores for Machine Learning and Data Analysis](https://mlsanity.com/paper/1807.07814/) (2018)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Non-convex Robust PCA](https://mlsanity.com/paper/1410.7660/) (2014)
- [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016)
- [Sparse Regression: Scalable algorithms and empirical performance](https://mlsanity.com/paper/1902.06547/) (2019)
- [Accelerated Alternating Projections for Robust Principal Component Analysis](https://mlsanity.com/paper/1711.05519/) (2017)
- [A unified approach to mixed-integer optimization problems with logical constraints](https://mlsanity.com/paper/1907.02109/) (2019)
- [A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics](https://mlsanity.com/paper/1908.05209/) (2019)
- [Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection](https://mlsanity.com/paper/1510.06083/) (2015)
- [Robust PCA by Manifold Optimization](https://mlsanity.com/paper/1708.00257/) (2017)
- [Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints](https://mlsanity.com/paper/2009.10395/) (2020)
- [Low Rank and Structured Modeling of High-dimensional Vector Autoregressions](https://mlsanity.com/paper/1812.03568/) (2018)
- [Certifiably Optimal Low Rank Factor Analysis](https://mlsanity.com/paper/1604.06837/) (2016)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [Free Energy Wells and Overlap Gap Property in Sparse PCA](https://mlsanity.com/paper/2006.10689/) (2020)
- [On the rate of convergence of alternating minimization for non-smooth non-strongly convex optimization in Banach spaces](https://mlsanity.com/paper/1911.00404/) (2019)
- [Approximation Bounds for Sparse Programs](https://mlsanity.com/paper/2102.06742/) (2021)

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

- [SLTrain: a sparse plus low-rank approach for parameter and memory efficient pretraining](https://mlsanity.com/paper/2406.02214/) (2024)
- [SLoPe: Double-Pruned Sparse Plus Lazy Low-Rank Adapter Pretraining of LLMs](https://mlsanity.com/paper/2405.16325/) (2024)
- [OATS: Outlier-Aware Pruning Through Sparse and Low Rank Decomposition](https://mlsanity.com/paper/2409.13652/) (2024)
- [Compressed Sensing: A Discrete Optimization Approach](https://mlsanity.com/paper/2306.04647/) (2023)
- [HASSLE-free: A unified Framework for Sparse plus Low-Rank Matrix Decomposition for LLMs](https://mlsanity.com/paper/2502.00899/) (2025)
- [Robust Low-Rank Sparse Framework for Video-Based Affective Computing](https://mlsanity.com/paper/2511.11406/) (2025)
- [Structural Correspondence and Universal Approximation in Diagonal plus Low-Rank Neural Networks](https://mlsanity.com/paper/2605.05659/) (2026)
- [GPTQ-intrinsic LoRA: A Near-optimal Algorithm for Low-precision Quantization with Low-rank Adaptation](https://mlsanity.com/paper/2606.01412/) (2026)
- [Robust support vector machines via conic optimization](https://mlsanity.com/paper/2402.01797/) (2024)
- [Predictive Low Rank Matrix Learning under Partial Observations: Mixed-Projection ADMM](https://mlsanity.com/paper/2407.13731/) (2024)
- [Hierarchical Sparse Plus Low Rank Compression of LLM](https://mlsanity.com/paper/2601.07839/) (2025)
- [Compact Lifted Relaxations for Low-Rank Optimization](https://mlsanity.com/paper/2603.20228/) (2026)
- [Sparse Network Inference under Imperfect Detection and its Application to Ecological Networks](https://mlsanity.com/paper/2604.18820/) (2026)
- [Joint Nuclear and ℓ1 Regularization for Logistic Matrix Regression with Applications to Brain Imaging](https://mlsanity.com/paper/2606.14436/) (2026)

## Abstract (arXiv)

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.