Research map / Learning theory and algorithms / Matrix and tensor methods
Efficient Leverage Score Sampling for Tensor Train Decomposition
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 rTT-ALS, an ALS method for tensor train decomposition that uses exact leverage score sampling enabled by maintaining canonical form, with a data structure sampling rows in time logarithmic in tensor size.
Problem
Computing tensor train (TT) decompositions with ALS is exponential in tensor order N because each least-squares solve involves large unfoldings of the target tensor; existing randomized TT methods mostly use randomized SVD rather than sampling inside ALS.
Approach
Exploit the TT canonical form so that the leverage scores of the unfolded core chain reduce to squared row norms (identity Gram matrix), and build a data structure (adapted from CP leverage-score samplers) that draws exact leverage-score samples from TT core chains in time logarithmic in mode sizes, using a uniformly random column trick to get quadratic dependence on rank.
Key results
- On sparse FROSTT tensors (R=4 to 12, J=2^16), rTT-ALS fits match exact TT-ALS to about the third significant figure, with per-sweep speedups of 1.5x to 26x (NELL-2 at R=4 reaches 26.0x).
- On real dense datasets with target rank 5, rTT-ALS runs up to about 10x faster than TT-ALS (e.g., Tabby Cat 7.4 s vs 44.6 s) with nearly identical fit.
- On synthetic 500x500x500 tensors, rTT-ALS is about 2x faster than TT-ALS and 3x faster than TT-SVD while keeping fit comparable; rTT-SVD is fastest but has poor fit.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use leverage-score sampling in ALS instead of exact full least-squares solves | TT decomposition on Pavia University · Pavia University | time (seconds): 4.159196376800537 -> 0.8219459056854248 | Helped |
| Use leverage-score sampling in ALS instead of exact full least-squares solves | TT decomposition on Pavia University · Pavia University | fit: 0.6103819274363476 -> 0.6045745873636315 | Hurt |
| Use leverage-score sampling in ALS instead of exact full least-squares solves | TT decomposition on Tabby Cat · Tabby Cat | time (seconds): 44.56976294517517 -> 7.35988712310791 | Helped |
| Use leverage-score sampling in ALS instead of exact full least-squares solves | TT decomposition on MNIST · MNIST | fit: 0.4581272148325476 -> 0.45045158424742504 | Hurt |
| Use leverage-score sampling in ALS instead of exact full least-squares solves | TT decomposition on DC Mall · DC Mall | time (seconds): 21.856302976608276 -> 2.8072521686553955 | Helped |
| Use leverage-score sampling in ALS instead of exact full least-squares solves | Sparse TT decomposition · Uber | fit: 0.1334 -> 0.1332 | No clear effect |
| Use leverage-score sampling in ALS instead of exact full least-squares solves | Sparse TT decomposition · Enron | fit: 0.0507 -> 0.0498 | Hurt |
| Use leverage-score sampling in ALS instead of exact full least-squares solves | Sparse TT decomposition · NELL-2 | fit: 0.0214 -> 0.0213 | No clear effect |
| Increase the sample count from J=2^{15} by a factor of 5 | rTT-ALS · Uber and NELL-2 | fit | Helped |
| Increase the sample count | rTT-ALS · Enron | fit | No clear effect |
Surprising findings
- The randomized rTT-SVD is the fastest method on synthetic and dense data but achieves noticeably worse fit than the ALS-based variants.
- Speedup over exact ALS is largest at low ranks and shrinks as rank grows (e.g., Uber speedup falls from 4.0x at R=4 to 1.5x at R=12), while the fit gap widens with rank for fixed sample count.
Limitations
- Leverage score sampling guarantees need J = O~(R^2/(eps delta)) samples, and fixed sample counts make accuracy gap grow with rank.
- Speedup diminishes at higher TT ranks and on some datasets (Enron fits slightly lower).
- Experiments are restricted to equal ranks and to ALS sweeps initialized by SVD-based methods; the method is only described for TT, not general tree tensor networks.
Experimental setup
Datasets: Pavia University DC Mall MNIST Tabby Cat video Uber (FROSTT) Enron (FROSTT) NELL-2 (FROSTT) synthetic random TT tensors
Benchmarks: Pavia University DC Mall MNIST Tabby Cat Uber Enron NELL-2 synthetic tensors
Metrics: fit running time speedup per ALS sweep
Baselines: TT-SVD rTT-SVD TT-ALS
Builds on: Tensor train decomposition (TT-SVD) TT-ALS SPALS Exact leverage score sampling for CP (Larsen & Kolda style sampler) Randomized SVD
Closest papers by meaning
- A Sampling-Based Method for Tensor Ring Decomposition (ICML 2021 · similarity 0.92)
- More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees (ICML 2022 · similarity 0.91)
- Fast Exact Leverage Score Sampling from Khatri-Rao Products with Applications to Tensor Decomposition (NeurIPS 2023 · similarity 0.90)
- On Tensor Train Rank Minimization : Statistical Efficiency and Scalable Algorithm (NeurIPS 2017 · similarity 0.90)
- SPALS: Fast Alternating Least Squares via Implicit Leverage Scores Sampling (NeurIPS 2016 · similarity 0.90)
- Fast Tensor Completion via Approximate Richardson Iteration (ICML 2025 · similarity 0.88)
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.