# More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees

arXiv: https://arxiv.org/abs/2110.07631 · HTML: https://mlsanity.com/paper/2110.07631/

## 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 (most cited first, 25 of 25)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Tensorizing Neural Networks](https://mlsanity.com/paper/1509.06569/) (2015)
- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [On the Expressive Power of Deep Learning: A Tensor Analysis](https://mlsanity.com/paper/1509.05009/) (2015)
- [Tensor-Train Recurrent Neural Networks for Video Classification](https://mlsanity.com/paper/1707.01786/) (2017)
- [Ultimate tensorization: compressing convolutional and FC layers alike](https://mlsanity.com/paper/1611.03214/) (2016)
- [Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives](https://mlsanity.com/paper/1708.09165/) (2017)
- [Efficient Low Rank Tensor Ring Completion](https://mlsanity.com/paper/1707.08184/) (2017)
- [Machine Learning by Unitary Tensor Network of Hierarchical Tree Structure](https://mlsanity.com/paper/1710.04833/) (2017)
- [Supervised Learning with Quantum-Inspired Tensor Networks](https://mlsanity.com/paper/1605.05775/) (2016)
- [Learning Compact Recurrent Neural Networks with Block-Term Tensor Decomposition](https://mlsanity.com/paper/1712.05134/) (2017)
- [Expressive power of recurrent neural networks](https://mlsanity.com/paper/1711.00811/) (2017)
- [Sketching for Kronecker Product Regression and P-splines](https://mlsanity.com/paper/1712.09473/) (2017)
- [Optimal Sketching for Kronecker Product Regression and Low Rank Approximation](https://mlsanity.com/paper/1909.13384/) (2019)
- [Fast and Guaranteed Tensor Decomposition via Sketching](https://mlsanity.com/paper/1506.04448/) (2015)
- [Low-Rank Tucker Approximation of a Tensor From Streaming Data](https://mlsanity.com/paper/1904.10951/) (2019)
- [High-dimension Tensor Completion via Gradient-based Optimization Under Tensor-train Format](https://mlsanity.com/paper/1804.01983/) (2018)
- [Randomized Tensor Ring Decomposition and Its Application to Large-scale Data Reconstruction](https://mlsanity.com/paper/1901.01652/) (2019)
- [Tensorized Random Projections](https://mlsanity.com/paper/2003.05101/) (2020)
- [Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares](https://mlsanity.com/paper/1912.08294/) (2019)
- [Reverse iterative volume sampling for linear regression](https://mlsanity.com/paper/1806.01969/) (2018)
- [Tensor Random Projection for Low Memory Dimension Reduction](https://mlsanity.com/paper/2105.00105/) (2021)
- [Matrix Product State for Feature Extraction of Higher-Order Tensors](https://mlsanity.com/paper/1503.00516/) (2015)
- [Johnson-Lindenstrauss Embeddings with Kronecker Structure](https://mlsanity.com/paper/2106.13349/) (2021)
- [Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling](https://mlsanity.com/paper/2107.10654/) (2021)

## Built on by (most cited first, 7 of 7)

- [Alternating Local Enumeration (TnALE): Solving Tensor Network Structure Search with Fewer Evaluations](https://mlsanity.com/paper/2304.12875/) (2023)
- [Approximately Optimal Core Shapes for Tensor Decompositions](https://mlsanity.com/paper/2302.03886/) (2023)
- [Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs](https://mlsanity.com/paper/2205.13163/) (2022)
- [Domain-Aware Tensor Network Structure Search](https://mlsanity.com/paper/2505.23537/) (2025)
- [Towards LLM-guided Efficient and Interpretable Multi-linear Tensor Network Rank Selection](https://mlsanity.com/paper/2410.10728/) (2024)
- [Sampling-Based Decomposition Algorithms for Arbitrary Tensor Networks](https://mlsanity.com/paper/2210.03828/) (2022)
- [Towards Efficient and Accurate Approximation: Tensor Decomposition Based on Randomized Block Krylov Iteration](https://mlsanity.com/paper/2211.14828/) (2022)

## 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.