# Error Analysis of Tensor-Train Cross Approximation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 80 references that are in the map.
- First posted on arXiv 9 Jul 2022.

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

- [Tensorizing Neural Networks](https://mlsanity.com/paper/1509.06569/) (2015)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [A Tensorized Transformer for Language Modeling](https://mlsanity.com/paper/1906.09777/) (2019)
- [Efficient tensor completion for color image and video recovery: Low-rank tensor train](https://mlsanity.com/paper/1606.01500/) (2016)
- [Tensor-Train Recurrent Neural Networks for Video Classification](https://mlsanity.com/paper/1707.01786/) (2017)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Long-term Forecasting using Higher Order Tensor RNNs](https://mlsanity.com/paper/1711.00073/) (2017)
- [Expressive power of recurrent neural networks](https://mlsanity.com/paper/1711.00811/) (2017)
- [Tensor-Train Density Estimation](https://mlsanity.com/paper/2108.00089/) (2021)
- [Optimal CUR Matrix Decompositions](https://mlsanity.com/paper/1405.7910/) (2014)
- [Compressing Recurrent Neural Network with Tensor Train](https://mlsanity.com/paper/1705.08052/) (2017)
- [Tensor Methods and Recommender Systems](https://mlsanity.com/paper/1603.06038/) (2016)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (2013)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions](https://mlsanity.com/paper/2103.11037/) (2021)
- [Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition](https://mlsanity.com/paper/2108.10448/) (2021)
- [CUR Algorithm for Partially Observed Matrices](https://mlsanity.com/paper/1411.0860/) (2014)
- [CUR Decompositions, Similarity Matrices, and Subspace Clustering](https://mlsanity.com/paper/1711.04178/) (2017)
- [Cherry-Picking Gradients: Learning Low-Rank Embeddings of Visual Data via Differentiable Cross-Approximation](https://mlsanity.com/paper/2105.14250/) (2021)
- [Tensor Completion via Gaussian Process Based Initialization](https://mlsanity.com/paper/1912.05179/) (2019)
- [Low-rank approximation in the Frobenius norm by column and row subset selection](https://mlsanity.com/paper/1908.06059/) (2019)

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

- [Generative Modeling via Hierarchical Tensor Sketching](https://mlsanity.com/paper/2304.05305/) (2023)

## Abstract (arXiv)

Tensor train decomposition is widely used in machine learning and quantum physics due to its concise representation of high-dimensional tensors, overcoming the curse of dimensionality. Cross approximation-originally developed for representing a matrix from a set of selected rows and columns-is an efficient method for constructing a tensor train decomposition of a tensor from few of its entries. While tensor train cross approximation has achieved remarkable performance in practical applications, its theoretical analysis, in particular regarding the error of the approximation, is so far lacking. To our knowledge, existing results only provide element-wise approximation accuracy guarantees, which lead to a very loose bound when extended to the entire tensor. In this paper, we bridge this gap by providing accuracy guarantees in terms of the entire tensor for both exact and noisy measurements. Our results illustrate how the choice of selected subtensors affects the quality of the cross approximation and that the approximation error caused by model error and/or measurement error may not grow exponentially with the order of the tensor. These results are verified by numerical experiments, and may have important implications for the usefulness of cross approximations for high-order tensors, such as those encountered in the description of quantum many-body states.