D-SLR: The Disjoint Row-Sparse plus Low-Rank Decomposition

Vincent Szolnoky

cs.LGOct 7, 2026

D-SLR: The Disjoint Row-Sparse plus Low-Rank Decomposition

Authors: Vincent Szolnoky

Organizations: Department of Mathematical Sciences Chalmers University of Technology

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.

Figures & tables

Method	Sparse	Overlap	Tuned	Iter.	Full path	Guarantee	Model
Recovery
PCP [ 5 ]	entries	yes	default	yes	no	recovery	yes
Nonconvex RPCA [ 24 ]	entries	yes	default	yes	no	recovery	yes
Outlier Pursuit [ 33 ]	rows	yes	yes	yes	no	recovery	yes
RSR [ 18 ]	none	–	no	yes	no	recovery	yes
Trimmed PCA [ 21 ]	rows	yes	yes	yes	no	stationary point	no

Table 1: D-SLR against methods of similar form. D-SLR is the only method with a sparse component that, like the truncated SVD, needs no tuning or iteration and gives the full path in one solve. Recovery methods recover an assumed underlying component, and reconstruction methods approximate the given matrix. Sparse : structure of the sparse component, none if there is no sparse component. Overlap : whether the sparse and low-rank components may share entries. Tuned : a penalty weight or threshold must be set, beyond choosing the size (default: a universal value is given). Iter. : solved iteratively. Full path : one solve gives the solution at every rank and sparsity, so a selection rule needs no re-solving. Guarantee : type of guarantee on the returned solution. Model : whether the guarantee assumes a model of the data.

Figure 1: The certificate on a small toy matrix shows where a better description could still exist, and the split floor of Section 6 closes most of these shapes (Appendix I ). Each shape $(r,k)$ is coloured by the returned score minus the floor on its score. Red shapes are still open, with the shade giving the most a description there could gain, and blue shapes are pruned. The star is the returned description, and the line bounds the open shapes.

Figure 2: Splitting the rows revives a floor that is exactly zero. Unsplit, the floor is 0. Split, it is $0.62+2.65+2.64\approx 5.9$ , shown in the left panel just below the true error of 6.73. A toy matrix at rank 1 with 7 stored rows, unsplit (left) and split into three blocks (right). In each block the binding floor is circled, and no circle means the two floors tie.

Method	Within 1%	Worst ratio	SVDs	Time (s)
D-SLR	100%	1.01	2.5	0.45
OP, tuned	94%	1.03	98	19.6
OP, default	81%	1.60	20	4.1
Convex relax.	78%	1.60	946	248
Heaviest rows	19%	2.86	0.8	0.2
Truncated SVD	16%	7.66	0.3	0.06

Table 2: D-SLR found a solution within 1% of the best score in every run, at a fraction of the cost of the iterative methods. Within 1% : share of runs whose score is within 1% of the best score any method reached on that matrix. Worst ratio : the largest ratio of a method’s score to that best score. SVDs : SVDs computed, relative to one SVD of

W

. OP is Outlier Pursuit. Time : median wall-clock time per matrix. The convex relaxation was run on two of the five seeds because of its cost.

Figure 3: D-SLR preserved the model’s behaviour far better than the truncated SVD at every parameter count, on the embedding table of Gemma 3 270M. Left : Frobenius error relative to the truncated SVD at the same parameter count, with the lower bound from the split floor. Top right : increase in held-out loss. Bottom right : share of held-out predictions that change. The search took two SVDs, and each D-SLR point one more. Heaviest rows stores the rows of largest weighted norm.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: The certificate on a small toy matrix. It shows where a better description could still exist, and how much a tighter floor narrows this down. The left panel uses the universal floor and the right panel the split floor of Section 6 , which closes most of the open shapes. Each shape $(r,k)$ is coloured by the returned score minus the floor on its score. Red shapes are still open, with the shade giving the most a description there could gain, and blue shapes are pruned. The star is the returned description, and the black line separates open from pruned shapes.

Method	Within 1%	Worst ratio	SVDs
D-SLR	100%	1.01	2.5
D-SLR, verified	100%	1.00	8.2
D-SLR without flagging	61%	5.96	2.9
Outlier Pursuit, tuned	94%	1.03	98
Outlier Pursuit, default	81%	1.60	20
Convex relaxation, tuned	78%	1.60	946

Appendix

Table 3: Every method on the torture test, including two variants of D-SLR. Without flagging, the heavy rows pull the basis away from the background, which is why Step 1 flags them. Columns as in Table 2 . Verified adds the shortlist refits of Appendix J . Default uses the method’s default weight instead of a grid search.

Method	Within 1%	Worst ratio	SVDs
D-SLR	99.9%	1.01	2.5
D-SLR, verified	100%	1.01	7.9
D-SLR without flagging	63%	5.57	2.9
Heaviest rows	25%	1.78	1.1
Truncated SVD	14%	8.29	0.3

Appendix

Table 4: D-SLR stayed within 1.1% of the best score at every shape and background rank, and within 1% in all but one of the 840 runs. Table 3 varies the share, size and noise of the heavy rows at one shape and background rank. This table holds those at each case’s middle setting and varies the shape and background rank instead. Only the methods cheap enough to run on every matrix are included, so the best is taken over the methods shown. Columns as in Table 2 .

Bound	Median (%)	Worst (%)
Universal	32.0	79.1
Split	1.7	20.5

Appendix

Table 5: The split floor certified D-SLR’s solution far more tightly than the universal floor on the torture test. Each value is the most any solution could improve on the score of D-SLR’s pick, at the price from its own noise estimate, by Theorem 5 with the given floor, as a percentage of that score. Over the 945 matrices of Table 3 .

Figure 5: The embedding table of Llama 3.2 1B, as in Figure 3 . D-SLR again beats the truncated SVD on all three measures at every parameter count.

