Research map / Architectures and efficiency / RNNs and normalization
Fast Updating Truncated SVD for Representation Learning with Sparse Matrices
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a fast method for updating a rank-k truncated SVD of sparse, evolving matrices by orthogonalizing augmented matrices in a sparse-vector-minus-low-rank-combination inner product space (SV-LCOV) and using an extended decomposition that avoids projecting all singular vectors.
Problem
Keeping truncated SVD-based representations up to date as large sparse data matrices evolve (row/column additions and low-rank weight updates) is inefficient, because existing Rayleigh-Ritz update methods densify the augmented matrix and project all singular vectors.
Approach
Represent augmented-matrix columns as SV-LCOV tuples (sparse vector, low-dimensional coefficient vector) whose inner product is isometric to the augmented space, so Gram-Schmidt and GKL/RPI basis approximations run in time dependent on nnz; store singular vectors via an extended product decomposition U'U'' so updates only touch low-dimensional matrices plus sparse additions.
Key results
- On the user-item matrix with k=16, the proposed method runs in 23s batch versus 192s for the best prior baseline at the same MSE (0.8616).
- On link prediction (Slashdot, Flickr, Epinions), the proposed method and its variants reduce runtime by more than 85% with comparable AP (e.g., 93.41% vs 93.40% on Slashdot).
- Runtime reductions of roughly an order of magnitude (factor of 10 or more) are reported for collaborative filtering while maintaining MSE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed sparse SV-LCOV updating algorithm instead of prior update methods | Truncated SVD updates · MovieLens25M streaming update, k=16 | Runtime: 626s -> 35s | Helped |
| Use the proposed sparse SV-LCOV updating algorithm instead of prior update methods | Truncated SVD updates · MovieLens25M streaming update, k=64 | Runtime: 2410s -> 135s | Helped |
| Use GKL to approximate the augmented space rather than the exact augmented space (ablation) | ours truncated SVD updater · MovieLens25M batch update, k=16 | Runtime: 23s -> 18s | Helped |
| Use GKL to approximate the augmented space rather than the exact augmented space (ablation) | ours truncated SVD updater · MovieLens25M streaming update, k=16 | Runtime: 35s -> 48s | Hurt |
| Use GKL to approximate the augmented space rather than the exact augmented space (ablation) | ours truncated SVD updater · MovieLens25M batch update, k=64 | Runtime: 49s -> 45s | Helped |
| Use GKL to approximate the augmented space rather than the exact augmented space (ablation) | ours truncated SVD updater · MovieLens25M streaming update, k=64 | Runtime: 135s -> 147s | Hurt |
| Use RPI to approximate the augmented space rather than the exact augmented space (ablation) | ours truncated SVD updater · MovieLens25M batch update, k=16 | Runtime: 23s -> 45s | Hurt |
| Use RPI to approximate the augmented space rather than the exact augmented space (ablation) | ours truncated SVD updater · MovieLens25M streaming update, k=16 | Runtime: 35s -> 43s | Hurt |
| Use RPI to approximate the augmented space rather than the exact augmented space (ablation) | ours truncated SVD updater · MovieLens25M batch update, k=64 | Runtime: 49s -> 98s | Hurt |
| Use RPI to approximate the augmented space rather than the exact augmented space (ablation) | ours truncated SVD updater · MovieLens25M streaming update, k=64 | Runtime: 135s -> 141s | Hurt |
| Use GKL to approximate the augmented space (ablation) | ours truncated SVD updater · Slashdot, Flickr, and Epinions | AP: 93.41% -> 93.56%; 95.16% -> 95.11%; 95.62% -> 95.70% | Mixed |
| Use RPI to approximate the augmented space (ablation) | ours truncated SVD updater · Slashdot, Flickr, and Epinions | AP: 93.41% -> 93.50%; 95.16% -> 95.14%; 95.62% -> 95.61% | Mixed |
Limitations
- Extended decomposition may have numerical issues when the matrix condition number is large; the suggested fix is resetting the k-by-k matrix to identity.
- Query cost increases from O(k) to O(k^2).
- Variants with GKL or RPI are needed for large update rank s, and performance gains vary with batch size and density.
Experimental setup
Datasets: Slashdot Flickr Epinions MovieLens25M
Benchmarks: Slashdot link prediction Flickr link prediction Epinions link prediction MovieLens25M collaborative filtering
Metrics: runtime average precision Frobenius norm mean squared error
Baselines: Zha-Simon SVD update GKL-based SVD update randomized power iteration SVD update graph coarsening SVD update
Builds on: Zha-Simon updating SVD Golub-Kahan-Lanczos bidiagonalization randomized power iteration
Closest papers by meaning
- Projection techniques to update the truncated SVD of evolving matrices with applications (ICML 2021 · similarity 0.91)
- [Re] Projection-based Algorithm for Updating the TruncatedSVD of Evolving Matrices (NeurIPS 2022 · similarity 0.87)
- Operator SVD with Neural Networks via Nested Low-Rank Approximation (ICML 2024 · similarity 0.85)
- Dobi-SVD: Differentiable SVD for LLM Compression and Some New Perspectives (ICLR 2025 · similarity 0.82)
- CORA: Per-Slice Coherent Orthogonal Rotation for SVD-based Low-Rank Adaptation (NeurIPS 2026 · similarity 0.82)
- OTLRM: Orthogonal Learning-based Low-Rank Metric for Multi-Dimensional Inverse Problems (AAAI 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.