mlsanityData to 14 Oct 2026

Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach

arXiv 2109.12701 ↗First posted 26 Sep 2021stat.ML cs.LG math.OCcited by 14

Not on the map. Why?

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.

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

19 of 69 references.

References · 19

  1. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 160
  2. 2018Interactive Supercomputing on 40,000 Cores for Machine Learning and Data Analysiscited by 110
  3. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 71
  4. 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 70
  5. 2014Non-convex Robust PCAcited by 41
  6. 2016Fast Algorithms for Robust PCA via Gradient Descentcited by 39
  7. 2019Sparse Regression: Scalable algorithms and empirical performancecited by 27
  8. 2017Accelerated Alternating Projections for Robust Principal Component Analysiscited by 25
  9. 2019A unified approach to mixed-integer optimization problems with logical constraintscited by 18
  10. 2019A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Roboticscited by 16
  11. 2015Regularization vs. Relaxation: A conic optimization perspective of statistical variable selectioncited by 13
  12. 2017Robust PCA by Manifold Optimizationcited by 13
7 more
  1. 2020Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraintscited by 13
  2. 2018Low Rank and Structured Modeling of High-dimensional Vector Autoregressionscited by 12
  3. 2016Certifiably Optimal Low Rank Factor Analysiscited by 10
  4. 2021A new perspective on low-rank optimizationcited by 10
  5. 2020Free Energy Wells and Overlap Gap Property in Sparse PCAcited by 9
  6. 2019On the rate of convergence of alternating minimization for non-smooth non-strongly convex optimization in Banach spacescited by 3
  7. 2021Approximation Bounds for Sparse Programscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 5; 2025: 3; 2026: 5.

14 papers.

Sort:

  1. 2024SLTrain: a sparse plus low-rank approach for parameter and memory efficient pretrainingcited by 45
  2. 2024SLoPe: Double-Pruned Sparse Plus Lazy Low-Rank Adapter Pretraining of LLMscited by 20
  3. 2024OATS: Outlier-Aware Pruning Through Sparse and Low Rank Decompositioncited by 20
  4. 2023Compressed Sensing: A Discrete Optimization Approachcited by 3
  5. 2025HASSLE-free: A unified Framework for Sparse plus Low-Rank Matrix Decomposition for LLMscited by 3
  6. 2025Robust Low-Rank Sparse Framework for Video-Based Affective Computingcited by 1
  7. 2026Structural Correspondence and Universal Approximation in Diagonal plus Low-Rank Neural Networkscited by 1
  8. 2026GPTQ-intrinsic LoRA: A Near-optimal Algorithm for Low-precision Quantization with Low-rank Adaptationcited by 1
  9. 2024Robust support vector machines via conic optimizationcited by 0
  10. 2024Predictive Low Rank Matrix Learning under Partial Observations: Mixed-Projection ADMMcited by 0
  11. 2025Hierarchical Sparse Plus Low Rank Compression of LLMcited by 0
  12. 2026Compact Lifted Relaxations for Low-Rank Optimizationcited by 0
2 more
  1. 2026Sparse Network Inference under Imperfect Detection and its Application to Ecological Networkscited by 0
  2. 2026Joint Nuclear and ℓ1 Regularization for Logistic Matrix Regression with Applications to Brain Imagingcited by 0