Many large learning problems reduce to repeated multiplications by a data matrix too big to hold in memory. Fitting a ridge-regression readout over hundreds of millions of robot camera frames, or extracting the leading principal components of a video corpus, are two examples. Iterative solvers such as conjugate gradient (CG) and Lanczos need only one thing from the matrix: its product with a vector. They never need the matrix stored explicitly, which is what "matrix-free" means. When the data sits on disk, though, every iteration becomes a full sweep over terabytes. The cost of the solve is then the number of bytes read per iteration times the number of iterations, and arithmetic barely matters.
Time-ordered data such as video, robot trajectories, and sensor streams is highly repetitive from one frame to the next. Video codecs exploit this by storing occasional "keyframes" plus small differences ("residuals"). We propose to store a time-ordered data matrix in that keyframe-plus-residual form inside a memory-mapped file and to compute every matrix-vector product directly on the compressed form, without reconstructing the frames. The product splits exactly into a cheap term over the few keyframes and a sparse term over the residuals. Bytes read and arithmetic per iteration both shrink by the redundancy ratio of the data. Because the decomposition is exact, the solver still converges to the original problem's solution, not to that of a subsampled or lossily decoded proxy.
Core Claim
Let $X \in \mathbb{R}^{N \times d}$ be a time-ordered data matrix: one row per frame, $N$ frames, $d$ features such as pixels or sensor channels. Group the rows into blocks of roughly $g$ consecutive frames. Write
$$X = P K + R,$$
where $K \in \mathbb{R}^{(N/g) \times d}$ holds the keyframe rows. $P \in \mathbb{R}^{N \times (N/g)}$ is a very sparse matrix that says which keyframe, or which interpolation weights between two neighbouring keyframes, predicts each frame. $R$ is the sparse residual left over. Both products a Krylov solver needs then factor exactly:
$$Xv = P(Kv) + Rv, \qquad X^\top u = K^\top(P^\top u) + R^\top u.$$
Each costs one read of $K$ plus one read of the nonzeros of $R$. With $s$ bytes per value, the bytes read per iteration drop from $Nds$ to roughly $(N/g)ds + \mathrm{nnz}(R)(s + \text{index bytes})$. The multiply count drops in the same proportion. Our claim is that for real robot and video data this ratio is large, and that a solver organised around it beats two alternatives in wall-clock time-to-tolerance on disk-resident problems. The first is streaming the raw matrix. The second, more serious one, is streaming a conventionally compressed matrix and decoding it on every pass. We also claim the speedup is predictable from a single measured quantity, the compressed size per pass.
Where This Sits
Three lines of work each contain one piece of this, and none combines them. Matrix-free iterative methods supply the solver side. Low-Precision Arithmetic for Fast Gaussian Processes replaces Cholesky with preconditioned CG to fit exact Gaussian processes on 1.8 million points. GCGE solves large eigenproblems with block inverse-power iterations. The implicit Runge-Kutta preconditioners of Fast Solution of Fully Implicit Runge-Kutta and Discontinuous Galerkin in Time couple time stages algebraically. All of them assume the operator's data is in memory, and none treats redundancy between time slices as a storage-level resource. We reuse their solvers unchanged and change only how the operator's data is laid out and touched.
Compressed-domain computation supplies the idea of not decoding. Compressed Video Action Recognition trains a classifier directly on I-frames, motion vectors and accumulated residuals, and reports 90.4% on UCF-101 at 4.6 times the speed of Res3D. That work performs a single learned forward pass, not repeated exact linear-algebra sweeps. Its residual accumulation is a source of drift, whereas our decomposition is exact by construction. KeyWorld shows that keyframes chosen adaptively along a trajectory with the Ramer–Douglas–Peucker simplification beat frame-by-frame treatment. We borrow that adaptive keyframe selection as one way to choose $P$.
Memory-mapped data systems supply the storage substrate and the closest competitor. Robo-DM pairs video codecs with mmap caching and reports up to 70 times smaller robot datasets and up to 50 times faster loading than LeRobot. TorchRL offers memory-mapped trajectory buffers. Chunked stores like those behind TerraMesh and SpatialData make lazy loading of huge arrays practical. All of them decode data back to dense tensors before computing, and they are built for one pass per training epoch. An iterative solver sweeps the data dozens or hundreds of times, so per-pass decode cost and the operating system's access-unaware page caching hurt far more. We place keyframes and residuals of each block contiguously, in the order the product visits them. Each pass then becomes a single sequential sweep, which avoids the page-thrashing failure mode noted for strided access.
Research Program
The first component is an encoder. It converts a time-ordered array into the triple $(K, P, R)$ and writes it to a chunked memory-mapped file with one chunk per block. Each chunk holds that block's keyframe rows, the small coefficient block of $P$, and the residual in compressed sparse row format. We will compare three ways of choosing keyframes. The first uses fixed spacing $g$. The second chooses keyframes adaptively in the style of KeyWorld, splitting wherever the residual would become dense. The third allows "bidirectional" rows predicted by interpolating two keyframes, analogous to B-frames.
The residual can be stored losslessly, which gives exact products. It can also be thresholded at magnitude $\tau$, which perturbs $X$ by a matrix $E$ with known spectral-norm bound. In the thresholded case, standard least-squares perturbation theory bounds the relative solution error by roughly the condition number times $\|E\|_2 / \|X\|_2$. The encoder can therefore pick $\tau$ to meet a target accuracy rather than a target size. We treat this lossy mode as a separate, clearly labelled variant.
The second component is an out-of-core product kernel that streams chunks sequentially with read-ahead hints. Within a pass it computes $Kv$ for every block, applies the tiny $P$ blocks, and adds $Rv$. It supports blocks of several vectors at once, so block Lanczos and multi-right-hand-side CG amortise each pass over many vectors. Following the low-precision GP work, we will test keyframe products in half precision while keeping residual accumulation and the Krylov recurrences in single precision with re-orthogonalisation. That paper shows that low precision without these safeguards loses orthogonality.
The third component is an analysis of when the method wins. Time-to-solution should be roughly (iterations) × max(bytes per pass / disk bandwidth, flops per pass / compute rate), plus decode time for the baselines. We will measure each term separately, so that any speedup can be attributed to fewer bytes, fewer multiplies, or the absence of decoding.
Baselines
The naive reference stores the raw matrix as uncompressed chunks in a memory-mapped Zarr-style store laid out in time order. It runs the same CG and block Lanczos code, so each iteration is one sequential sweep. This is the "do nothing" point. It is already better than random-access mmap, so beating it measures the value of exploiting redundancy rather than the value of a sensible layout.
The strongest competitor is codec-compressed streaming in the style of Robo-DM. The same frames are stored with a lossless setting of a standard video or general-purpose array codec, decoded block by block on every pass, and multiplied densely. This baseline gets most of the I/O reduction for free, so it is the real threat. It will run with the same storage device, the same CPU and GPU budget, multi-threaded decode, and codec settings tuned for decode speed with a tuning budget equal to the one we spend on keyframe selection. Robo-DM reports up to 70 times dataset-size reduction, up to 50 times faster loading than LeRobot, and a 2.6% validation-loss increase under lossy compression. Those are single-pass loading figures. For iterative-solver time-to-solution on disk-resident data, no reported result was found on Lacuna for any method, so we will establish the number ourselves. Beating this baseline means a lower wall-clock time to reach a relative residual of $10^{-6}$ at matched exactness: lossless against lossless, or equal measured solution error in the lossy variants.
The oracle is the same solve run fully in memory on a large-memory node, which lower-bounds achievable time for the naive arithmetic. A frame-subsampling baseline keeps only the keyframes and solves the smaller problem. It is reported by its solution error against the full solve as well as by speed.
The key ablation is decode-then-multiply on our own format. We store exactly the $(K, P, R)$ chunks, reconstruct dense rows in memory, and multiply densely. This isolates the contribution of computing in the compressed domain from the contribution of the encoding itself. A second ablation replaces adaptive keyframes with fixed spacing.
Why not just…?
Why not just compress with an ordinary codec and decode every pass? This is the alternative most likely to match us. On fast local disks with abundant CPU cores, decoding may outrun the disk and recover most of the byte savings. Our method has two structural advantages: it skips decode entirely, and it cuts arithmetic as well as bytes, because $Kv$ is computed once per keyframe rather than once per frame. Whether those advantages matter is an empirical question. The codec baseline and the decode-then-multiply ablation settle it directly. If our method is not at least 1.5 times faster than both on GPU-backed solves, where dense multiplication is cheap and decode is the bottleneck, we will conclude that the format matters and the compressed-domain arithmetic does not, and we will report that.
Why not just subsample frames uniformly or keep only keyframes? Subsampling answers a different question. ClipBERT shows that sparse sampling is enough for training video-language models end to end, but a least-squares readout or a principal subspace computed on a subset is a different estimator. We will report how far its solution and leading eigenvectors land from the full-data answer. The trade-off is made explicit by plotting time against solution error for subsampling and for our thresholded variant on the same axes.
Why not just buy enough memory, or sketch the data in one pass? Putting everything in memory is the oracle baseline. It shows how much of the gap to raw arithmetic we close, and the TerraMesh raw size of 36.2 TB indicates that realistic corpora outgrow single nodes. Randomised sketching, meaning compressing $X$ with a random projection in one pass and then solving or preconditioning on the small sketch, is a genuine threat for moderate-accuracy least squares. It does not remove the passes needed for high accuracy, and it does not help eigenvector refinement. It also composes with our method, since the sketching pass is itself a product $X^\top u$ that benefits from the delta form. We will run sketch-and-precondition CG on both raw and delta storage to show whether the gains add.
Why not just warm-start each solve from the previous solution? Warm starts reduce the number of iterations, while we reduce the cost of each one. The two are orthogonal, and every method in the comparison gets the same warm starts, so neither can take credit for the other.
Proposed Experiments
The workloads are two problems that are standard, exactly specified, and sweep the data many times. The first is ridge regression from raw downsampled camera pixels to robot actions, solved by CG on the normal equations. The second is the top 64 principal components by block Lanczos. Both run on time-ordered pixel matrices built from Open-X-Embodiment and RT-1 trajectories, LIBERO episodes, and UCF-101 videos. SkyTimelapse serves as a deliberate stress case: its whole-frame continuous motion should make residuals dense, so the method ought to gain little. Resolution and frame counts will be chosen to give matrices from about 0.5 TB to 10 TB on disk, against a node with substantially less memory. We will run on both local NVMe and network storage to vary the ratio of bandwidth to compute.
Metrics are wall-clock time to a relative residual of $10^{-6}$ for CG, and time to subspace angle below $10^{-4}$ against the in-memory reference for Lanczos. We also report bytes read per pass, flops per pass, and peak memory. Lossy variants additionally report solution error and the downstream action-prediction error of the ridge readout.
The decisive checks are three. First, measured speedup over naive streaming should track the measured compression ratio per pass. If it does not, the product kernel, not the data, is the bottleneck. Second, our method must beat the codec baseline and the decode-then-multiply ablation at equal exactness on most datasets; otherwise the central claim fails. Third, on SkyTimelapse the advantage should collapse toward one, which confirms the gain comes from temporal redundancy rather than incidental engineering. Lossless runs must also reproduce the in-memory solution to solver tolerance, and half-precision keyframe products must not increase iteration counts beyond what re-orthogonalisation recovers.
References
- Low-Precision Arithmetic for Fast Gaussian Processes
- GCGE: a package for solving large scale eigenvalue problems by parallel block damping inverse power method
- Fast Solution of Fully Implicit Runge-Kutta and Discontinuous Galerkin in Time for Numerical PDEs, Part I: the Linear Setting
- Compressed Video Action Recognition
- KeyWorld: Key Frame Reasoning Enables Effective and Efficient World Models
- Robo-DM: Data Management for Large Robot Datasets
- TorchRL: A data-driven decision-making library for PyTorch
- TerraMesh: A Planetary Mosaic of Multimodal Earth Observation Data
- SpatialData: an open and universal data framework for spatial omics
- Less Is More: ClipBERT for Video-and-Language Learning via Sparse Sampling