Figure 6: Figure 3 with Outlier Pursuit added. It comes close to D-SLR at most limits but needs 174 SVDs against D-SLR’s three. Its weight only steers the number of stored rows indirectly, so at the highest limits it can only add rank, and it falls behind.

Figure 7: D-SLR matched or beat the truncated SVD at every parameter count on all three matrices. Error relative to the truncated SVD at the same parameter count, with the lower bound from the split floor. The dashed line adds the shortlist refits, and covers the solid line where the two agree. The star is the EBIC pick, which on GEANT stores no rows and so equals the truncated SVD.

Figure 8: The probe rank barely mattered, and the flagged share only failed when no more rows were flagged than the matrix had heavy rows. Worst score over each case’s matrices relative to the score at the defaults (grey lines), varying one constant at a time. Left :

r_{\mathrm{probe}}

k_{\mathrm{flag}}=n/2

. Right :

k_{\mathrm{flag}}

r_{\mathrm{probe}}=15

Explore similar work

May 27, 2026math.OC

Manifold-based Algorithms for the Hadamard Decomposition

Given a matrix

X

, and two ranks

r_1

and

r_2

, the Hadamard decomposition (HD) looks for two low-rank matrices,

X_1

of rank

r_1

and

X_2

of rank

r_2

, both of the same size as

X

, such that

X\approx X_1\circ X_2

, where

\circ

is the Hadamard (element-wise) product. In most cases, HD is more expressive than standard low-rank approximations such as the truncated singular value decomposition (TSVD), as it can represent higher-rank matrices with the same number of parameters; this is because the rank of

X_1 \circ X_2

is generically equal to

r_1 r_2

. In this paper, we first present some theoretical insights for HD, in particular a useful reformulation

X\approx WH^\top

where

W

and

H

have

r_1 r_2

columns and belong to certain manifolds. These allow us to develop three new algorithms for computing HD. The first one uses the representation

X\approx X_1\circ X_2

and relies on the Manopt toolbox. The other two rely on the reformulation

X\approx WH^\top

: one is a block projected gradient method, and the other is a manifold-based gradient descent algorithm that does not require projection onto the feasible set. The last two algorithms are particularly effective for handling large sparse data. We also propose new initializations that allow us to improve the accuracy of the HD. We compare our algorithms and initialization strategies with the TSVD and with the state of the art. Numerical results show that the new methods are efficient and competitive on both synthetic and real data.

Nicolas Gillis, Subhayan Saha, Stefano Sicilia +1

Department of Mathematics and Operational Research, University of Mons, Mons, Belgium. · SS is a member of the Gruppo Nazionale Calcolo Scientifico-Istituto Nazionale di Alta Matematica (GNCS-INdAM).

Low-Rank Matrix Decomposition Low-Rank Approximation Matrix Optimization Matrix Factorization

Ask PDF

Jun 30, 2026math.OC

Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics

Low-rank matrix optimization is often carried out via the Burer-Monteiro (BM) formulation, but choosing the factorization rank

r

is delicate and can substantially slow optimization. We propose a unified framework, termed direction-magnitude decomposition (DMD), that decomposes the optimization variable to improve optimization efficiency even when the target rank is unknown. We develop two DMD-based approaches and establish their theoretical advantages on the canonical problem of matrix factorization. The first, overparameterized DMD, uses a rank

r

larger than necessary and enjoys faster convergence as

r

increases. The second, recursive DMD, is motivated by the incremental eigenpair learning, or saddle-to-saddle, behavior of overparameterized DMD. It achieves lower memory and computational costs, complementing overparameterized DMD. Both approaches are exponentially faster than gradient descent applied to the BM formulation. Numerical experiments on matrix factorization, sensing, and completion corroborate our theoretical findings and demonstrate the practical effectiveness of DMD.

Yudong Wei, Liang Zhang, Bingcong Li +1

Department of Mathematics, ETH Zurich, Zurich, Switzerland · Department of Computer Science, ETH Zurich, Zurich, Switzerland

Low-Rank Matrix Decomposition Nonconvex Optimization Matrix Optimization Matrix Factorization Gradient Descent Dynamics

Ask PDF

Jul 3, 2026cs.LG

LACE-SVD: Loss-Aware SVD with Cumulative Error Correction for LLM Compression

The rapid growth in the parameter scale of large language models (LLMs) has created a strong demand for efficient compression techniques. As a hardware-agnostic and highly compatible approach, low-rank compression has been widely adopted to reduce both memory footprint and computational cost. However, existing SVD-based methods are still largely driven by local reconstruction objectives, overlooking two critical limitations: rank budgets are often allocated without explicitly considering layer-wise loss sensitivity, and local approximation errors can propagate and accumulate through the residual stream, leading to amplified global deviations from the original model. To address these issues, we propose LACE-SVD, a Loss-Aware SVD framework with Cumulative Error correction for LLM compression. LACE-SVD first estimates the calibration negative-log-likelihood increase induced by candidate layer-wise compression ratios and solves a budget-constrained allocation problem to assign rank budgets. It then refines the compressed model with closed-form local updates and introduces a propagation-aware correction for residual-stream output modules, reducing layer-output discrepancy as a proxy for cumulative error propagation. Experimental results demonstrate that at a high compression ratio (0.6), the WikiText-2 PPL of our method on LLaMA-7B (32.57) is significantly better than that of Dobi-SVD (46.18).

Zhuowen Liu, Longkun Hao, Shiyu Feng +3

Zhuowen Liu1 · Longkun Hao2 · Shiyu Feng3 +3

Model Compression LLM Compression Low-Rank Matrix Decomposition Low-Rank Compression Low-Rank Approximation Singular Value Decomposition

Ask PDF