D-SLR: The Disjoint Row-Sparse plus Low-Rank Decomposition
Abstract
Compressing a matrix for reconstruction still defaults to the truncated SVD, approximating the data with a single low-rank structure. It is common to reduce the residual further by adding an overlapping row-sparse component, but methods that solve this joint problem often require iterative solvers and tuning of regularization parameters. We propose the Disjoint Row-Sparse plus Low-Rank (D-SLR) decomposition, a closed-form drop-in for the truncated SVD that improves or exactly matches it. D-SLR restricts rows to either being stored verbatim or approximated by the low-rank fit, never both. Under squared error this restriction costs nothing: the joint optimum is attainable disjointly with fewer parameters at every non-trivial rank and stored row count (shape). With zero stored rows D-SLR reduces to the truncated SVD, so it never does worse at equal cost. The algorithm scores the entire error-versus-parameters tradeoff, and the solution is chosen afterwards by a supplied error target or parameter count, or by a selection rule. The grid and solution together cost three SVDs, with no tuning or regularization. We derive an assumption-free, a-posteriori lower bound on the error at every shape, giving each solution a computable certificate on the potential gain of any other choice of rank and stored rows. Experiments on synthetic and real data (LLM embedding tables, network traffic, hyperspectral images) confirm the gains and quantify the certificate.
Related
- Sparse plus low-rank matrix embedding with applications in cancer radiotherapy optimization
- Low-Rank and Structured Sparse Tensor Decomposition for Anomaly Detection in Multivariate Functional Data
- Min-plus Bruhat decomposition
- A decomposition theorem for elliptic structures of minimal rank on compact Lie groups and applications
- Decomposition of Sparse Integer Programs via Nonlinear Edge Encodings and Column-and-Row Generation
BibTeX
@misc{szolnoky2026dslr,
title = {{D-SLR: The Disjoint Row-Sparse plus Low-Rank Decomposition}},
author = {Vincent Szolnoky},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10636},
eprint = {2610.10636},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10636},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - D-SLR: The Disjoint Row-Sparse plus Low-Rank Decomposition
AU - Vincent Szolnoky
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10636
UR - https://arxiv.org/abs/2610.10636
AB - Compressing a matrix for reconstruction still defaults to the truncated SVD, approximating the data with a single low-rank structure. It is common to reduce the residual further by adding an overlapping row-sparse component, but methods that solve this joint problem often require iterative solvers and tuning of regularization parameters. We propose the Disjoint Row-Sparse plus Low-Rank (D-SLR) decomposition, a closed-form drop-in for the truncated SVD that improves or exactly matches it. D-SLR restricts rows to either being stored verbatim or approximated by the low-rank fit, never both. Under squared error this restriction costs nothing: the joint optimum is attainable disjointly with fewer parameters at every non-trivial rank and stored row count (shape). With zero stored rows D-SLR reduces to the truncated SVD, so it never does worse at equal cost. The algorithm scores the entire error-versus-parameters tradeoff, and the solution is chosen afterwards by a supplied error target or parameter count, or by a selection rule. The grid and solution together cost three SVDs, with no tuning or regularization. We derive an assumption-free, a-posteriori lower bound on the error at every shape, giving each solution a computable certificate on the potential gain of any other choice of rank and stored rows. Experiments on synthetic and real data (LLM embedding tables, network traffic, hyperspectral images) confirm the gains and quantify the certificate.
ER -