mlsanityData to 14 Oct 2026

More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees

arXiv 2110.07631 ↗First posted 14 Oct 2021math.NA cs.LG cs.NAcited by 7

Not on the map. Why?

Abstract (arXiv)

Recent papers have developed alternating least squares (ALS) methods for CP and tensor ring decomposition with a per-iteration cost which is sublinear in the number of input tensor entries for low-rank decomposition. However, the per-iteration cost of these methods still has an exponential dependence on the number of tensor modes when parameters are chosen to achieve certain worst-case guarantees. In this paper, we propose sampling-based ALS methods for the CP and tensor ring decompositions whose cost does not have this exponential dependence, thereby significantly improving on the previous state-of-the-art. We provide a detailed theoretical analysis and also apply the methods in a feature extraction experiment.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 25 of its 92 references that are in the map. First posted on arXiv 14 Oct 2021.

Builds on

25 of 92 references.

References · 25

  1. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  2. 2015Tensorizing Neural Networkscited by 250
  3. 2016Tensor Ring Decompositioncited by 127
  4. 2015On the Expressive Power of Deep Learning: A Tensor Analysiscited by 97
  5. 2017Tensor-Train Recurrent Neural Networks for Video Classificationcited by 59
  6. 2016Ultimate tensorization: compressing convolutional and FC layers alikecited by 56
  7. 2017Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectivescited by 54
  8. 2017Efficient Low Rank Tensor Ring Completioncited by 45
  9. 2017Machine Learning by Unitary Tensor Network of Hierarchical Tree Structurecited by 40
  10. 2016Supervised Learning with Quantum-Inspired Tensor Networkscited by 36
  11. 2017Learning Compact Recurrent Neural Networks with Block-Term Tensor Decompositioncited by 33
  12. 2017Expressive power of recurrent neural networkscited by 30
13 more
  1. 2017Sketching for Kronecker Product Regression and P-splinescited by 29
  2. 2019Optimal Sketching for Kronecker Product Regression and Low Rank Approximationcited by 29
  3. 2015Fast and Guaranteed Tensor Decomposition via Sketchingcited by 19
  4. 2019Low-Rank Tucker Approximation of a Tensor From Streaming Datacited by 15
  5. 2018High-dimension Tensor Completion via Gradient-based Optimization Under Tensor-train Formatcited by 12
  6. 2019Randomized Tensor Ring Decomposition and Its Application to Large-scale Data Reconstructioncited by 11
  7. 2020Tensorized Random Projectionscited by 11
  8. 2019Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squarescited by 10
  9. 2018Reverse iterative volume sampling for linear regressioncited by 9
  10. 2021Tensor Random Projection for Low Memory Dimension Reductioncited by 7
  11. 2015Matrix Product State for Feature Extraction of Higher-Order Tensorscited by 6
  12. 2021Johnson-Lindenstrauss Embeddings with Kronecker Structurecited by 5
  13. 2021Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Samplingcited by 5

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 2; 2024: 1; 2025: 1.

7 papers.

  1. 2023Alternating Local Enumeration (TnALE): Solving Tensor Network Structure Search with Fewer Evaluationscited by 12
  2. 2023Approximately Optimal Core Shapes for Tensor Decompositionscited by 8
  3. 2022Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputscited by 5
  4. 2025Domain-Aware Tensor Network Structure Searchcited by 5
  5. 2024Towards LLM-guided Efficient and Interpretable Multi-linear Tensor Network Rank Selectioncited by 3
  6. 2022Sampling-Based Decomposition Algorithms for Arbitrary Tensor Networkscited by 2
  7. 2022Towards Efficient and Accurate Approximation: Tensor Decomposition Based on Randomized Block Krylov Iterationcited by 0