# Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 52 references that are in the map.
- First posted on arXiv 15 Jul 2022.

## Builds on (most cited first, 18 of 18)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Towards Efficient Tensor Decomposition-Based DNN Model Compression with Optimization Framework](https://mlsanity.com/paper/2107.12422/) (2021)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Optimal Sketching for Kronecker Product Regression and Low Rank Approximation](https://mlsanity.com/paper/1909.13384/) (2019)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Low-Rank Tucker Approximation of a Tensor From Streaming Data](https://mlsanity.com/paper/1904.10951/) (2019)
- [High-Dimensional Stochastic Optimal Control using Continuous Tensor Decompositions](https://mlsanity.com/paper/1611.04706/) (2016)
- [Tensorized Random Projections](https://mlsanity.com/paper/2003.05101/) (2020)
- [Fast Regression for Structured Inputs](https://mlsanity.com/paper/2203.07557/) (2022)
- [Linear Hamilton Jacobi Bellman Equations in High Dimensions](https://mlsanity.com/paper/1404.1089/) (2014)
- [L1-norm Tucker Tensor Decomposition](https://mlsanity.com/paper/1904.06455/) (2019)
- [Sublinear Time Numerical Linear Algebra for Structured Matrices](https://mlsanity.com/paper/1912.06060/) (2019)
- [Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling](https://mlsanity.com/paper/2107.10654/) (2021)
- [Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs](https://mlsanity.com/paper/2205.13163/) (2022)
- [Parameterization of tensor network contraction](https://mlsanity.com/paper/1906.00013/) (2019)
- [In-Database Regression in Input Sparsity Time](https://mlsanity.com/paper/2107.05672/) (2021)

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

- [Solving Tensor Low Cycle Rank Approximation](https://mlsanity.com/paper/2304.06594/) (2023)
- [Faster Robust Tensor Power Method for Arbitrary Order](https://mlsanity.com/paper/2306.00406/) (2023)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)
- [ℓp-Regression in the Arbitrary Partition Model of Communication](https://mlsanity.com/paper/2307.05117/) (2023)

## Abstract (arXiv)

We study low rank approximation of tensors, focusing on the tensor train and Tucker decompositions, as well as approximations with tree tensor networks and more general tensor networks. For tensor train decomposition, we give a bicriteria (1 + eps)-approximation algorithm with a small bicriteria rank and O(q · nnz(A)) running time, up to lower order terms, which improves over the additive error algorithm of citehuber2017randomized. We also show how to convert the algorithm of citehuber2017randomized into a relative error algorithm, but their algorithm necessarily has a running time of O(qr2 · nnz(A)) + n · poly(qk/eps) when converted to a (1 + eps)-approximation algorithm with bicriteria rank r. To the best of our knowledge, our work is the first to achieve polynomial time relative error approximation for tensor train decomposition. Our key technique is a method for obtaining subspace embeddings with a number of rows polynomial in q for a matrix which is the flattening of a tensor train of q tensors. We extend our algorithm to tree tensor networks. In addition, we extend our algorithm to tensor networks with arbitrary graphs (which we refer to as general tensor networks), by using a result of citems08simulatingquantumtensorcontraction and showing that a general tensor network of rank k can be contracted to a binary tree network of rank kO(deg(G)tw(G)), allowing us to reduce to the case of tree tensor networks. Finally, we give new fixed-parameter tractable algorithms for the tensor train, Tucker, and CP decompositions, which are simpler than those of citeswz19tensorlowrank since they do not make use of polynomial system solvers. Our technique of Gaussian subspace embeddings with exactly k rows (and thus exponentially small success probability) may be of independent interest.