mlsanityData to 14 Oct 2026

Error Analysis of Tensor-Train Cross Approximation

arXiv 2207.04327 ↗First posted 9 Jul 2022cs.LG cs.IT math.ITcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper 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

22 of 80 references.

References · 22

  1. 2015Tensorizing Neural Networkscited by 250
  2. 2016Tensor Decomposition for Signal Processing and Machine Learningcited by 224
  3. 2016Tensor Ring Decompositioncited by 127
  4. 2019A Tensorized Transformer for Language Modelingcited by 86
  5. 2016Efficient tensor completion for color image and video recovery: Low-rank tensor traincited by 61
  6. 2017Tensor-Train Recurrent Neural Networks for Video Classificationcited by 59
  7. 2018On Fast Leverage Score Sampling and Optimal Learningcited by 41
  8. 2017Long-term Forecasting using Higher Order Tensor RNNscited by 34
  9. 2017Expressive power of recurrent neural networkscited by 30
  10. 2021Tensor-Train Density Estimationcited by 30
  11. 2014Optimal CUR Matrix Decompositionscited by 29
  12. 2017Compressing Recurrent Neural Network with Tensor Traincited by 28
10 more
  1. 2016Tensor Methods and Recommender Systemscited by 24
  2. 2013Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Samplingcited by 21
  3. 2021Robust CUR Decomposition: Theory and Imaging Applicationscited by 20
  4. 2021Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositionscited by 13
  5. 2021Fast Robust Tensor Principal Component Analysis via Fiber CUR Decompositioncited by 8
  6. 2014CUR Algorithm for Partially Observed Matricescited by 7
  7. 2017CUR Decompositions, Similarity Matrices, and Subspace Clusteringcited by 4
  8. 2021Cherry-Picking Gradients: Learning Low-Rank Embeddings of Visual Data via Differentiable Cross-Approximationcited by 4
  9. 2019Tensor Completion via Gaussian Process Based Initializationcited by 3
  10. 2019Low-rank approximation in the Frobenius norm by column and row subset selectioncited by 2

Built on by

Cited by year

Citing papers per year: 2023: 1.

1 paper.

  1. 2023Generative Modeling via Hierarchical Tensor Sketchingcited by 8