Streaming Tensor Train Approximation

DOI10.1137/22M1515045zbMATH Open1523.65042arXiv2208.02600OpenAlexW4387339899MaRDI QIDQ6074548FDOQ6074548

Authors: Daniel Kressner, Bart Vandereycken, Rik Voorhaar 

Publication date: 12 October 2023

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: Tensor trains are a versatile tool to compress and work with high-dimensional data and functions. In this work we introduce the Streaming Tensor Train Approximation (STTA), a new class of algorithms for approximating a given tensor $mathcalT$ in the tensor train format. STTA accesses $mathcalT$ exclusively via two-sided random sketches of the original data, making it streamable and easy to implement in parallel -- unlike existing deterministic and randomized tensor train approximations. This property also allows STTA to conveniently leverage structure in $mathcalT$, such as sparsity and various low-rank tensor formats, as well as linear combinations thereof. When Gaussian random matrices are used for sketching, STTA is admissible to an analysis that builds and extends upon existing results on the generalized Nystr"om approximation for matrices. Our results show that STTA can be expected to attain a nearly optimal approximation error if the sizes of the sketches are suitably chosen. A range of numerical experiments illustrates the performance of STTA compared to existing deterministic and randomized approaches.

Full work available at URL: https://arxiv.org/abs/2208.02600

Recommendations

• Low-rank Tucker approximation of a tensor from streaming data
• Parallel Algorithms for Computing the Tensor-Train Decomposition
• SOTT: greedy approximation of a tensor as a sum of tensor trains
• Tensor train construction from tensor actions, with application to compression of large high order derivative tensors
• A continuous analogue of the tensor-train decomposition

zbMATH Keywords

dimension reductionlow-rank approximationparallel computingmatrix product statestensor train

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Multilinear algebra, tensor calculus (15A69) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• Tensor Decompositions and Applications
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Tensor-train decomposition
• Numerical linear algebra in the streaming model
• Tensor numerical methods in scientific computing
• Tensor Spaces and Numerical Tensor Calculus
• A literature survey of low-rank tensor approximation techniques
• A practical introduction to tensor networks: Matrix product states and projected entangled pair states
• The density-matrix renormalization group in the age of matrix product states
• Tensor networks and hierarchical tensors for the solution of high-dimensional partial differential equations
• Randomized algorithms for the approximations of Tucker and the tensor train decompositions
• Geometric Methods on Low-Rank Matrix and Tensor Manifolds
• Practical sketching algorithms for low-rank matrix approximation
• Tensor train construction from tensor actions, with application to compression of large high order derivative tensors
• Parallel Algorithms for Computing the Tensor-Train Decomposition
• Randomized Algorithms for Rounding in the Tensor-Train Format

Cited In (14)

• SVD-based algorithms for fully-connected tensor network decomposition
• An algorithm for arbitrary-order cumulant tensor calculation in a sliding window of data streams
• Approximation in the extended functional tensor train format
• SOTT: greedy approximation of a tensor as a sum of tensor trains
• A continuous analogue of the tensor-train decomposition
• An Incremental Tensor Train Decomposition Algorithm
• A sequential multilinear Nyström algorithm for streaming low-rank approximation of tensors in Tucker format
• SVD-based algorithms for tensor wheel decomposition
• Low-rank Tucker approximation of a tensor from streaming data
• Randomized Algorithms for Rounding in the Tensor-Train Format
• Tensor train construction from tensor actions, with application to compression of large high order derivative tensors
• Efficient construction of tensor ring representations from sampling
• Tracking tensor ring decompositions of streaming tensors
• Randomized tensor wheel decomposition

This page was built for publication: Streaming Tensor Train Approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074548)