Research map / Learning theory and algorithms / Matrix and tensor methods
Sublinear Time Orthogonal Tensor Decomposition
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace sketching with importance (l2) sampling for inner products in robust tensor power method | robust tensor power method · Synthetic n=1200, λi=1/i^2 | running time to reach similar residual norm: 2.595 s vs 116.3 s (sampling vs sketching) | Helped |
| importance sampling without pre-scanning (uniform b/n samples per slice) instead of sketching | robust tensor power method · Synthetic n=1200, λi=1/i^2 | preprocessing time: 0.0 s vs 55.34 s | Helped |
| pre-scanning slice Frobenius norms to allocate samples proportional to slice norm (ablation) | importance sampling power method · Synthetic n=1200, λi=1/i^2 | running time at b=5n,B=10: 3.1 s with pre-scan vs 2.595 s without, plus 2.234 s preprocessing | Hurt |
| importance sampling (with or without pre-scan) vs sketching on LDA wiki tensor | robust tensor power method · LDA wiki dim 200 | running time to reach similar residual norm: about 0.56-0.64 s vs 4.577 s | Helped |
| number of samples per iteration (b) and number of repetitions (B) reduced relative to sketching (ablation) | importance sampling power method · Synthetic n=1200 | squared residual norm: residual ~0.087 across b=5n..40n and B=10..50 vs sketching 0.089 at largest budget | No clear effect |
Closest papers by meaning
- Fitting Low-Rank Tensors in Constant Time (NeurIPS 2017 · similarity 0.88)
- Tensor Decomposition via Joint Matrix Schur Decomposition (ICML 2016 · similarity 0.87)
- Random Tensor Theory for Tensor Decomposition (AAAI 2022 · similarity 0.86)
- Fast Sampling-Based Sketches for Tensors (ICML 2024 · similarity 0.86)
- Fast Tensor Completion via Approximate Richardson Iteration (ICML 2025 · similarity 0.86)
- Efficient Leverage Score Sampling for Tensor Train Decomposition (NeurIPS 2024 · similarity 0.85)
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.