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

# 1Introduction
Source: [https://arxiv.org/html/2610.10636](https://arxiv.org/html/2610.10636)
D\-SLR: The Disjoint Row\-Sparse plus Low\-Rank Decomposition

Vincent SzolnokyDepartment of Mathematical SciencesChalmers 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\.

## 1Introduction

The truncated SVD is the default way to compress a matrixWWwhen nothing else is known about it\. It fits every row with one shared low\-rank basis, which works well when the rows agree on that basis\. When a group of rows does not, it pulls the shared basis away from the majority, and the rank must grow to keep the error down\. Since the misfit lives in whole rows, a common fix is to add a row\-sparse componentSSthat absorbs them, leaving the low\-rank componentLLto capture the rest\. This gives the problem

minL,S\\displaystyle\\min\_\{L,S\}‖W−L−S‖F2\\displaystyle\\\|W\-L\-S\\\|^\{2\}\_\{F\}\(1\)s\.t\.\\displaystyle\\text\{s\.t\.\}rank⁡\(L\)≤r,\\displaystyle\\operatorname\{rank\}\(L\)\\leq r,S​has at mostknon\-zero rows\.\\displaystyle S\\text\{ has at most $k$ non\-zero rows\.\}Problem \([1](https://arxiv.org/html/2610.10636#S1.E1)\) is hard for two reasons\. It is non\-convex and combinatorial, because the rank bound and the row count are both cardinality constraints\. AndLLandSSmay overlap, so a row can be split between them, which couples the two components\. A possible remedy is the convex relaxation

minL,S⁡‖W−L−S‖F2\+λ1​‖L‖∗\+λ2​‖S‖2,1,\\min\_\{L,S\}\\ \\\|W\-L\-S\\\|^\{2\}\_\{F\}\+\\lambda\_\{1\}\\\|L\\\|\_\{\\ast\}\+\\lambda\_\{2\}\\\|S\\\|\_\{2,1\},\(2\)where∥⋅∥∗\\\|\\cdot\\\|\_\{\\ast\}is the nuclear norm and∥⋅∥2,1\\\|\\cdot\\\|\_\{2,1\}sums the row norms\. It is convex, but its penalties are non\-smooth and the components stay coupled, so it is solved iteratively, andλ1\\lambda\_\{1\}andλ2\\lambda\_\{2\}must be tuned\.

D\-SLR adds one requirement\. Each row is either stored verbatim inSSor approximated byLL,never both\. This removes the coupling, but it looks like a concession, because it shrinks the feasible set of \([1](https://arxiv.org/html/2610.10636#S1.E1)\)\. With row sparsity and squared error it is not, and removing whole rows leaves a plain SVD to solve\. This is why we use rows rather than entries\. We make three contributions\.

1. 1\.Disjointness is free\.At every rank and stored\-row count, the optimum of \([1](https://arxiv.org/html/2610.10636#S1.E1)\) is attainable by a disjoint solution, which needs fewer parameters than the overlapping one, whenever both rows and rank are used \(Proposition[1](https://arxiv.org/html/2610.10636#Thmtheorem1)\)\. With no stored rows D\-SLR is the truncated SVD, so at equal parameter count it is never worse than the SVD\. This makes D\-SLR a drop\-in for the truncated SVD\.
2. 2\.An assumption\-free certificate\.FromWWalone we lower\-bound the error of every row\-sparse solution \(Corollary[4](https://arxiv.org/html/2610.10636#Thmtheorem4)\)\. A block\-wise construction then tightens this floor, never weakening it, by applying it to blocks of rows, which in our tests shrank the certified gap by an order of magnitude \(Theorem[6](https://arxiv.org/html/2610.10636#Thmtheorem6)\)\. Adding a price per parameter stored turns this into a bound on how much any rival row\-sparse solution could improve the score of the returned one\. A bound of zero proves the returned solution is a global minimiser among row\-sparse solutions, and a positive bound says how much room is left and at which ranks and row counts\. Unlike a\-priori guarantees, it is computed after the fit for the given matrix and assumes no model of the data\.
3. 3\.A closed\-form algorithm with no tuning\.Because rows are disjoint, a solution is just a set of stored rows and an SVD of the rest\. This lets us attack \([1](https://arxiv.org/html/2610.10636#S1.E1)\) directly, scoring every rank and row count with a closed\-form upper bound on the error, at the cost of three SVDs and no iterations \(Section[7](https://arxiv.org/html/2610.10636#S7)\)\. Together with the certificate’s floor, these scores bracket the best achievable error at every parameter count\. A solution is then picked by an error target, a parameter count or a selection rule such as EBIC, so neither the rank nor row count has to be chosen in advance\. Because the scores use an upper bound, the final pick can optionally refit the top few solutions on the exact error and keep the best, at one SVD per refit\.

Together, these make D\-SLR a drop\-in for the truncated SVD that is never worse at equal cost, costs three SVDs, and states how far it could be from the best\.

On synthetic matrices built to stress each part of the method, D\-SLR matched or beat iterative methods at a small fraction of their cost, and in most cases the certificate proved its score was within a few percent of the best achievable\. On LLM embedding tables, when retaining only half the table’s parameters, D\-SLR changed about ten times fewer of the model’s predictions than the truncated SVD, and matched or improved on storing the heaviest rows with the best row count chosen on the exact error\.

## 2Related work

#### Sparse\-plus\-low\-rank models\.

Sparse\-plus\-low\-rank decompositions are best known from robust PCA\. Principal component pursuit\[[5](https://arxiv.org/html/2610.10636#bib.bib1)\]splits a matrix into a low\-rank component and an overlapping, entrywise sparse component\. Later work added dense noise\[[37](https://arxiv.org/html/2610.10636#bib.bib2)\]and replaced the convex program with faster non\-convex projections\[[24](https://arxiv.org/html/2610.10636#bib.bib3)\]\. Closest to D\-SLR in form is Outlier Pursuit \(OP\)\[[33](https://arxiv.org/html/2610.10636#bib.bib5)\], whose sparse component is row\-sparse\. These methods assume the matrix was generated as a low\-rank component plus sparse perturbations, and their goal is to recover either of the components or both\. D\-SLR has a different goal\. It approximates the given matrix as closely as possible for its parameter count, which a recovery method does not optimise\. A few methods do target the approximation error, either directly at a fixed rank and sparsity\[[36](https://arxiv.org/html/2610.10636#bib.bib4)\]or weighted by input activations to compress LLM weights\[[35](https://arxiv.org/html/2610.10636#bib.bib27)\]\. Both keep an overlapping, entrywise sparse component and alternate between the two components\. LoSparse\[[19](https://arxiv.org/html/2610.10636#bib.bib26)\]instead trains a low\-rank component plus a column\-sparse component on the task loss\. All of these methods are iterative, and each run returns one solution for one setting of its penalty weights, or of its rank and sparsity\. Tracing the trade\-off between error and parameter count means solving again for every setting\. D\-SLR’s search is closed form, so a single pass scores every rank and row count at once, for three SVDs\.

#### Low\-rank approximations for compression\.

The truncated SVD gives the best low\-rank approximation of any matrix in Frobenius norm\[[11](https://arxiv.org/html/2610.10636#bib.bib6)\]\. It is fast, closed form and assumes nothing about the data, which has made it a default compressor across many fields\. In imaging it has been used from early image storage to MRI and hyperspectral data\[[1](https://arxiv.org/html/2610.10636#bib.bib7),[22](https://arxiv.org/html/2610.10636#bib.bib8),[34](https://arxiv.org/html/2610.10636#bib.bib9)\]\. In the sciences it condenses seismic, geothermal and single\-cell data\[[4](https://arxiv.org/html/2610.10636#bib.bib10),[32](https://arxiv.org/html/2610.10636#bib.bib22),[25](https://arxiv.org/html/2610.10636#bib.bib11)\]and underlies reduced\-order modelling\[[9](https://arxiv.org/html/2610.10636#bib.bib12)\]\. In machine learning it compresses neural network weights\[[8](https://arxiv.org/html/2610.10636#bib.bib13)\], most recently in large language models\[[28](https://arxiv.org/html/2610.10636#bib.bib21),[31](https://arxiv.org/html/2610.10636#bib.bib14)\]\. D\-SLR is also closed form and assumption\-free, at the cost of a few SVDs, so it can serve as a drop\-in for the SVD in any of these settings\.

#### Optimality certificates\.

Guarantees in low\-rank modelling are usually a priori\. Dual certificates for convex relaxations prove recovery under an assumed model of the data\[[6](https://arxiv.org/html/2610.10636#bib.bib16),[14](https://arxiv.org/html/2610.10636#bib.bib15)\], and analyses of non\-convex solvers bound the error over a model class\[[24](https://arxiv.org/html/2610.10636#bib.bib3)\]\. Both are properties of the method, fixed before the matrix is seen\. The certificate of Theorem[5](https://arxiv.org/html/2610.10636#Thmtheorem5)is instead computed fromWWafter the fit and assumes no structure inWW, like the gap reported by a branch\-and\-bound solver\.\[[2](https://arxiv.org/html/2610.10636#bib.bib28)\]obtain such gaps for entrywise sparse plus low rank by branch\-and\-bound, for one rank and sparsity at a time and at a cost that grows quickly with the matrix size\. Our certificate is closed form\. It lower\-bounds the error of every row\-sparse solution at every rank and row count at once, and when positive it says where a better solution could still exist\.

#### Row selection and model selection\.

Choosing a subset of rows is also central to row sampling and coresets\[[10](https://arxiv.org/html/2610.10636#bib.bib29),[17](https://arxiv.org/html/2610.10636#bib.bib17)\]\. There the chosen rows stand in for the whole matrix, and the rest are approximated through them\. D\-SLR does the opposite\. It stores the rows that fit the shared basis worst and keeps them out of that basis\. Choosing the rank and row count is a model\-selection problem\. We adapt the extended BIC\[[7](https://arxiv.org/html/2610.10636#bib.bib30),[20](https://arxiv.org/html/2610.10636#bib.bib20)\], which is built for very many candidate models, as in our grid of ranks and row counts\. Since the score uses a single price per parameter, other penalties such as MDL\[[26](https://arxiv.org/html/2610.10636#bib.bib18)\]or data\-driven penalties\[[3](https://arxiv.org/html/2610.10636#bib.bib19)\]can be used in its place\.

Table[1](https://arxiv.org/html/2610.10636#S2.T1)summarises how these methods compare to D\-SLR\.

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\.MethodSparseOverlapTunedIter\.Full pathGuaranteeModel*Recovery*PCP\[[5](https://arxiv.org/html/2610.10636#bib.bib1)\]entriesyesdefaultyesnorecoveryyesNonconvex RPCA\[[24](https://arxiv.org/html/2610.10636#bib.bib3)\]entriesyesdefaultyesnorecoveryyesOutlier Pursuit\[[33](https://arxiv.org/html/2610.10636#bib.bib5)\]rowsyesyesyesnorecoveryyesRSR\[[18](https://arxiv.org/html/2610.10636#bib.bib23)\]none–noyesnorecoveryyesTrimmed PCA\[[21](https://arxiv.org/html/2610.10636#bib.bib24)\]rowsyesyesyesnostationary pointno*Reconstruction*Truncated SVD\[[11](https://arxiv.org/html/2610.10636#bib.bib6)\]none–nonoyesglobal optimumnoCoresets\[[10](https://arxiv.org/html/2610.10636#bib.bib29),[17](https://arxiv.org/html/2610.10636#bib.bib17)\]none–nononoerror boundnoGoDec\[[36](https://arxiv.org/html/2610.10636#bib.bib4)\]entriesyesnoyesnolocal convergencenoDiscrete SLR\[[2](https://arxiv.org/html/2610.10636#bib.bib28)\]entriesyesyesyesnocertified gap \(smallnn\)noConvex relax\. \([2](https://arxiv.org/html/2610.10636#S1.E2)\)rowsyesyesyesnorelaxed optimumnoD\-SLRrowsnononoyesscore certificateno

## 3Problem formulation

#### Notation\.

LetW∈ℝn×mW\\in\\mathbb\{R\}^\{n\\times m\}be the input matrix and𝒩\\mathcal\{N\}its set of rows\. For any matrixXXand set of rowsKK,XKX\_\{K\}denotes the rows ofXXindexed byKK\. Writeσ1​\(X\)≥σ2​\(X\)≥…\\sigma\_\{1\}\(X\)\\geq\\sigma\_\{2\}\(X\)\\geq\\dotsfor the singular values ofXX, withσi​\(X\)=0\\sigma\_\{i\}\(X\)=0beyond the smaller dimension ofXX\. Define

T⁡\(X,r\)\\displaystyle T\(X;r\)=∑i\>rσi​\(X\)2,\\displaystyle=\\sum\_\{i\>r\}\\sigma\_\{i\}\(X\)^\{2\},\(3\)R⁡\(X,k\)\\displaystyle R\(X;k\)=sum of theklargest squared\\displaystyle=\\text\{sum of the $k$ largest squared\}row norms ofX\.\\displaystyle\\phantom\{=\}\\ \\text\{row norms of $X$\}\.\(4\)By the Eckart–Young theorem,T⁡\(X,r\)=‖X−Xr‖F2T\(X;r\)=\\\|X\-X\_\{r\}\\\|\_\{F\}^\{2\}, whereXrX\_\{r\}is the best rank\-rrapproximation ofXX\[[11](https://arxiv.org/html/2610.10636#bib.bib6)\]\. SoTTis the energy a rank\-rrfit leaves behind\. When the matrix argument is omitted, as inT⁡\(r\)T\(r\), it is the matrix under discussion, usuallyWW\.

#### Descriptions and solutions\.

A*description*is a pair\(r,K\)\(r,K\)of a rank0≤r≤min⁡\{n,m\}0\\leq r\\leq\\min\\\{n,m\\\}and a setK⊆𝒩K\\subseteq\\mathcal\{N\}of rows to store verbatim\. Its*shape*is\(r,k\)\(r,k\)withk=\|K\|k=\|K\|, andB=𝒩∖KB=\\mathcal\{N\}\\setminus Kis the set of unstored rows\. The description defines the D\-SLR*solution*W^=S\+L\\hat\{W\}=S\+L, whereSSequalsWWon the rowsKKand is zero elsewhere, andLLis the best rank\-rrapproximation ofWBW\_\{B\}on the rowsBBand is zero onKK\. Its*error*is

E⁡\(r,K\)=‖W−S−L‖F2=T⁡\(WB,r\),E\(r,K\)=\\\|W\-S\-L\\\|\_\{F\}^\{2\}=T\(W\_\{B\};r\),\(5\)and for any matrixXXwe writeE⁡\(X,r,K\)E\(X;r,K\)for the error of\(r,K\)\(r,K\)onXX\. A description says which rows to store and which rank to use, and the solution is the matrix it produces\. The shape only counts the two\. Many descriptions share a shape, and their cost depends on the shape alone\. Where the pairs pile up, we writey=\(r,K\)y=\(r,K\)for a description ands=\(r,k\)s=\(r,k\)for its shape, and evaluate functions of descriptions, such asEE, atyyand functions of shapes, such asCC, atss\.

#### Cost\.

StoringWKW\_\{K\}takesk​mkmparameters, and storing the rank\-rrapproximation of then−kn\-kunstored rows takesr⁡\(n−k\+m\)r\(n\-k\+m\)\. A shape therefore costs

C⁡\(r,k\)=k​m\+r⁡\(n−k\+m\),C\(r,k\)=km\+r\(n\-k\+m\),\(6\)with the rank term dropped whenk=nk=nand nothing is left to approximate\. The cost counts what the shape reserves, whatever values are stored\. We do not count the indices of the stored rows\. They arekkintegers next to thek​mkmstored values, so including them would raise the cost by a factor of at most1\+1/m1\+1/m\.

Before looking at any data, the cost alone already tells us where D\-SLR should help most\. One more stored row addsm−rm\-rparameters, while one more rank addsn−k\+mn\-k\+m\. A row is therefore always cheaper than a rank, because storing it also removes it from the low\-rank factor\. For smallrrandkka rank costs about1\+n/m1\+n/mrows, so the taller the matrix \(n≫mn\\gg m\), the more rows the same parameters can buy\. D\-SLR therefore tends to work best on tall matrices, although whether a row actually lowers the error more than a rank still depends on the data\.

#### Problem\.

Every description gives a point of cost and error\. The best trade\-off between the two is the*frontier*

F⁡\(c\)=min⁡\{E⁡\(r,K\):C⁡\(r,\|K\|\)≤c\},F\(c\)=\\min\\bigl\\\{E\(r,K\):C\(r,\|K\|\)\\leq c\\bigr\\\},\(7\)the lowest error reachable withinccparameters\. Picking a solution under a parameter limit means readingFFat that limit, and picking one for an error target means finding the smallestccthat reaches it\. To pick a solution without either, we price each parameter atλ\>0\\lambda\>0in squared\-error units and minimise the*score*

Q⁡\(r,K\)=E⁡\(r,K\)\+λ​C​\(r,\|K\|\)\.Q\(r,K\)=E\(r,K\)\+\\lambda C\(r,\|K\|\)\.\(8\)The minimiser is\(r^,K^\)=arg​minr,K⁡Q​\(r,K\)\(\\hat\{r\},\\hat\{K\}\)=\\argmin\_\{r,K\}Q\(r,K\), and Section[7](https://arxiv.org/html/2610.10636#S7)setsλ\\lambdawith EBIC\.

Given a returned solution, could another rival solution have a lower error at the same cost, or a lower score? If so, then*potentially*by how much, and where in the solution space could it lie? And how can one efficiently compute the frontier and the score in the first place? The rest of the paper answers these in turn\. Section[4](https://arxiv.org/html/2610.10636#S4)first shows that nothing is lost by forbidding overlap\. Section[5](https://arxiv.org/html/2610.10636#S5)lower\-bounds the error at every shape, which gives a floor under the frontier and a certificate for the score, and Section[6](https://arxiv.org/html/2610.10636#S6)tightens it with blocks of rows\. Section[7](https://arxiv.org/html/2610.10636#S7)gives the algorithm and Section[8](https://arxiv.org/html/2610.10636#S8)the experiments\. Proofs and further results are in the appendix\.

## 4Disjointness is lossless and cheaper

Forbidding overlap shrinks the feasible set of \([1](https://arxiv.org/html/2610.10636#S1.E1)\), so does D\-SLR give anything up? We now show that it does not\. Take any solution of \([1](https://arxiv.org/html/2610.10636#S1.E1)\) whereSSandLLoverlap, and call the rows whereSSis non\-zeroKK\. On those rows,SScan at best absorb whateverLLleaves behind\. But why absorb only the leftover?SScan just as well store the entire rowsWKW\_\{K\}, andLLcan drop them altogether\. The error onKKthen becomes zero,LLis free to fit the remaining rowsWBW\_\{B\}as well as it can, and the rows ofLLinsideKKno longer need to be stored\. This is exactly the disjoint solution of\(r,K\)\(r,K\)\.

###### Proposition 1\(Disjointness is lossless and cheaper\)\.

Fixrrandkk\. LetL∈ℝn×mL\\in\\mathbb\{R\}^\{n\\times m\}haverank⁡\(L\)≤r\\operatorname\{rank\}\(L\)\\leq r, and letS∈ℝn×mS\\in\\mathbb\{R\}^\{n\\times m\}have all its non\-zero rows inside a setKKwith\|K\|=k\|K\|=k\. StoringLLandSSseparately costsr⁡\(n\+m\)\+k​mr\(n\+m\)\+kmparameters\. Then the disjoint solution of\(r,K\)\(r,K\)is no worse and no more expensive,

‖W−L−S‖F2\\displaystyle\\\|W\-L\-S\\\|^\{2\}\_\{F\}≥E⁡\(r,K\),\\displaystyle\\geq E\(r,K\),\(9\)r⁡\(n\+m\)\+k​m\\displaystyle r\(n\+m\)\+km≥C⁡\(r,k\),\\displaystyle\\geq C\(r,k\),\(10\)and \([10](https://arxiv.org/html/2610.10636#S4.E10)\) is strict wheneverr\>0r\>0andk\>0k\>0\. In particular, the optimum of \([1](https://arxiv.org/html/2610.10636#S1.E1)\) equalsmin\|K\|=k⁡E⁡\(r,K\)\\min\_\{\|K\|=k\}E\(r,K\), so it is attainable by a disjoint solution\.

So the overlap that couplesLLandSSis not required to reach the optimum\. An overlapping solution can match the disjoint one in error, but it spends extra parameters on rows thatSScan cover anyway\. The lossless part \([9](https://arxiv.org/html/2610.10636#S4.E9)\) is already known in a slightly different form from the RPCA literature, where it shows that the minimising subspace is the same with and without overlap\[[21](https://arxiv.org/html/2610.10636#bib.bib24)\]\. Here we state it for every shape and price both solutions with \([10](https://arxiv.org/html/2610.10636#S4.E10)\)\. No restriction is placed on howLLandSSare built fromWW, so the result covers every overlapping solution with a row\-sparseSS\. It does not extend to an entrywise sparseSS, because zeroing single entries ofLLgenerally raises its rank, soLLcannot simply step aside whereSSstores values\.

## 5A universal certificate valid for any matrix

For a subspaceV⊆ℝmV\\subseteq\\mathbb\{R\}^\{m\}withdimV=r\\dim V=rand orthogonal projectorPVP\_\{V\}, the error of the best rank\-rrapproximation of a matrixXXcan be written as

mindimV=r⁡\[‖X‖F2−‖X​PV‖F2\]=T⁡\(X,r\)\.\\min\_\{\\dim V=r\}\\Bigl\[\\\|X\\\|^\{2\}\_\{F\}\-\\\|XP\_\{V\}\\\|^\{2\}\_\{F\}\\Bigr\]=T\(X;r\)\.\(11\)WithX=WBX=W\_\{B\}, the errorE⁡\(r,K\)E\(r,K\)is the smallest total squared distance from the unstored rows to anyrr\-dimensional subspace\. It depends on two things, which rows are stored and which subspace is used\. We derive two lower bounds by attacking \([11](https://arxiv.org/html/2610.10636#S5.E11)\) from either side\. Each one forgets one of the two things and assumes the worst case in its place\.

First we forget which rows are stored\. Whichever they are,W^=S\+L\\hat\{W\}=S\+Lis a matrix of rank at mostr\+kr\+k, becauseSShaskknon\-zero rows andLLhas rank at mostrr\. SoW^\\hat\{W\}can never be closer toWWthan the best rank\-\(r\+k\)\(r\+k\)approximation\.

###### Lemma 2\(Spectral floor\)\.

For allrr,kkand everyKKwith\|K\|=k\|K\|=k,E⁡\(r,K\)≥T⁡\(r\+k\)E\(r,K\)\\geq T\(r\+k\)\.

Next we do the opposite and forget which subspace is used\. Storing a row removes its error, but that error is never more than the row’s own energy\. So compared with storing no rows at all, storingkkrows can lower the error by at most the energy of thekkheaviest rows\.

###### Lemma 3\(Row\-energy floor\)\.

For allrr,kkand everyKKwith\|K\|=k\|K\|=k,E⁡\(r,K\)≥T⁡\(r\)−R⁡\(k\)E\(r,K\)\\geq T\(r\)\-R\(k\)\.

Lemma[2](https://arxiv.org/html/2610.10636#Thmtheorem2)follows from Eckart–Young applied at rankr\+kr\+k, and Lemma[3](https://arxiv.org/html/2610.10636#Thmtheorem3)from bounding what each stored row can remove from the error\. Both floors hold at once, so we keep whichever is larger\. This gives a floor that holds for every description at every shape, which is what the certificate below is built on\.

###### Corollary 4\(Universal floor\)\.

For any matrixXXand allrr,kk, define

E¯​\(X,r,k\)=max⁡\{T⁡\(X,r\+k\),T⁡\(X,r\)−R⁡\(X,k\),0\}\.\\underline\{E\}\(X;r,k\)=\\max\\bigl\\\{T\(X;r\+k\),\\ T\(X;r\)\-R\(X;k\),\\ 0\\bigr\\\}\.Then

1. 1\.E⁡\(X,r,K\)≥E¯​\(X,r,k\)E\(X;r,K\)\\geq\\underline\{E\}\(X;r,k\)for everyKKwith\|K\|=k\|K\|=k, and
2. 2\.E¯​\(X,r,k\)≥T⁡\(X,r\+k−j\)−R⁡\(X,j\)\\underline\{E\}\(X;r,k\)\\geq T\(X;r\+k\-j\)\-R\(X;j\)for everyj∈\{0,…,k\}j\\in\\\{0,\\ldots,k\\\}\.

The second item answers a question one might have\. Could a mix of the two be better, treating some of the stored rows as extra ranks and the rest as heavy rows? Each such mix is also a valid floor, but none of them beats the larger endpoints, so nothing is lost by keeping only the two\.

Because the floor holds at every shape, it also bounds the frontier \([7](https://arxiv.org/html/2610.10636#S3.E7)\) from below,

F⁡\(c\)≥min⁡\{E¯​\(r,k\):C⁡\(r,k\)≤c\}\.F\(c\)\\geq\\min\\bigl\\\{\\underline\{E\}\(r,k\):C\(r,k\)\\leq c\\bigr\\\}\.\(12\)This holds with any valid floor in place ofE¯\\underline\{E\}, such as the split floor of Section[6](https://arxiv.org/html/2610.10636#S6), which gives the lower bounds in our experiments\.

The floor also lets us certify a single returned descriptiony^\\hat\{y\}with shapes^\\hat\{s\}and scoreq^=Q⁡\(y^\)\\hat\{q\}=Q\(\\hat\{y\}\)\. We say a rivaly′y^\{\\prime\}with shapes′s^\{\\prime\}*beats*it ifQ⁡\(y′\)<q^Q\(y^\{\\prime\}\)<\\hat\{q\}\. Writing out the score, this happens exactly whenE⁡\(y′\)<E⁡\(y^\)\+λ⁡\(C⁡\(s^\)−C⁡\(s′\)\)E\(y^\{\\prime\}\)<E\(\\hat\{y\}\)\+\\lambda\(C\(\\hat\{s\}\)\-C\(s^\{\\prime\}\)\)\. So a cheaper rival may be worse by less than what it saves, priced byλ\\lambda, and a more expensive rival must be better by more than what it costs\.

###### Theorem 5\(Score certificate\)\.

Lety^\\hat\{y\}be a description with shapes^\\hat\{s\}and scoreq^=Q⁡\(y^\)\\hat\{q\}=Q\(\\hat\{y\}\)\. Define the floor on the score at each shape

Q¯​\(s\)=E¯​\(s\)\+λ​C​\(s\),\\underline\{Q\}\(s\)=\\underline\{E\}\(s\)\+\\lambda C\(s\),and setqmax=q^−mins⁡Q¯​\(s\)q\_\{\\max\}=\\hat\{q\}\-\\min\_\{s\}\\underline\{Q\}\(s\)\. Then the following hold\.

1. 1\.Every descriptiony′y^\{\\prime\}with shapes′s^\{\\prime\}satisfiesQ⁡\(y′\)≥Q¯​\(s′\)Q\(y^\{\\prime\}\)\\geq\\underline\{Q\}\(s^\{\\prime\}\)\. So a shapes′s^\{\\prime\}can contain a description that beatsy^\\hat\{y\}only ifQ¯​\(s′\)<q^\\underline\{Q\}\(s^\{\\prime\}\)<\\hat\{q\}\.
2. 2\.The gap to the global minimum satisfies 0≤q^−miny⁡Q⁡\(y\)≤qmax,0\\leq\\hat\{q\}\-\\min\_\{y\}Q\(y\)\\leq q\_\{\\max\},andy^\\hat\{y\}is a global minimiser ofQQwheneverqmax=0q\_\{\\max\}=0\.

Theorem[5](https://arxiv.org/html/2610.10636#Thmtheorem5)can be checked for any returned description, regardless of how it was produced, and it is cheap to calculate\. The universal floor only needs the singular values and row norms ofWW, so it costs a single SVD\. The shapes withQ¯​\(s′\)<q^\\underline\{Q\}\(s^\{\\prime\}\)<\\hat\{q\}are the only places where a better description could still exist, andq^−Q¯​\(s′\)\\hat\{q\}\-\\underline\{Q\}\(s^\{\\prime\}\)is the most it could gain there\. This is only an upper bound, and it says nothing about whether any description actually reaches it\. The certificate also holds only for the givenλ\\lambda, so a new price means recomputing it\. Finally, nothing in the theorem depends on howE¯\\underline\{E\}was obtained\. Any valid lower bound on the error can be swapped in, and a tighter one gives a sharper certificate\. Section[6](https://arxiv.org/html/2610.10636#S6)builds such a bound\.

The certificate prunes much like branch\-and\-bound \(BnB\), with each shape playing the role of a box\. Each box has a floor on the score of every description inside it, and a box is pruned when its floor is at least the incumbent’s score\. The box holding the incumbent can never be pruned\. Its gapq^−Q¯​\(s^\)=E⁡\(y^\)−E¯​\(s^\)\\hat\{q\}\-\\underline\{Q\}\(\\hat\{s\}\)=E\(\\hat\{y\}\)\-\\underline\{E\}\(\\hat\{s\}\)is the slack between the returned error and its own floor, which only a tighter floor can close\. Figure[1](https://arxiv.org/html/2610.10636#S5.F1)shows the certificate on a small example\.

![Refer to caption](https://arxiv.org/html/2610.10636v1/fig_certificate_universal.png)Figure 1:The certificate on a small toy matrix shows where a better description could still exist, and the split floor of Section[6](https://arxiv.org/html/2610.10636#S6)closes most of these shapes \(Appendix[I](https://arxiv.org/html/2610.10636#A9)\)\. Each shape\(r,k\)\(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\.
## 6A block\-wise tightening of the certificate

Both floors in Corollary[4](https://arxiv.org/html/2610.10636#Thmtheorem4)are worst\-case bounds, and each can become vacuous for completely benign reasons\. The spectral floor forgets which rows are stored, so it fades to zero oncer\+kr\+kreaches the rank ofWW\. The row\-energy floor forgets which subspace is used, so it is clipped to zero as soon as a few heavy rows outweigh the entire residualT⁡\(r\)T\(r\)\. Neither failure means the true error is small\. Each floor has simply discarded the one piece of information that would have kept it alive\. We cannot add that information back without breaking the floors, so we need another route\.

The route is to split the rows into blocks\. The squared error is a sum over rows, so it is also a sum over blocks, and a floor on each block’s share of the error adds up to a floor on the whole\. All blocks share the sameLL, but a sharedLLcan fit each block no better than that block’s own best rank\-rrfit, so the universal floor still applies to each block on its own\. The split floor therefore reuses the universal floor unchanged\. It drops only the requirement that blocks share a basis, keeps the total number of stored rows exact, and so lets each block recover information the universal floor discarded\. The only thing we do not know is how thekkstored rows are spread over the blocks, so we take the smallest total over every possible spread \(Theorem[6](https://arxiv.org/html/2610.10636#Thmtheorem6)\)\.

Figure[2](https://arxiv.org/html/2610.10636#S6.F2)shows why this helps on a small matrix at rank 1 with 7 stored rows\. Unsplit, both floors are dead\. The spectral floor has run out of tail becauser\+kr\+kreaches the rank of the matrix, and a few heavy rows clip the row\-energy floor to zero\. Splitting the rows into three blocks changes this\. The heavy rows are isolated in one block, which takes none of the stored rows\. With them out of the way, the row\-energy floor binds in a second block, and the third block only has to store two rows, so its spectral floor binds instead\. The total comes back close to the true error\.

![Refer to caption](https://arxiv.org/html/2610.10636v1/fig_blockwise_revive.png)Figure 2:Splitting the rows revives a floor that is exactly zero\. Unsplit, the floor is 0\. Split, it is0\.62\+2\.65\+2\.64≈5\.90\.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\.###### Theorem 6\(Split floor\)\.

Let𝒫=\{𝒫1,…,𝒫t\}\\mathcal\{P\}=\\\{\\mathcal\{P\}\_\{1\},\\ldots,\\mathcal\{P\}\_\{t\}\\\}be any partition of the rows ofWWintottnon\-empty blocks, and let

𝒢\(k\)=\{\(g1,…,gt\):0≤gj≤\|𝒫j\|,∑jgj=k\}\\mathcal\{G\}\(k\)=\\Bigl\\\{\(g\_\{1\},\\ldots,g\_\{t\}\):0\\leq g\_\{j\}\\leq\|\\mathcal\{P\}\_\{j\}\|,\\ \\textstyle\\sum\_\{j\}g\_\{j\}=k\\Bigr\\\}be the ways of spreadingkkstored rows over the blocks\. Define the*split floor*

E¯𝒫​\(r,k\)=min⁡∑j=1t\(g1,…,gt\)∈𝒢⁡\(k\)⁡E¯​\(W𝒫j,r,gj\)\.\\underline\{E\}\_\{\\mathcal\{P\}\}\(r,k\)=\\min\_\{\(g\_\{1\},\\ldots,g\_\{t\}\)\\in\\mathcal\{G\}\(k\)\}\\sum\_\{j=1\}^\{t\}\\underline\{E\}\\bigl\(W\_\{\\mathcal\{P\}\_\{j\}\};r,g\_\{j\}\\bigr\)\.ThenE⁡\(r,K\)≥E¯𝒫​\(r,k\)E\(r,K\)\\geq\\underline\{E\}\_\{\\mathcal\{P\}\}\(r,k\)for allrr,kkand everyKKwith\|K\|=k\|K\|=k\.

Every partition gives a valid floor, so we can use several and keep the largest\. The partitions may even be chosen by looking atWW, for example by sorting its rows by norm, because Theorem[6](https://arxiv.org/html/2610.10636#Thmtheorem6)holds for every partition\.

###### Corollary 7\(Floor over many partitions\)\.

Let𝒫\(1\),…,𝒫\(J\)\\mathcal\{P\}^\{\(1\)\},\\ldots,\\mathcal\{P\}^\{\(J\)\}be partitions of the rows ofWW, possibly chosen usingWW, and define

E¯⋆​\(r,k\)=max⁡\{E¯​\(r,k\),E¯𝒫\(1\)​\(r,k\),…,E¯𝒫\(J\)​\(r,k\)\}\.\\underline\{E\}^\{\\star\}\(r,k\)=\\max\\bigl\\\{\\underline\{E\}\(r,k\),\\ \\underline\{E\}\_\{\\mathcal\{P\}^\{\(1\)\}\}\(r,k\),\\ldots,\\underline\{E\}\_\{\\mathcal\{P\}^\{\(J\)\}\}\(r,k\)\\bigr\\\}\.ThenE⁡\(r,K\)≥E¯⋆​\(r,k\)E\(r,K\)\\geq\\underline\{E\}^\{\\star\}\(r,k\)for everyKKwith\|K\|=k\|K\|=k, and Theorem[5](https://arxiv.org/html/2610.10636#Thmtheorem5)and \([12](https://arxiv.org/html/2610.10636#S5.E12)\) hold withE¯⋆\\underline\{E\}^\{\\star\}in place ofE¯\\underline\{E\}\.

Each partition only needs the singular values of its blocks\. Together the blocks hold thennrows ofWW, so a partition in total costs at most about one SVD ofWWto check\. Appendix[I](https://arxiv.org/html/2610.10636#A9)describes the partitions we use\.

There is one catch\. The number of ways to spreadkkrows overttblocks grows like\(k\+t−1t−1\)\\binom\{k\+t\-1\}\{t\-1\}, so the minimum in Theorem[6](https://arxiv.org/html/2610.10636#Thmtheorem6)looks expensive\. It turns out to be a simple sort\. Storing one more row in a block can only lower that block’s floor, and by less each time\. So the lowest total comes from taking thekklargest drops across all blocks, that is thekkmost negative\.

###### Proposition 8\(The split floor is a sort\)\.

Let𝒫\\mathcal\{P\}be a partition as in Theorem[6](https://arxiv.org/html/2610.10636#Thmtheorem6)andk≤nk\\leq n\. For each block, write the change in its floor from storing one more row as

δj​\(i\)=E¯​\(W𝒫j,r,i\)−E¯​\(W𝒫j,r,i−1\),1≤i≤\|𝒫j\|\.\\delta\_\{j\}\(i\)=\\underline\{E\}\(W\_\{\\mathcal\{P\}\_\{j\}\};r,i\)\-\\underline\{E\}\(W\_\{\\mathcal\{P\}\_\{j\}\};r,i\-1\),\\quad 1\\leq i\\leq\|\\mathcal\{P\}\_\{j\}\|\.ThenE¯𝒫​\(r,k\)=∑j=1tE¯​\(W𝒫j,r,0\)\\underline\{E\}\_\{\\mathcal\{P\}\}\(r,k\)=\\sum\_\{j=1\}^\{t\}\\underline\{E\}\(W\_\{\\mathcal\{P\}\_\{j\}\};r,0\)plus the sum of thekksmallest, i\.e\. most negative, of allδj​\(i\)\\delta\_\{j\}\(i\)\.

## 7The D\-SLR algorithm

How can every shape be scored without solving each one separately? The key is to fix the basis\. If the rank\-rrfit of the unstored rows is restricted to the toprrdirections of one fixed basisV^\\hat\{V\}, then each row’s error at rankrris simply its energy outside those directions\. The bestkkrows to store are then thekkwith the most energy left over, so one sort per rank scores every row count at once\. Because the basis is fixed rather than refit, this surrogate error is an upper bound on the true error of the description it proposes\.

Step 1\. Basis and noise\.Compute the SVD ofWWand flag the rows that fit a low\-rank probe ofWWworst\. Compute a second SVD of the unflagged rows only, the same idea as a least trimmed squares fit\[[27](https://arxiv.org/html/2610.10636#bib.bib31)\]\. Its right singular vectors give the basisV^\\hat\{V\}, and the bottom of its spectrum gives the noise estimateτ^2\\hat\{\\tau\}^\{2\}\. The flagging only keeps the basis and the noise estimate clean, and has nothing to do with which rows are later stored\.

Step 2\. Sweep\.Score every shape with the surrogate error\. The columnk=0k=0is instead filled with the exact tailT⁡\(r\)T\(r\)from the first SVD, so the truncated SVD is always among the candidates with its true error\. This is what makes D\-SLR never worse than the truncated SVD at equal cost\.

Step 3\. Pick\.Read a description off the grid, either the lowest error within a parameter limit, the lowest cost that meets an error target, or the lowest score \([8](https://arxiv.org/html/2610.10636#S3.E8)\)\. By default it uses an EBIC\-style price\[[7](https://arxiv.org/html/2610.10636#bib.bib30)\]

λ=τ^2​\(log⁡\(n​m\)\+2​log⁡N\),N=\(min⁡\{n,m\}\+1\)​\(n\+1\),\\begin\{gathered\}\\lambda=\\hat\{\\tau\}^\{2\}\\bigl\(\\log\(nm\)\+2\\log N\\bigr\),\\\\ N=\(\\min\\\{n,m\\\}\+1\)\(n\+1\),\\end\{gathered\}\(13\)whereNNcounts every possible shape, so the price does not depend on how much of the grid is computed\.

Step 4\. Final fit\.Store the chosen rows verbatim and fit the rest with one truncated SVD\. This gives the exact errorE⁡\(y^\)E\(\\hat\{y\}\)used by the certificate\.

The grid and the chosen solution together cost three SVDs regardless of the grid size, and no step iterates\. Optionally, the best few shapes can be refit exactly before picking, at one SVD per refit, which corrects any misranking caused by the surrogate’s slack near the optimum \(Appendix[J](https://arxiv.org/html/2610.10636#A10)\)\.

The algorithm has two internal constants, the probe rankrprober\_\{\\mathrm\{probe\}\}and the number of flagged rowskflagk\_\{\\mathrm\{flag\}\}, which are fixed across all inputs and appear in neither the problem \([1](https://arxiv.org/html/2610.10636#S1.E1)\) nor the certificate \(Appendix[N](https://arxiv.org/html/2610.10636#A14)\)\.

## 8Experiments

We test D\-SLR on synthetic matrices built to stress each part of the method, and on the embedding tables of two LLMs\. Costs are counted in SVDs, relative to one SVD of the input matrix\. Full settings and further results are in Appendices[K](https://arxiv.org/html/2610.10636#A11)–[M](https://arxiv.org/html/2610.10636#A13)\.

### 8\.1Synthetic torture test

We compare D\-SLR with the methods closest to it in form\. Outlier Pursuit is the closest method from the literature, but it targets recovery, so we give it the most generous reconstruction treatment\. It stores only the rows it flags, its low\-rank part is refit exactly, and its solution is picked with the same score as D\-SLR, using D\-SLR’s own noise estimate\. The convex relaxation \([2](https://arxiv.org/html/2610.10636#S1.E2)\) targets reconstruction directly\. Both are tuned by a grid search over their weights\. We also test storing the heaviest rows, and the truncated SVD that D\-SLR is meant as a drop\-in for\. The synthetic test \(Appendix[K](https://arxiv.org/html/2610.10636#A11)\) has seven cases, one easy and six adversarial, each swept over its generating parameters, for 945 matrices in total\.

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 ofWW\. 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\.MethodWithin 1%Worst ratioSVDsTime \(s\)D\-SLR100%1\.012\.50\.45OP, tuned94%1\.039819\.6OP, default81%1\.60204\.1Convex relax\.78%1\.60946248Heaviest rows19%2\.860\.80\.2Truncated SVD16%7\.660\.30\.06Table[2](https://arxiv.org/html/2610.10636#S8.T2)shows that D\-SLR was within 1% of the best score in every run, at about 2\.5 SVDs and under half a second per matrix\. Outlier Pursuit with tuned weights came closest, at 94% of runs, but needed around 40 times as many SVDs and as much time, and the convex relaxation reached 78% at over four minutes per matrix\. Storing the heaviest rows is a simplified D\-SLR procedure that skips the search and simply orders the rows by size\. Without the search it has no surrogate scores, so it must check every row count it considers on the exact error, and on the synthetic matrices it is rarely competitive\. The truncated SVD was the cheapest but fell far short whenever some rows fit the shared basis poorly\.

On D\-SLR’s solution, the universal floor alone often left a lot of room, giving about 32% potential improvement in the median case\. The split floor on the other hand, of Section[6](https://arxiv.org/html/2610.10636#S6), certified D\-SLR within 1\.7% in the median case \(Table[5](https://arxiv.org/html/2610.10636#A11.T5)\)\.

### 8\.2LLM embedding tables

We use D\-SLR as a drop\-in for the truncated SVD on the embedding tables of Gemma 3 270M\[[12](https://arxiv.org/html/2610.10636#bib.bib33)\]and Llama 3\.2 1B\[[13](https://arxiv.org/html/2610.10636#bib.bib34)\]\. They are among the tallest matrices in an LLM, where rows are cheap compared with ranks \(Section[3](https://arxiv.org/html/2610.10636#S3)\)\. Internal weight matrices are closer to square, where the cost argument favours rows far less\. This is a showcase rather than a full compression pipeline\. Both methods compress the table weighted by calibration statistics from the training split of WikiText\-2\[[31](https://arxiv.org/html/2610.10636#bib.bib14),[16](https://arxiv.org/html/2610.10636#bib.bib25),[23](https://arxiv.org/html/2610.10636#bib.bib32)\], so the truncated SVD is close to the compression step of SVD\-LLM V2\[[31](https://arxiv.org/html/2610.10636#bib.bib14)\]\. All results are measured on the test split\.

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\.Figure[3](https://arxiv.org/html/2610.10636#S8.F3)shows that D\-SLR beat the truncated SVD on all three measures at every parameter count, and the same held for Llama 3\.2 1B \(Appendix[L](https://arxiv.org/html/2610.10636#A12)\)\. At half the table’s parameters it changed about ten times fewer predictions, and at 90% it changed none\.

Unlike on the synthetic matrices, storing the heaviest rows is a natural rule here, since the weighting tends to make frequent tokens heavy\. We chose its row count from 400 candidates on the exact error\. D\-SLR used only its own scores, yet matched it at low parameter counts and did slightly better at high ones\.

The best achievable error lies between D\-SLR and the lower bound\. The bound was tightest at high compression where the error is highest and it is needed the most, but loosened gradually\. However the gap to it stayed under a quarter of D\-SLR’s gain over the SVD\. On Gemma 3, Outlier Pursuit came close to D\-SLR at most limits but needed 174 SVDs and about 70 minutes, against D\-SLR’s three SVDs and 60 seconds \(Appendix[L](https://arxiv.org/html/2610.10636#A12)\)\. On three further real matrices, D\-SLR beat the truncated SVD at most parameter counts \(Appendix[M](https://arxiv.org/html/2610.10636#A13)\)\.

## 9Conclusion

We introduced D\-SLR, which stores each row verbatim or fits it with a shared low\-rank basis, never both\. The restriction is free under squared error, makes D\-SLR a drop\-in for the truncated SVD that is never worse at equal cost, and lets every rank and row count be scored in three SVDs without iteration or tuning, with a certificate that needs no assumptions on the data\. It helps most on tall matrices with rows that fit the shared basis poorly, and otherwise returns the truncated SVD\. Its default pick assumes the leftover error is noise, and its certificate loosens when many rows and ranks are affordable\. In our experiments D\-SLR matched the iterative methods at a fraction of their cost and preserved the predictions of LLM embedding tables far better than the truncated SVD\. It can also be combined with further compression such as quantisation\. Tighter floors and smarter partitions plug straight into the certificate, and better surrogates for the search would tighten the solution itself\.

## References

- \[1\]\(1976\)Singular value decomposition \(svd\) image coding\.IEEE Transactions on Communications24\(4\),pp\. 425–432\.External Links:[Document](https://dx.doi.org/10.1109/TCOM.1976.1093309)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px2.p1.1)\.
- \[2\]D\. Bertsimas, R\. Cory\-Wright, and N\. A\. G\. Johnson\(2023\)Sparse plus low rank matrix decomposition: a discrete optimization approach\.Journal of Machine Learning Research24\(267\),pp\. 1–51\.External Links:[Link](http://jmlr.org/papers/v24/21-1130.html)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px3.p1.1),[Table 1](https://arxiv.org/html/2610.10636#S2.T1.16.12.1)\.
- \[3\]L\. Birgé and P\. Massart\(2007\)Minimal penalties for gaussian model selection\.Probability Theory and Related Fields138\(1\),pp\. 33–73\.External Links:ISSN 1432\-2064,[Document](https://dx.doi.org/10.1007/s00440-006-0011-8),[Link](https://doi.org/10.1007/s00440-006-0011-8)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px4.p1.1)\.
- \[4\]M\. Brankovic, E\. Gildin, R\. L\. Gibson, and M\. E\. Everett\(2021\)A machine learning\-based seismic data compression and interpretation using a novel shifted\-matrix decomposition algorithm\.Applied Sciences11\(11\)\.External Links:[Link](https://www.mdpi.com/2076-3417/11/11/4874),ISSN 2076\-3417,[Document](https://dx.doi.org/10.3390/app11114874)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px2.p1.1)\.
- \[5\]E\. J\. Candès, X\. Li, Y\. Ma, and J\. Wright\(2011\)Robust principal component analysis?\.J\. ACM58\(3\)\.External Links:ISSN 0004\-5411,[Link](https://doi.org/10.1145/1970392.1970395),[Document](https://dx.doi.org/10.1145/1970392.1970395)Cited by:[Appendix K](https://arxiv.org/html/2610.10636#A11.p3.2),[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px1.p1.1),[Table 1](https://arxiv.org/html/2610.10636#S2.T1.16.3.1)\.
- \[6\]E\. J\. Candès and B\. Recht\(2009\)Exact matrix completion via convex optimization\.Foundations of Computational Mathematics9\(6\),pp\. 717–772\.External Links:ISSN 1615\-3383,[Document](https://dx.doi.org/10.1007/s10208-009-9045-5),[Link](https://doi.org/10.1007/s10208-009-9045-5)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px3.p1.1)\.
- \[7\]J\. Chen and Z\. Chen\(2008\)Extended bayesian information criteria for model selection with large model spaces\.Biometrika95\(3\),pp\. 759–771\.External Links:ISSN 0006\-3444,[Document](https://dx.doi.org/10.1093/biomet/asn034),[Link](https://doi.org/10.1093/biomet/asn034),https://academic\.oup\.com/biomet/article\-pdf/95/3/759/578041/asn034\.pdfCited by:[Appendix J](https://arxiv.org/html/2610.10636#A10.SS0.SSS0.Px3.p1.1),[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px4.p1.1),[§7](https://arxiv.org/html/2610.10636#S7.p4.1)\.
- \[8\]E\. Denton, W\. Zaremba, J\. Bruna, Y\. LeCun, and R\. Fergus\(2014\)Exploiting linear structure within convolutional networks for efficient evaluation\.InAdvances in Neural Information Processing Systems,NIPS’14, Vol\.27,pp\. 1269–1277\.Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px2.p1.1)\.
- \[9\]E\. Di Costanzo, N\. Kühl, J\. Marongiu, and T\. Rung\(2025\)Incremental model order reduction of smoothed\-particle hydrodynamic simulations\.International Journal for Numerical Methods in Fluids97\(12\),pp\. 1571–1594\.External Links:[Document](https://dx.doi.org/10.1002/fld.70012),[Link](https://onlinelibrary.wiley.com/doi/abs/10.1002/fld.70012),https://onlinelibrary\.wiley\.com/doi/pdf/10\.1002/fld\.70012Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px2.p1.1)\.
- \[10\]P\. Drineas, M\. W\. Mahoney, and S\. Muthukrishnan\(2008\)Relative\-error CUR matrix decompositions\.SIAM Journal on Matrix Analysis and Applications30\(2\),pp\. 844–881\.External Links:[Document](https://dx.doi.org/10.1137/07070471X),[Link](https://doi.org/10.1137/07070471X),https://doi\.org/10\.1137/07070471XCited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px4.p1.1),[Table 1](https://arxiv.org/html/2610.10636#S2.T1.16.10.1)\.
- \[11\]C\. Eckart and G\. Young\(1936\)The approximation of one matrix by another of lower rank\.Psychometrika1\(3\),pp\. 211–218\.External Links:ISSN 1860\-0980,[Document](https://dx.doi.org/10.1007/BF02288367),[Link](https://doi.org/10.1007/BF02288367)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px2.p1.1),[Table 1](https://arxiv.org/html/2610.10636#S2.T1.16.9.1),[§3](https://arxiv.org/html/2610.10636#S3.SS0.SSS0.Px1.p1.2)\.
- \[12\]Gemma Team\(2025\)Gemma 3 technical report\.arXiv preprint arXiv:2503\.19786\.Cited by:[§8\.2](https://arxiv.org/html/2610.10636#S8.SS2.p1.1)\.
- \[13\]A\. Grattafioriet al\.\(2024\)The llama 3 herd of models\.arXiv preprint arXiv:2407\.21783\.Cited by:[§8\.2](https://arxiv.org/html/2610.10636#S8.SS2.p1.1)\.
- \[14\]D\. Gross\(2011\)Recovering low\-rank matrices from few coefficients in any basis\.IEEE Transactions on Information Theory57\(3\),pp\. 1548–1566\.External Links:[Document](https://dx.doi.org/10.1109/TIT.2011.2104999)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px3.p1.1)\.
- \[15\]Grupo de Inteligencia Computacional, UPV/EHU\(2011\)Hyperspectral remote sensing scenes: Pavia University\.Note:[https://www\.ehu\.eus/ccwintco/index\.php/Hyperspectral\_Remote\_Sensing\_Scenes](https://www.ehu.eus/ccwintco/index.php/Hyperspectral_Remote_Sensing_Scenes)ROSIS sensor data courtesy of P\. Gamba, University of PaviaCited by:[Appendix M](https://arxiv.org/html/2610.10636#A13.SS0.SSS0.Px1.p1.1),[Appendix M](https://arxiv.org/html/2610.10636#A13.p1.1)\.
- \[16\]Y\. Hsu, T\. Hua, S\. Chang, Q\. Lou, Y\. Shen, and H\. Jin\(2022\)Language model compression with weighted low\-rank factorization\.InThe Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25\-29, 2022,External Links:[Link](https://openreview.net/forum?id=uPv9Y3gmAI5)Cited by:[Appendix L](https://arxiv.org/html/2610.10636#A12.p1.1),[§8\.2](https://arxiv.org/html/2610.10636#S8.SS2.p1.1)\.
- \[17\]I\. Jubran, A\. Maalouf, and D\. Feldman\(2019\)Introduction to coresets: accurate coresets\.CoRRabs/1910\.08707\.External Links:[Link](http://arxiv.org/abs/1910.08707),1910\.08707Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px4.p1.1),[Table 1](https://arxiv.org/html/2610.10636#S2.T1.16.10.1)\.
- \[18\]G\. Lerman, M\. B\. McCoy, J\. A\. Tropp, and T\. Zhang\(2015\)Robust computation of linear models by convex relaxation\.Foundations of Computational Mathematics15\(2\),pp\. 363–410\.External Links:ISSN 1615\-3383,[Document](https://dx.doi.org/10.1007/s10208-014-9221-0),[Link](https://doi.org/10.1007/s10208-014-9221-0)Cited by:[Table 1](https://arxiv.org/html/2610.10636#S2.T1.16.6.1)\.
- \[19\]Y\. Li, Y\. Yu, Q\. Zhang, C\. Liang, P\. He, W\. Chen, and T\. Zhao\(2023\)LoSparse: structured compression of large language models based on low\-rank and sparse approximation\.InProceedings of the 40th International Conference on Machine Learning,A\. Krause, E\. Brunskill, K\. Cho, B\. Engelhardt, S\. Sabato, and J\. Scarlett \(Eds\.\),Proceedings of Machine Learning Research, Vol\.202,pp\. 20336–20350\.External Links:[Link](https://proceedings.mlr.press/v202/li23ap.html)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px1.p1.1)\.
- \[20\]S\. Luo and Z\. Chen\(2013\)Extended bic for linear regression models with diverging number of relevant features and high or ultra\-high feature spaces\.Journal of Statistical Planning and Inference143\(3\),pp\. 494–504\.External Links:ISSN 0378\-3758,[Document](https://dx.doi.org/10.1016/j.jspi.2012.08.015),[Link](https://www.sciencedirect.com/science/article/pii/S0378375812002832)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px4.p1.1)\.
- \[21\]G\. Mateos and G\. B\. Giannakis\(2012\)Robust pca as bilinear decomposition with outlier\-sparsity regularization\.IEEE Transactions on Signal Processing60\(10\),pp\. 5176–5190\.External Links:[Document](https://dx.doi.org/10.1109/TSP.2012.2204986)Cited by:[Table 1](https://arxiv.org/html/2610.10636#S2.T1.16.7.1),[§4](https://arxiv.org/html/2610.10636#S4.p2.1)\.
- \[22\]D\. F\. McGivney, E\. Pierre, D\. Ma, Y\. Jiang, H\. Saybasili, V\. Gulani, and M\. A\. Griswold\(2014\)SVD compression for magnetic resonance fingerprinting in the time domain\.IEEE Transactions on Medical Imaging33\(12\),pp\. 2311–2322\.External Links:[Document](https://dx.doi.org/10.1109/TMI.2014.2337321)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px2.p1.1)\.
- \[23\]S\. Merity, C\. Xiong, J\. Bradbury, and R\. Socher\(2017\)Pointer sentinel mixture models\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=Byj72udxe)Cited by:[Appendix L](https://arxiv.org/html/2610.10636#A12.SS0.SSS0.Px1.p1.1),[§8\.2](https://arxiv.org/html/2610.10636#S8.SS2.p1.1)\.
- \[24\]P\. Netrapalli, U\. N\. Niranjan, S\. Sanghavi, A\. Anandkumar, and P\. Jain\(2014\)Provable non\-convex robust pca\.InAdvances in Neural Information Processing Systems,Z\. Ghahramani, M\. Welling, C\. Cortes, N\. Lawrence, and K\. Weinberger \(Eds\.\),Vol\.27,pp\. 1107–1115\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2014/file/3e3d6580fc108fb932e5008a94e024a3-Paper.pdf)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px3.p1.1),[Table 1](https://arxiv.org/html/2610.10636#S2.T1.16.4.1)\.
- \[25\]P\. B\. Nicol and J\. W\. Miller\(2025\)Model\-based dimensionality reduction for single\-cell rna\-seq using generalized bilinear models\.Biostatistics26\(1\),pp\. kxaf024\.External Links:ISSN 1468\-4357,[Document](https://dx.doi.org/10.1093/biostatistics/kxaf024),[Link](https://doi.org/10.1093/biostatistics/kxaf024),https://academic\.oup\.com/biostatistics/article\-pdf/26/1/kxaf024/63994958/kxaf024\.pdfCited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px2.p1.1)\.
- \[26\]J\. Rissanen\(1978\)Modeling by shortest data description\.Automatica14\(5\),pp\. 465–471\.External Links:ISSN 0005\-1098,[Document](https://dx.doi.org/10.1016/0005-1098%2878%2990005-5),[Link](https://www.sciencedirect.com/science/article/pii/0005109878900055)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px4.p1.1)\.
- \[27\]P\. J\. Rousseeuw\(1984\)Least median of squares regression\.Journal of the American Statistical Association79\(388\),pp\. 871–880\.External Links:ISSN 01621459, 1537274X,[Link](http://www.jstor.org/stable/2288718)Cited by:[§7](https://arxiv.org/html/2610.10636#S7.p2.1)\.
- \[28\]R\. Saha, N\. Sagan, V\. Srivastava, A\. J\. Goldsmith, and M\. Pilanci\(2024\)Compressing large language models using low rank and low precision decomposition\.InAdvances in Neural Information Processing Systems,A\. Globerson, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. Tomczak, and C\. Zhang \(Eds\.\),Vol\.37,pp\. 88981–89018\.External Links:[Document](https://dx.doi.org/10.52202/079017-2823),[Link](https://proceedings.neurips.cc/paper_files/paper/2024/file/a20e8451ffb07ad25282c21945ad4f19-Paper-Conference.pdf)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px2.p1.1)\.
- \[29\]A\. Trindade\(2015\)ElectricityLoadDiagrams20112014\.UCI Machine Learning Repository\.External Links:[Document](https://dx.doi.org/10.24432/C58C86)Cited by:[Appendix M](https://arxiv.org/html/2610.10636#A13.SS0.SSS0.Px1.p1.1),[Appendix M](https://arxiv.org/html/2610.10636#A13.p1.1)\.
- \[30\]S\. Uhlig, B\. Quoitin, J\. Lepropre, and S\. Balon\(2006\)Providing public intradomain traffic matrices to the research community\.SIGCOMM Comput\. Commun\. Rev\.36\(1\),pp\. 83–86\.External Links:ISSN 0146\-4833,[Link](https://doi.org/10.1145/1111322.1111341),[Document](https://dx.doi.org/10.1145/1111322.1111341)Cited by:[Appendix M](https://arxiv.org/html/2610.10636#A13.SS0.SSS0.Px1.p1.1),[Appendix M](https://arxiv.org/html/2610.10636#A13.p1.1)\.
- \[31\]X\. Wang, S\. Alam, Z\. Wan, H\. Shen, and M\. Zhang\(2025\)SVD\-LLM v2: optimizing singular value truncation for large language model compression\.InProceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 1: Long Papers\),L\. Chiruzzo, A\. Ritter, and L\. Wang \(Eds\.\),Albuquerque, New Mexico,pp\. 4287–4296\.External Links:[Link](https://aclanthology.org/2025.naacl-long.217/),[Document](https://dx.doi.org/10.18653/v1/2025.naacl-long.217),ISBN 979\-8\-89176\-189\-6Cited by:[Appendix L](https://arxiv.org/html/2610.10636#A12.p1.1),[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px2.p1.1),[§8\.2](https://arxiv.org/html/2610.10636#S8.SS2.p1.1)\.
- \[32\]M\. White, Y\. Vasyliv, K\. Beckers, M\. Martinez, P\. Balestra, C\. Parisi, C\. Augustine, G\. Bran\-Anleu, R\. Horne, L\. Pauley, G\. Bettin, T\. Marshall, and A\. Bernat\(2024\)Numerical investigation of closed\-loop geothermal systems in deep geothermal reservoirs\.Geothermics116,pp\. 102852\.External Links:ISSN 0375\-6505,[Document](https://dx.doi.org/10.1016/j.geothermics.2023.102852),[Link](https://www.sciencedirect.com/science/article/pii/S0375650523002079)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px2.p1.1)\.
- \[33\]H\. Xu, C\. Caramanis, and S\. Sanghavi\(2012\)Robust pca via outlier pursuit\.IEEE Transactions on Information Theory58\(5\),pp\. 3047–3064\.External Links:[Document](https://dx.doi.org/10.1109/TIT.2011.2173156)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px1.p1.1),[Table 1](https://arxiv.org/html/2610.10636#S2.T1.16.5.1)\.
- \[34\]J\. Zhang, J\. Erway, X\. Hu, Q\. Zhang, and R\. Plemmons\(2012\)Randomized svd methods in hyperspectral imaging\.Journal of Electrical and Computer Engineering2012\(1\),pp\. 409357\.External Links:[Document](https://dx.doi.org/10.1155/2012/409357),[Link](https://onlinelibrary.wiley.com/doi/abs/10.1155/2012/409357),https://onlinelibrary\.wiley\.com/doi/pdf/10\.1155/2012/409357Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px2.p1.1)\.
- \[35\]S\. Zhang and V\. Papyan\(2025\)OATS: outlier\-aware pruning through sparse and low rank decomposition\.InInternational Conference on Learning Representations,Y\. Yue, A\. Garg, N\. Peng, F\. Sha, and R\. Yu \(Eds\.\),pp\. 50870–50895\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2025/file/7f2fc4053a66edfa430bcdf9a6ff3b17-Paper-Conference.pdf)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px1.p1.1)\.
- \[36\]T\. Zhou and D\. Tao\(2011\)GoDec: randomized low\-rank & sparse matrix decomposition in noisy case\.InProceedings of the 28th International Conference on Machine Learning,ICML’11,Madison, WI, USA,pp\. 33–40\.External Links:ISBN 9781450306195Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px1.p1.1),[Table 1](https://arxiv.org/html/2610.10636#S2.T1.16.11.1)\.
- \[37\]Z\. Zhou, X\. Li, J\. Wright, E\. Candès, and Y\. Ma\(2010\)Stable principal component pursuit\.In2010 IEEE International Symposium on Information Theory,Vol\.,pp\. 1518–1522\.External Links:[Document](https://dx.doi.org/10.1109/ISIT.2010.5513535)Cited by:[§2](https://arxiv.org/html/2610.10636#S2.SS0.SSS0.Px1.p1.1)\.

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

## Appendix AProof of Proposition[1](https://arxiv.org/html/2610.10636#Thmtheorem1)

LetB=𝒩∖KB=\\mathcal\{N\}\\setminus K\. SinceSSis zero onBBand the squared error splits over rows,

‖W−L−S‖F2=‖WK−LK−SK‖F2\+‖WB−LB‖F2≥‖WB−LB‖F2≥T⁡\(WB,r\)=E⁡\(r,K\)\.\\\|W\-L\-S\\\|\_\{F\}^\{2\}=\\\|W\_\{K\}\-L\_\{K\}\-S\_\{K\}\\\|\_\{F\}^\{2\}\+\\\|W\_\{B\}\-L\_\{B\}\\\|\_\{F\}^\{2\}\\geq\\\|W\_\{B\}\-L\_\{B\}\\\|\_\{F\}^\{2\}\\geq T\(W\_\{B\};r\)=E\(r,K\)\.The last inequality is Eckart–Young, which applies because deleting rows cannot raise the rank, sorank⁡\(LB\)≤r\\operatorname\{rank\}\(L\_\{B\}\)\\leq r\. For the cost, whenk<nk<n,

r⁡\(n\+m\)\+k​m−C⁡\(r,k\)=r​k≥0,r\(n\+m\)\+km\-C\(r,k\)=rk\\geq 0,with equality only ifr​k=0rk=0\. Whenk=nk=nthe conventionC⁡\(r,n\)=n​mC\(r,n\)=nmmakes the differencer⁡\(n\+m\)r\(n\+m\), which is again positive wheneverr\>0r\>0\. Finally, every disjoint solution of shape\(r,k\)\(r,k\)is feasible for \([1](https://arxiv.org/html/2610.10636#S1.E1)\), so the optimum of \([1](https://arxiv.org/html/2610.10636#S1.E1)\) is at mostmin\|K\|=k⁡E⁡\(r,K\)\\min\_\{\|K\|=k\}E\(r,K\)\. By \([9](https://arxiv.org/html/2610.10636#S4.E9)\), applied with anyKKof sizekkthat contains the non\-zero rows ofSS, it is also at least that, so the two are equal\.

## Appendix BProof of Lemma[2](https://arxiv.org/html/2610.10636#Thmtheorem2)

We prove Lemmas[2](https://arxiv.org/html/2610.10636#Thmtheorem2)and[3](https://arxiv.org/html/2610.10636#Thmtheorem3)for any matrixXXin place ofWW, since Corollary[4](https://arxiv.org/html/2610.10636#Thmtheorem4)and Theorem[6](https://arxiv.org/html/2610.10636#Thmtheorem6)apply them to blocks of rows\. SetX^=S\+L\\hat\{X\}=S\+L, whereSSstores the rowsKKexactly andLLis the best rank\-rrfit of the unstored rowsBB, sorank⁡\(X^\)≤rank⁡\(S\)\+rank⁡\(L\)≤k\+r\\operatorname\{rank\}\(\\hat\{X\}\)\\leq\\operatorname\{rank\}\(S\)\+\\operatorname\{rank\}\(L\)\\leq k\+r\. By SVD optimality, no matrix of rank at mostr\+kr\+kis closer toXXthanT⁡\(X,r\+k\)T\(X;r\+k\), so‖X−X^‖F2≥T⁡\(X,r\+k\)\\\|X\-\\hat\{X\}\\\|^\{2\}\_\{F\}\\geq T\(X;r\+k\)\. Finally‖X−X^‖F2=T⁡\(XB,r\)=E⁡\(X,r,K\)\\\|X\-\\hat\{X\}\\\|^\{2\}\_\{F\}=T\(X\_\{B\};r\)=E\(X;r,K\)because theKKrows contribute no error and the residual purely exists in the approximatedBBrows\.

## Appendix CProof of Lemma[3](https://arxiv.org/html/2610.10636#Thmtheorem3)

ForV⊆ℝmV\\subseteq\\mathbb\{R\}^\{m\}withdim⁡\(V\)=r\\operatorname\{dim\}\(V\)=rand some matrixXXwith rowsxix\_\{i\}, define:

ρi​\(X,V\)=‖xi‖2−‖xi​PV‖2\\rho\_\{i\}\(X;V\)=\\\|x\_\{i\}\\\|^\{2\}\-\\\|x\_\{i\}P\_\{V\}\\\|^\{2\}\(14\)Two direct consequences that follow are:

0≤ρi​\(X,V\)≤‖xi‖2\\displaystyle 0\\leq\\rho\_\{i\}\(X;V\)\\leq\\\|x\_\{i\}\\\|^\{2\}\(15\)T⁡\(X,r\)=min⁡∑idim⁡\(V\)=r⁡ρi​\(X,V\)\\displaystyle T\(X;r\)=\\min\_\{\\operatorname\{dim\}\(V\)=r\}\\sum\_\{i\}\\rho\_\{i\}\(X;V\)\(16\)
Using these properties, for everyVVwithdim⁡\(V\)=r\\operatorname\{dim\}\(V\)=r:

∑i∉Kρi​\(V\)=∑iρi​\(V\)−∑i∈Kρi​\(V\)≥∑iρi​\(V\)−∑i∈K‖xi‖2≥∑iρi​\(V\)−R⁡\(k\)\.\\sum\_\{i\\notin K\}\\rho\_\{i\}\(V\)\\;=\\;\\sum\_\{i\}\\rho\_\{i\}\(V\)\-\\sum\_\{i\\in K\}\\rho\_\{i\}\(V\)\\;\\geq\\;\\sum\_\{i\}\\rho\_\{i\}\(V\)\-\\sum\_\{i\\in K\}\\\|x\_\{i\}\\\|^\{2\}\\;\\geq\\;\\sum\_\{i\}\\rho\_\{i\}\(V\)\-R\(k\)\.
The last step is valid because whichever rowsKKcontains, the energy they carry is at most that of thekkheaviest rows ofXX\. The subtracted termR⁡\(k\)R\(k\)is constant inVVandKKso the inequality is valid after minimising both sides:

E⁡\(r,K\)=T⁡\(XB,r\)=min⁡∑i∉KV⁡ρi​\(V\)≥min⁡∑iV⁡ρi​\(V\)−R⁡\(k\)=T⁡\(r\)−R⁡\(k\)\.E\(r,K\)=T\(X\_\{B\};r\)=\\min\_\{V\}\\sum\_\{i\\notin K\}\\rho\_\{i\}\(V\)\\;\\geq\\;\\min\_\{V\}\\sum\_\{i\}\\rho\_\{i\}\(V\)\-R\(k\)=T\(r\)\-R\(k\)\.

## Appendix DProof of Corollary[4](https://arxiv.org/html/2610.10636#Thmtheorem4)

Both Lemmas[2](https://arxiv.org/html/2610.10636#Thmtheorem2)and[3](https://arxiv.org/html/2610.10636#Thmtheorem3)bound the same quantity,E⁡\(r,K\)E\(r,K\), depending only on the shape\|K\|=k\|K\|=k, so they bound it uniformly inKKand so does the max over them\.

Item 2 follows from two facts\. The first shows that each mixed floor is itself valid, and the second that the largest of them is an endpoint\.

FixXX,rr, andkk\. Then for everyj∈\{0,…,k\}j\\in\\\{0,\\ldots,k\\\}and everyK​with​\|K\|=kK\\text\{ with \}\|K\|=k:

E⁡\(r,K\)≥T⁡\(r\+k−j\)−R⁡\(j\),\\displaystyle E\(r,K\)\\geq T\(r\+k\-j\)\-R\(j\),\(17\)max0≤j≤k⁡\[T⁡\(r\+k−j\)−R⁡\(j\)\]=max⁡\{T⁡\(r\+k\),T⁡\(r\)−R⁡\(k\)\}=E¯​\(r,k\)\.\\displaystyle\\max\_\{0\\leq j\\leq k\}\\bigl\[T\(r\+k\-j\)\-R\(j\)\\bigr\]=\\max\\bigl\\\{T\(r\+k\),T\(r\)\-R\(k\)\\bigr\\\}=\\underline\{E\}\(r,k\)\.\(18\)The first expression \([17](https://arxiv.org/html/2610.10636#A4.E17)\) states that the error is always lower bounded by the interpolating floor\. The second expression \([18](https://arxiv.org/html/2610.10636#A4.E18)\) affirms that maximising the interpolated form yields the universal error floor, meaning that the maximum is attained at an endpoint, so no interpolated value exceeds both\.

First we prove \([17](https://arxiv.org/html/2610.10636#A4.E17)\), the validity of the interpolating floor\. SplitK=K1∪K2K=K\_\{1\}\\cup K\_\{2\}disjointly with\|K1\|=j,\|K2\|=k−j\|K\_\{1\}\|=j,\\,\|K\_\{2\}\|=k\-j\. Using the same notation and steps as in the proof for Lemma[3](https://arxiv.org/html/2610.10636#Thmtheorem3), for everyrr\-dimensionalVV:

∑i∉Kρi​\(V\)=∑i∉K2ρi​\(V\)−∑i∈K1ρi​\(V\)≥∑i∉K2ρi​\(V\)−R⁡\(j\)\\sum\_\{i\\notin K\}\\rho\_\{i\}\(V\)\\;=\\;\\sum\_\{i\\notin K\_\{2\}\}\\rho\_\{i\}\(V\)\-\\sum\_\{i\\in K\_\{1\}\}\\rho\_\{i\}\(V\)\\;\\geq\\;\\sum\_\{i\\notin K\_\{2\}\}\\rho\_\{i\}\(V\)\-R\(j\)\(19\)Minimising \([19](https://arxiv.org/html/2610.10636#A4.E19)\) overVVgivesE⁡\(r,K\)≥T⁡\(X𝒩∖K2,r\)−R⁡\(j\)E\(r,K\)\\;\\geq\\;T\(X\_\{\\mathcal\{N\}\\setminus K\_\{2\}\};r\)\-R\(j\), and applying Lemma[2](https://arxiv.org/html/2610.10636#Thmtheorem2)toXXwith stored setK2K\_\{2\}givesT⁡\(X𝒩∖K2,r\)≥T⁡\(r\+k−j\)T\(X\_\{\\mathcal\{N\}\\setminus K\_\{2\}\};r\)\\;\\geq\\;T\(r\+k\-j\)\.

Now we prove \([18](https://arxiv.org/html/2610.10636#A4.E18)\), the maximum over the interpolated floor is either of its endpoints\. WriteT⁡\(r\+k−j\)−R⁡\(j\)=T⁡\(r\+k\)\+f⁡\(j\)T\(r\+k\-j\)\-R\(j\)=T\(r\+k\)\+f\(j\)where:

f⁡\(j\)=∑i=r\+k−j\+1r\+kσi​\(X\)2−R⁡\(j\)f\(j\)\\;=\\;\\sum\_\{i=r\+k\-j\+1\}^\{r\+k\}\\sigma\_\{i\}\(X\)^\{2\}\-R\(j\)Note that by constructionf⁡\(0\)=0f\(0\)=0andT⁡\(r\+k\)\+f⁡\(k\)=T⁡\(r\)−R⁡\(k\)T\(r\+k\)\+f\(k\)=T\(r\)\-R\(k\), that is the endpoints are the floors of Lemmas[2](https://arxiv.org/html/2610.10636#Thmtheorem2)and[3](https://arxiv.org/html/2610.10636#Thmtheorem3)respectively\. Seta1≥a2≥…a\_\{1\}\\geq a\_\{2\}\\geq\\ldotsas the sorted squared row norms\. Identify thatR⁡\(j\)=∑i≤jaiR\(j\)=\\sum\_\{i\\leq j\}a\_\{i\}and:

f⁡\(j\)−f⁡\(j−1\)=σr\+k−j\+12−ajf\(j\)\-f\(j\-1\)=\\sigma^\{2\}\_\{r\+k\-j\+1\}\-a\_\{j\}
Asjjrises, the singular value carries a lower index, hence it is larger in value, whileaja\_\{j\}becomes smaller\. The increments are therefore non\-decreasing,ffis convex on\{0,…,k\}\\\{0,\\ldots,k\\\}, and a convex sequence on consecutive integers is bounded by its endpoints, somaxj⁡f⁡\(j\)=max⁡\{0,f⁡\(k\)\}\\max\_\{j\}f\(j\)=\\max\\\{0,f\(k\)\\\}\.

## Appendix EProof of Theorem[5](https://arxiv.org/html/2610.10636#Thmtheorem5)

1. 1\.Lety′y^\{\\prime\}be a description with shapes′s^\{\\prime\}\. Its cost isC⁡\(s′\)C\(s^\{\\prime\}\)and its error is at leastE¯​\(s′\)\\underline\{E\}\(s^\{\\prime\}\)by the universal floor, soQ⁡\(y′\)=E⁡\(y′\)\+λ​C​\(s′\)≥Q¯​\(s′\)Q\(y^\{\\prime\}\)=E\(y^\{\\prime\}\)\+\\lambda C\(s^\{\\prime\}\)\\geq\\underline\{Q\}\(s^\{\\prime\}\)\. IfQ¯​\(s′\)≥q^\\underline\{Q\}\(s^\{\\prime\}\)\\geq\\hat\{q\}, thenQ⁡\(y′\)≥q^Q\(y^\{\\prime\}\)\\geq\\hat\{q\}, andy′y^\{\\prime\}does not beaty^\\hat\{y\}\.
2. 2\.By item[1](https://arxiv.org/html/2610.10636#A5.I1.i1), every descriptionyywith shapesshasQ⁡\(y\)≥Q¯​\(s\)≥mins′⁡Q¯​\(s′\)Q\(y\)\\geq\\underline\{Q\}\(s\)\\geq\\min\_\{s^\{\\prime\}\}\\underline\{Q\}\(s^\{\\prime\}\)\. Sominy⁡Q⁡\(y\)≥mins⁡Q¯​\(s\)\\min\_\{y\}Q\(y\)\\geq\\min\_\{s\}\\underline\{Q\}\(s\), that isq^−miny⁡Q⁡\(y\)≤qmax\\hat\{q\}\-\\min\_\{y\}Q\(y\)\\leq q\_\{\\max\}\. The gap is at least00becausey^\\hat\{y\}is itself a description\. Ifqmax=0q\_\{\\max\}=0, the gap is therefore00, andy^\\hat\{y\}is a global minimiser\.

The bounds also cover overlapping solutions of \([1](https://arxiv.org/html/2610.10636#S1.E1)\), priced atr⁡\(n\+m\)\+k​mr\(n\+m\)\+kmparameters\. By Proposition[1](https://arxiv.org/html/2610.10636#Thmtheorem1), such a solution has error at leastE⁡\(r,K\)E\(r,K\)and costs at leastC⁡\(r,k\)C\(r,k\), so its score is at leastQ⁡\(r,K\)Q\(r,K\), the score of a description\.

## Appendix FProof of Theorem[6](https://arxiv.org/html/2610.10636#Thmtheorem6)

Use the same definition ofρi​\(V\)\\rho\_\{i\}\(V\)as in \([14](https://arxiv.org/html/2610.10636#A3.E14)\)\. Set the allocation\(g1,…,gt\)​s\.t\.​gj=\|𝒫j∩K\|\(g\_\{1\},\\ldots,g\_\{t\}\)\\text\{ s\.t\. \}g\_\{j\}=\|\\mathcal\{P\}\_\{j\}\\cap K\|\. For anyrr\-dimensionalVV, the sum over the residual energyρi​\(V\)\\rho\_\{i\}\(V\)for rows inBBcan be expressed as the double sum over each row in every block𝒫j\\mathcal\{P\}\_\{j\}:

∑i∈Bρi​\(V\)=∑j=1t∑i∈𝒫j∖Kρi​\(V\)\\sum\_\{i\\in B\}\\rho\_\{i\}\(V\)=\\sum\_\{j=1\}^\{t\}\\sum\_\{i\\in\\mathcal\{P\}\_\{j\}\\setminus K\}\\rho\_\{i\}\(V\)\(20\)
If one decouples each block’s subspace from the shared subspaceVVand minimises over each one individually, the sum at the shared subspace must be at least as large:

∑j=1t∑i∈𝒫j∖Kρi​\(V\)\\displaystyle\\sum\_\{j=1\}^\{t\}\\sum\_\{i\\in\\mathcal\{P\}\_\{j\}\\setminus K\}\\rho\_\{i\}\(V\)≥∑j=1tmin⁡∑i∈𝒫j∖Kdim⁡\(V′\)=r⁡ρi​\(V′\)=∑j=1tT⁡\(W𝒫j∖K,r\)\\displaystyle\\geq\\sum\_\{j=1\}^\{t\}\\min\_\{\\operatorname\{dim\}\(V^\{\\prime\}\)=r\}\\sum\_\{i\\in\\mathcal\{P\}\_\{j\}\\setminus K\}\\rho\_\{i\}\(V^\{\\prime\}\)=\\sum\_\{j=1\}^\{t\}T\(W\_\{\\mathcal\{P\}\_\{j\}\\setminus K\};r\)=∑j=1tE⁡\(W𝒫j,r,K∩𝒫j\)≥∑j=1tE¯​\(W𝒫j,r,gj\)\\displaystyle=\\sum\_\{j=1\}^\{t\}E\(W\_\{\\mathcal\{P\}\_\{j\}\};r,K\\cap\\mathcal\{P\}\_\{j\}\)\\geq\\sum\_\{j=1\}^\{t\}\\underline\{E\}\(W\_\{\\mathcal\{P\}\_\{j\}\};r,g\_\{j\}\)
The first equality is borrowed from \([16](https://arxiv.org/html/2610.10636#A3.E16)\), and the last inequality is just the universal floor of Corollary[4](https://arxiv.org/html/2610.10636#Thmtheorem4)applied to each block in the sum individually\.

Now the right\-hand side no longer depends on the shared subspaceVV, so we can minimise the left\-hand side over all subspaces and still retain the inequality:

E⁡\(r,K\)=min⁡∑i∈Bdim⁡\(V\)=r⁡ρi​\(V\)≥∑j=1tE¯​\(W𝒫j,r,gj\)E\(r,K\)=\\min\_\{\\operatorname\{dim\}\(V\)=r\}\\sum\_\{i\\in B\}\\rho\_\{i\}\(V\)\\geq\\sum\_\{j=1\}^\{t\}\\underline\{E\}\(W\_\{\\mathcal\{P\}\_\{j\}\};r,g\_\{j\}\)
Finally because\(g1,…,gt\)\(g\_\{1\},\\ldots,g\_\{t\}\)is an element of𝒢⁡\(k\)\\mathcal\{G\}\(k\), minimising over all allocations can only lower it:

E⁡\(r,K\)≥min⁡∑j=1t\(g1′,…,gt′\)∈𝒢⁡\(k\)⁡E¯​\(W𝒫j,r,gj′\)=E¯𝒫​\(r,k\)E\(r,K\)\\geq\\min\_\{\(g\_\{1\}^\{\\prime\},\\ldots,g\_\{t\}^\{\\prime\}\)\\in\\mathcal\{G\}\(k\)\}\\sum\_\{j=1\}^\{t\}\\underline\{E\}\(W\_\{\\mathcal\{P\}\_\{j\}\};r,g\_\{j\}^\{\\prime\}\)=\\underline\{E\}\_\{\\mathcal\{P\}\}\(r,k\)

## Appendix GProof of Corollary[7](https://arxiv.org/html/2610.10636#Thmtheorem7)

Each term in the set that is being maximised over is a valid lower bound onE⁡\(r,K\)E\(r,K\)\. The first by Corollary[4](https://arxiv.org/html/2610.10636#Thmtheorem4)and the rest by Theorem[6](https://arxiv.org/html/2610.10636#Thmtheorem6)\. The latter places no condition on how each partition is created\. A maximum of finitely many valid lower bounds is also a valid lower bound, and Theorem[5](https://arxiv.org/html/2610.10636#Thmtheorem5)accepts any valid floor\.

## Appendix HProof of Proposition[8](https://arxiv.org/html/2610.10636#Thmtheorem8)

First we establish that each block’s floor is non\-increasing and convex inkk\. Write the floors of Lemmas[2](https://arxiv.org/html/2610.10636#Thmtheorem2)and[3](https://arxiv.org/html/2610.10636#Thmtheorem3)as functions ofkk,e1​\(X,k\)=T⁡\(X,r\+k\)e\_\{1\}\(X;k\)=T\(X;r\+k\)ande2​\(X,k\)=T⁡\(X,r\)−R⁡\(X,k\)e\_\{2\}\(X;k\)=T\(X;r\)\-R\(X;k\)respectively\. Their respective increments areΔ1​\(X,k\)=−σr\+k\+1​\(X\)2\\Delta\_\{1\}\(X;k\)=\-\\sigma\_\{r\+k\+1\}\(X\)^\{2\}andΔ2​\(X,k\)=−ak\+1\\Delta\_\{2\}\(X;k\)=\-a\_\{k\+1\}wherea1≥a2≥…a\_\{1\}\\geq a\_\{2\}\\geq\\ldotsare the sorted squared row norms\. BothΔ1≤0\\Delta\_\{1\}\\leq 0andΔ2≤0\\Delta\_\{2\}\\leq 0for anyXXandkk, so as a sequence inkkthey both are non\-increasing, while their respective sequences of increments are non\-decreasing as the singular values and squared row norms are sorted\. Thereforee1e\_\{1\}ande2e\_\{2\}are non\-increasing and convex\. Furthermore a pointwise max of non\-increasing, convex sequences, together with the point 0, is itself non\-increasing and convex\.

#### ≥\\geq

Any allocation\(g1,…,gt\)∈𝒢⁡\(k\)\(g\_\{1\},\\ldots,g\_\{t\}\)\\in\\mathcal\{G\}\(k\)gives the total∑jE¯​\(W𝒫j,r,0\)\+∑j∑i≤gjδj​\(i\)\\sum\_\{j\}\\underline\{E\}\(W\_\{\\mathcal\{P\}\_\{j\}\};r,0\)\+\\sum\_\{j\}\\sum\_\{i\\leq g\_\{j\}\}\\delta\_\{j\}\(i\)\. The double sum pickskkdistinct increments, so it is at least the sum of thekksmallest\. This direction does not use convexity, so the sorted value is a valid floor for any blocks\.

#### ≤\\leq

Take thekksmallest increments, breaking ties in favour of the smallerii, then the smallerjj\. Ifδj​\(i\)\\delta\_\{j\}\(i\)is picked butδj​\(i−1\)\\delta\_\{j\}\(i\-1\)is not, thenδj​\(i−1\)<δj​\(i\)\\delta\_\{j\}\(i\-1\)<\\delta\_\{j\}\(i\)is impossible because the smaller increment would have been picked first,δj​\(i−1\)\>δj​\(i\)\\delta\_\{j\}\(i\-1\)\>\\delta\_\{j\}\(i\)is impossible by convexity, and equality is excluded by the tie\-breaking rule\. So the increments picked from blockjjare its firstgjg\_\{j\}, withgj≤\|𝒫j\|g\_\{j\}\\leq\|\\mathcal\{P\}\_\{j\}\|because the block has no further increments\. This is an allocation in𝒢⁡\(k\)\\mathcal\{G\}\(k\), and its total is exactly the right\-hand side\.

## Appendix IHow to best partition the matrix

Theorem[6](https://arxiv.org/html/2610.10636#Thmtheorem6)holds for any partition, so which partitions give a tight floor? Each of the two floors can be helped in its own way\.

#### Spectral floor\.

Split the rows intottblocks that each look like a smaller copy ofWW, so each block holds about a1/t1/tshare of its spectrum\. If thekkstored rows are spread evenly, each block concedes onlyk/tk/textra directions instead ofkk, and

∑jT⁡\(W𝒫j,r\+k/t\)≈T⁡\(W,r\+k/t\)≥T⁡\(W,r\+k\)\.\\sum\_\{j\}T\\bigl\(W\_\{\\mathcal\{P\}\_\{j\}\};r\+k/t\\bigr\)\\approx T\(W;r\+k/t\)\\geq T\(W;r\+k\)\.The split floor takes the worst spread, not the even one\. But each block’s floor is convex in its number of stored rows \(proof of Proposition[8](https://arxiv.org/html/2610.10636#Thmtheorem8)\), so when the blocks are alike the even spread is the worst\. A block also needs enough rows\. With few rows it has few singular values, and its floor reaches zero after only a few ranks or stored rows\.

#### Row\-energy floor\.

The row floorT⁡\(r\)−R⁡\(k\)T\(r\)\-R\(k\)is zero as soon as thekkheaviest rows hold more energy than the tail\. Putting the heaviest rows in a block of their own confines this\. That block’s floor drops to zero, but the other blocks only subtract their own lighter rows\.

#### What we use\.

Sorting the rows by norm and dealing them round\-robin into blocks gives each block a similar mix of heavy and light rows\. We do this starting witht=⌊n/\(0\.8​m\)⌋t=\\lfloor n/\(0\.8m\)\\rfloorblocks and halvingttup to four times\. A hybrid variant serves both floors\. The sorted rows are cut into two or three strata of growing size, and each stratum is dealt round\-robin into blocks of about0\.8​m0\.8mor1\.5​m1\.5mrows\. The heaviest rows then share a small block, and the blocks within each stratum stay alike\. All experiments use these partitions together with the unsplit floor\. These are heuristics, but a poor partition costs nothing, because Corollary[7](https://arxiv.org/html/2610.10636#Thmtheorem7)always keeps the unsplit floor\. Figure[4](https://arxiv.org/html/2610.10636#A9.F4)shows the effect on a small matrix\.

![Refer to caption](https://arxiv.org/html/2610.10636v1/fig_certificate_demo.png)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](https://arxiv.org/html/2610.10636#S6), which closes most of the open shapes\. Each shape\(r,k\)\(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\.

## Appendix JAlgorithm details

#### Defaults\.

The probe rank isrprobe=min⁡\{15,min⁡\{n,m\}−1\}r\_\{\\mathrm\{probe\}\}=\\min\\\{15,\\min\\\{n,m\\\}\-1\\\}, and half of the rows are flagged,kflag=⌊n/2⌋k\_\{\\mathrm\{flag\}\}=\\lfloor n/2\\rfloor\. Flagging is deliberately over\-inclusive, because a flagged row is only left out of the basis fit and can still be stored or approximated like any other\.

#### Noise estimate\.

τ^2\\hat\{\\tau\}^\{2\}is the mean of the bottom half of the squared singular values of the unflagged block, divided by its larger dimension\. On pure noise the bottom of the spectrum sits below the average, so this raw estimate is low by a factor that depends only on the block’s aspect ratio\. We compute that factor once from the Marchenko–Pastur law and divide it out\.

#### Price\.

The price \([13](https://arxiv.org/html/2610.10636#S7.E13)\) is adapted from EBIC\[[7](https://arxiv.org/html/2610.10636#bib.bib30)\]rather than taken from it\. Like BIC, it chargeslog⁡\(n​m\)\\log\(nm\)per parameter, for then​mnmobserved entries\. EBIC adds twice the log of the number of candidate models of the same size, once per model\. Bounding that number bypνp^\{\\nu\}forν\\nuparameters drawn fromppcandidates turns it into2​log⁡p2\\log pper parameter, and we use the number of shapesNNforpp\. Both terms are multiplied byτ^2\\hat\{\\tau\}^\{2\}to put them in squared\-error units\. This is a heuristic choice, and any other price can be used, because the certificate holds for everyλ\\lambda\.

#### Shortlist verification\.

With verification enabled, the shortlist by default holds the eight best\-scoring shapes withk\>0k\>0, the best shape withk=0k=0, plus the best row count for each of four ranks on a geometric ladder\. Each shape withk\>0k\>0is refit exactly twice, once on the rows the sweep proposes and once on its heaviest rows, at one SVD of the unstored block each, and the better of the two is kept\. The shortlist is then re\-ranked on the exact score\. Shapes withk=0k=0are already exact and cost nothing\.

#### Other candidates\.

Storing the heaviest rows is a simplified D\-SLR procedure that skips the search and simply orders the rows by size, so the certificate applies to its solutions unchanged\. Without the search it has no surrogate scores, so on its own it must check every row count it considers on the exact error, and in our synthetic tests it is rarely competitive \(Table[2](https://arxiv.org/html/2610.10636#S8.T2)\)\.

## Appendix KSynthetic torture test

All timings in this paper come from one consumer workstation with an AMD Threadripper 2950X processor and 128 GB of memory, with the same BLAS thread settings for every method and experiment\. A GPU computed only the calibration statistics and held\-out measures of the LLMs, which no timing includes\.

Two torture tests are run, one that compares all methods, and one that only compares the faster methods\. The first test is more varied overall but was restricted in certain aspects to save time\. The second test explores what was left out\.

For the main test used in Section[8\.1](https://arxiv.org/html/2610.10636#S8.SS1)the generated matrix follows a common recipe that is then changed\. It is a rank\-10 background plus some heavy rows and noise, at4000×2004000\\times 200\. The background is a product of Gaussian factors with entries of unit variance, the heavy rows are Gaussian rows scaled up and placed at random, and the noise is Gaussian\. The core grid varies the share of heavy rows \(2, 10 and 20%\), the noise level per entry \(0\.05, 0\.1 and 0\.2\) and how much heavier the heavy rows are \(1\.5, 4 and 16 times\), for 27 settings\. Each case changes one thing about this recipe\.

- •Plain: the recipe as is\.
- •Many heavy rows: 20, 30 and 40% of the rows are heavy\.
- •Mixed heavy sizes: each heavy row gets its own size, between 0\.25 and 32 times the base size\.
- •Aligned heavy rows: the heavy rows all point in one direction\.
- •Uneven background: each background row is scaled by a random weight from a Pareto distribution with shape 1\.5, so the background rows have very uneven norms\.
- •Heavy\-tailed noise: the noise follows a Studentttdistribution with 3 degrees of freedom\.
- •Partly heavy rows: only 30% of each heavy row’s entries are large\.

With five seeds this gives 945 matrices\. Every method returns a description of the formW^=S\+L\\hat\{W\}=S\+Land picks it with the EBIC score \([13](https://arxiv.org/html/2610.10636#S7.E13)\) at D\-SLR’s noise estimate, since none of the baselines has a reliable estimate of its own\. Each pick is then scored with the true noise level, which is known here\. Outlier Pursuit flags the rows whose sparse part exceeds3​τ^​m3\\hat\{\\tau\}\\sqrt\{m\}, withτ^2\\hat\{\\tau\}^\{2\}D\-SLR’s noise estimate\. For each weight, the flagged rows are stored and the rest are refit exactly at every rank\. Its default weight is the universal weight of PCP\[[5](https://arxiv.org/html/2610.10636#bib.bib1)\], rescaled bym\\sqrt\{m\}to act on row norms, givingm/max⁡\{n,m\}\\sqrt\{m\}/\\sqrt\{\\max\\\{n,m\\\}\}\. The convex relaxation is solved by ADMM, refit and picked in the same way, and because of its cost was run on two of the five seeds\. It did worse than Outlier Pursuit, likely because it must select both the rows and the rank through its penalties, while Outlier Pursuit has its rank picked by the same score as D\-SLR\. Storing the heaviest rows is refit exactly at every rank, on a grid of 48 row counts\. The time of Outlier Pursuit at its default weight is estimated from that weight’s share of the iterations in the tuned run\. The best score on a matrix is the lowest score of any method run on it\.

The second test aims to target parameters that could affect D\-SLR more than others\. A smaller version of the first test was run but now varying the matrix shape and background rank\. Table[4](https://arxiv.org/html/2610.10636#A11.T4)repeats the comparison at three shapes \(2000×2002000\\times 200,4000×2004000\\times 200and4000×4004000\\times 400\) and eight background ranks \(1, 4, 8, 12, 16, 32, 64 and 96\), at each case’s middle share of heavy rows and five seeds, for 840 matrices\. Only the methods cheap enough to run on every matrix are included\. D\-SLR’s results held in similar fashion to the first test\.

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](https://arxiv.org/html/2610.10636#S8.T2)\.Verifiedadds the shortlist refits of Appendix[J](https://arxiv.org/html/2610.10636#A10)\.Defaultuses the method’s default weight instead of a grid search\.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](https://arxiv.org/html/2610.10636#A11.T3)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](https://arxiv.org/html/2610.10636#S8.T2)\.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](https://arxiv.org/html/2610.10636#Thmtheorem5)with the given floor, as a percentage of that score\. Over the 945 matrices of Table[3](https://arxiv.org/html/2610.10636#A11.T3)\.
## Appendix LLLM embedding tables

The embedding tables are262144×640262144\\times 640for Gemma 3 270M and128256×2048128256\\times 2048for Llama 3\.2 1B, about 63% and 21% of each model’s parameters\. Both models share this table between the input embedding and the output head\. The tables are weighted using the forward activations and the curvature of the output loss, as in\[[31](https://arxiv.org/html/2610.10636#bib.bib14),[16](https://arxiv.org/html/2610.10636#bib.bib25)\], so that the reconstruction error better approximates the downstream error \(Appendix[O](https://arxiv.org/html/2610.10636#A15)\)\. Calibration uses about 33k tokens of the train split of WikiText\-2 for Gemma 3 and 130k for Llama 3\.2, and evaluation uses about 16k tokens of its test split\. Both methods see the same weighted table, and each parameter limit is a share of the table’s parameters\.

The held\-out loss is the mean cross\-entropy per token in nats, and its increase is measured against the uncompressed model\. A prediction changes when the model’s most likely next token differs from that of the uncompressed model\.

The D\-SLR points are the standard algorithm of Section[7](https://arxiv.org/html/2610.10636#S7), without shortlist verification\. Figure[5](https://arxiv.org/html/2610.10636#A12.F5)shows Llama 3\.2 1B, and Figure[6](https://arxiv.org/html/2610.10636#A12.F6)adds Outlier Pursuit to Gemma 3\. Outlier Pursuit was given D\-SLR’s noise estimate and run at six weights plus the empty row set, with at most 50 iterations each, where the torture test never needed more than 26\. Its description at each limit is the lowest exact error among all its candidates within that limit\.

Figure 5:The embedding table of Llama 3\.2 1B, as in Figure[3](https://arxiv.org/html/2610.10636#S8.F3)\. D\-SLR again beats the truncated SVD on all three measures at every parameter count\.Figure 6:Figure[3](https://arxiv.org/html/2610.10636#S8.F3)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\.#### Assets\.

Gemma 3 is released under the Gemma Terms of Use and Llama 3\.2 under the Llama 3\.2 Community License\. WikiText\-2 is released under CC BY\-SA\[[23](https://arxiv.org/html/2610.10636#bib.bib32)\]\.

## Appendix MFurther real\-world matrices

We also used D\-SLR as a drop\-in for the truncated SVD on three real matrices with no model in the loop, so the error is plain squared error\. PaviaU is a hyperspectral image of Pavia University\[[15](https://arxiv.org/html/2610.10636#bib.bib37)\], with one row per pixel and one column per spectral band, giving a207400×103207400\\times 103matrix that we centre per band\. GEANT holds the traffic of a European research network\[[30](https://arxiv.org/html/2610.10636#bib.bib36)\], with one row per 15\-minute snapshot and one column per origin\-destination flow, giving a10769×52910769\\times 529matrix that we use as is\. The electricity data holds the load of Portuguese customers every 15 minutes\[[29](https://arxiv.org/html/2610.10636#bib.bib35)\]\. We keep 2012 to 2014 and the 321 customers active from the start, centre and scale each customer, and cut the series into daily load curves, the usual unit in load\-profile analysis\. This gives a351816×96351816\\times 96matrix with one row per customer and day\. A stored row is a pixel, snapshot or customer\-day kept exactly, and neither method is charged for the means removed by centring\. The lower bound uses the partitions of Appendix[I](https://arxiv.org/html/2610.10636#A9)\.

Figure[7](https://arxiv.org/html/2610.10636#A13.F7)shows that D\-SLR matched or beat the truncated SVD at every limit on all three matrices\. On PaviaU it gained from 3% of the parameters upward\. PaviaU and GEANT are close to low rank, so each added rank removes much of the remaining error and it is difficult for a few stored rows to do better, which keeps their gains modest\. On GEANT D\-SLR gained at the tightest limits, where a few snapshots fit the shared basis poorly and a stored row costs about a twentieth of a rank\. From 5% to 80% it returned the truncated SVD, as did the EBIC pick, and at 90% it stored rows again\. The lower bound shows that room remained there, and the shortlist refits of Appendix[J](https://arxiv.org/html/2610.10636#A10)found it, at about 27 SVDs per limit instead of one\. On the electricity data D\-SLR beat the truncated SVD at every limit, by storing individual customer\-days that fit the typical daily shapes poorly, and the gain grew with the parameter count\. Put another way, to reach the truncated SVD’s error D\-SLR needed up to a quarter fewer parameters on PaviaU and on the electricity data, and up to half on GEANT at its tightest limits\. On all three matrices the lower bound fades at the most generous limits, where many rows and ranks are affordable and the floors loosen\.

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\.#### Assets\.

The electricity data is released under CC BY 4\.0\[[29](https://arxiv.org/html/2610.10636#bib.bib35)\]\. The PaviaU scene\[[15](https://arxiv.org/html/2610.10636#bib.bib37)\]and the GEANT traffic matrices\[[30](https://arxiv.org/html/2610.10636#bib.bib36)\]are distributed by their authors for research use, with no stated license\. No data is redistributed with this paper\.

## Appendix NSensitivity torprober\_\{\\mathrm\{probe\}\}andkflagk\_\{\\mathrm\{flag\}\}

Unlike the weights in \([2](https://arxiv.org/html/2610.10636#S1.E2)\), the constantsrprober\_\{\\mathrm\{probe\}\}andkflagk\_\{\\mathrm\{flag\}\}appear in neither the problem \([1](https://arxiv.org/html/2610.10636#S1.E1)\) nor the certificate, which holds whatever price is used\. They only affect which solution is proposed and the noise estimateτ^2\\hat\{\\tau\}^\{2\}\. And unlike a penalty weight,τ2\\tau^\{2\}has a true value in the data that the estimate can be checked against\.

We ran D\-SLR at every pair ofrprobe∈\{0,1,2,4,8,15,30,60,100\}r\_\{\\mathrm\{probe\}\}\\in\\\{0,1,2,4,8,15,30,60,100\\\}andkflag/n∈\{0,0\.02,0\.05,0\.1,0\.2,0\.3,0\.5,0\.7,0\.9\}k\_\{\\mathrm\{flag\}\}/n\\in\\\{0,0\.02,0\.05,0\.1,0\.2,0\.3,0\.5,0\.7,0\.9\\\}, on the seven torture\-test cases at three settings each\. These are the middle of the core grid, its hardest corner, with heavy rows only 1\.5 times the background at the highest noise, and a background of rank 32, more than the default probe rank\. With three seeds this gives 63 matrices of size4000×2004000\\times 200\. Each result is scored with the true noise level and compared with the defaults on the same matrix\.

Figure[8](https://arxiv.org/html/2610.10636#A14.F8)shows that the probe rank barely mattered\. From 0 to 100 no matrix scored more than 1% worse than at the defaults, including those whose background has more directions than the probe\. The flagged share mattered only when it was too small\. Every setting more than 5% worse than the defaults flagged no more rows than the matrix had heavy rows\. The extra heavy rows then entered the basis fit, the noise estimate and with it the price came out many times too high, and D\-SLR stored too little\. At the default probe rank, from 30% of the rows upward no matrix scored more than 3% worse\. The default flags half the rows, so it can only fail when more than half the rows fit the shared basis poorly, and then the matrix is no longer a low\-rank background with some rows apart\. On every matrix the defaults were also within 1% of the best setting on the grid\.

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:rprober\_\{\\mathrm\{probe\}\}atkflag=n/2k\_\{\\mathrm\{flag\}\}=n/2\.Right:kflagk\_\{\\mathrm\{flag\}\}atrprobe=15r\_\{\\mathrm\{probe\}\}=15\.
## Appendix OWeighted inputs

D\-SLR minimises squared error, but some uses call for a weighted error\. We support weights that scale each row and a Gram matrix that mixes the columns, and minimise

∑iwi​\(xi−x^i\)​G​\(xi−x^i\)⊤\\sum\_\{i\}w\_\{i\}\\,\(x\_\{i\}\-\\hat\{x\}\_\{i\}\)\\,G\\,\(x\_\{i\}\-\\hat\{x\}\_\{i\}\)^\{\\top\}over the rowsxix\_\{i\}ofWW, withwi\>0w\_\{i\}\>0andGGpositive semidefinite\. We add a small ridgeϵ​I\\epsilon ItoGGand floor the weights at10−610^\{\-6\}of their largest value, so that both maps below can be inverted, and minimise the objective withG\+ϵ​IG\+\\epsilon Iin place ofGG\. WritingG\+ϵ​I=H​H⊤G\+\\epsilon I=HH^\{\\top\}withHHits square Cholesky factor, this is the plain squared error ofM=diag⁡\(w\)​W​HM=\\operatorname\{diag\}\(\\sqrt\{w\}\)\\,WH, so D\-SLR runs unchanged onMMand its solution is mapped back\. Both maps act within a row or on the right, never across rows, so a stored row ofMMis a stored row ofWWand still costsmmparameters\. A full covariance across rows would mix them, and a stored row would no longer be a row ofWW\. The stored rows are copied fromWWitself, so they stay exact, and the low\-rank part is mapped back by undoing the row scale andHH\. The floors and the certificate hold unchanged onMM, so they bound this weighted error, which exceeds the error underGGalone byϵ​∑iwi​‖xi−x^i‖2\\epsilon\\sum\_\{i\}w\_\{i\}\\\|x\_\{i\}\-\\hat\{x\}\_\{i\}\\\|^\{2\}\.

For the LLM tables,GGis the mean outer product of the hidden states entering the output head, andwiw\_\{i\}the mean ofpi​\(1−pi\)p\_\{i\}\(1\-p\_\{i\}\), wherepip\_\{i\}is the predicted probability of tokenii\. With these values, the weighted sum is just the second\-order approximation of the cross\-entropy loss, when dropping the first\-order term\. This keeps only the diagonal of the curvature across tokens and treats it as independent of the hidden states, so it is an approximation\. The embedding table is shared between input and output and the decomposed table is used to replace both, and the held\-out loss measures the result\.