cs.LGOct 7, 2026
SaveD-SLR: The Disjoint Row-Sparse plus Low-Rank Decomposition
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 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 , 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 . 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 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 |
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 |
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 |
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 : at . Right : at .