# Sampling-Based Decomposition Algorithms for Arbitrary Tensor Networks

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 34 references that are in the map.
- First posted on arXiv 7 Oct 2022.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [TensorLy: Tensor Learning in Python](https://mlsanity.com/paper/1610.09555/) (2016)
- [Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives](https://mlsanity.com/paper/1708.09165/) (2017)
- [Randomized Tensor Ring Decomposition and Its Application to Large-scale Data Reconstruction](https://mlsanity.com/paper/1901.01652/) (2019)
- [More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees](https://mlsanity.com/paper/2110.07631/) (2021)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [Optimizing Tensor Network Contraction Using Reinforcement Learning](https://mlsanity.com/paper/2204.09052/) (2022)
- [Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs](https://mlsanity.com/paper/2205.13163/) (2022)
- [Fast algorithms for least square problems with Kronecker lower subsets](https://mlsanity.com/paper/2209.05662/) (2022)

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

- [Tensor Decomposition with Unaligned Observations](https://mlsanity.com/paper/2410.14046/) (2024)
- [Fast Tensor Completion via Approximate Richardson Iteration](https://mlsanity.com/paper/2502.09534/) (2025)

## Abstract (arXiv)

We show how to develop sampling-based alternating least squares (ALS) algorithms for decomposition of tensors into any tensor network (TN) format. Provided the TN format satisfies certain mild assumptions, resulting algorithms will have input sublinear per-iteration cost. Unlike most previous works on sampling-based ALS methods for tensor decomposition, the sampling in our framework is done according to the exact leverage score distribution of the design matrices in the ALS subproblems. We implement and test two tensor decomposition algorithms that use our sampling framework in a feature extraction experiment where we compare them against a number of other decomposition algorithms.