Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

SIAM Journal on Scientific Computing

SOTT: Greedy Approximation of a Tensor as a Sum of Tensor Trains

Virginie Ehrlacher, Maria Fuente-Ruiz, Damiano Lombardi

Published Mar 21, 2022• 3 citations
Publisher

Abstract

In the present work, a method is proposed in order to compute an approximation of a given tensor as a sum of tensor trains (TTs), where the order of the variates and the values of the ranks can vary from one term to the other in an adaptive way. The numerical scheme is based on a greedy algorithm and an adaptation of the TT-SVD method. It achieves good performance without depending on the variable ordering: we observed that it behaves as the average of the TT-SVDs when considering all possible permutations of the variable order. The proposed approach can also be used in order to compute an approximation of a tensor in a canonical polyadic (CP) format, as an alternative to standard algorithms like alternating linear squares (ALS) or alternating singular value decomposition (ASVD) methods. Some numerical experiments are proposed, in which the proposed method is compared to ALS and ASVD methods for the construction of a CP approximation of a given tensor and performs particularly well for high-order tensors. The interest of approximating a tensor as a sum of TTs is illustrated in several numerical test cases.

DOI
10.1137/20m1381472

Related papers

Optimizing the Order of Modes in Tensor Train Decomposition

Petr Tichavský, Ondřej Straka

The tensor train (TT) is a popular way of representing high-dimensional hyper-rectangular data structures called tensors. It is widely used, for example, in quantum chemistry under the name “matrix product state”. The complexity of the TT model mainly depends on the bond dimensions that connect TT cores, constituting the model. Unlike canonical polyadic decomposition, the TT model complexity may depend on the order of the modes/indices in the data structures or the order of the core tensors in the TT, in general. This letter aims to provide methods for optimizing the order of the modes to reduce the bond dimensions. Since the number of possible orderings of the cores is exponentially high, we propose a greedy algorithm that provides a suboptimal solution. We consider three problem setups, i.e., specifications of the tensor: tensor given by a list of all its elements, tensor described by a TT model with some default order of the modes, and tensor obtained by sampling a multivariate function.

IEEE Signal Processing Letters•Jan 1, 2025•4 citations

A TT-Based Hierarchical Framework for Decomposing High-Order Tensors

Yassine Zniyed, Rémy Boyer, André L. F. de Almeida +1 more

In the context of big data, high-order tensor decompositions have to face a new challenge in terms of storage and computational costs. The tensor train (TT) decomposition provides a very useful graph-based model reduction, whose storage cost grows linearly with the tensor order $D$. The computation of the TT-core tensors and TT-ranks can be done in a stable sequential (i.e., noniterative) way thanks to the popular TT-SVD algorithm. In this paper, we exploit the ideas developed for the hierarchical/tree Tucker decomposition in the context of the TT decomposition. Specifically, a new efficient estimation scheme, called TT-HSVD (Tensor-Train Hierarchical SVD), is proposed as a solution to compute the TT decomposition of a high-order tensor. The new algorithm simultaneously delivers the TT-core tensors and their TT-ranks in a hierarchical way. It is a stable (i.e., noniterative) and computationally more efficient algorithm than TT-SVD, which is very important when dealing with large-scale data. The TT-HSVD algorithm uses a new reshaping strategy and a tailored partial SVD, which allows us to deal with smaller matrices compared to those of the TT-SVD. In addition, TT-HSVD is well suited for a parallel processing architecture. An algebraic analysis of the two algorithms is carried out, showing that TT-SVD and TT-HSVD compute the same TT-ranks and TT-core tensors up to specific bases. Simulation results for different tensor orders and dimensions corroborate the effectiveness of the proposed algorithm.

SIAM Journal on Scientific Computing•Jan 1, 2020•36 citations

The Alternating Linear Scheme for Tensor Optimization in the Tensor Train Format

Sebastian Holtz, Thorsten Rohwedder, Reinhold Schneider

Recent achievements in the field of tensor product approximation provide promising new formats for the representation of tensors in form of tree tensor networks. In contrast to the canonical r-term representation (CANDECOMP, PARAFAC), these new formats provide stable representations, while the amount of required data is only slightly larger. The tensor train (TT) format [SIAM J. Sci. Comput., 33 (2011), pp. 2295–2317], a simple special case of the hierarchical Tucker format [J. Fourier Anal. Appl., 5 (2009), p. 706], is a useful prototype for practical low-rank tensor representation. In this article, we show how optimization tasks can be treated in the TT format by a generalization of the well-known alternating least squares (ALS) algorithm and by a modified approach (MALS) that enables dynamical rank adaptation. A formulation of the component equations in terms of so-called retraction operators helps to show that many structural properties of the original problems transfer to the micro-iterations, giving what is to our knowledge the first stable generic algorithm for the treatment of optimization tasks in the tensor format. For the examples of linear equations and eigenvalue equations, we derive concrete working equations for the micro-iteration steps; numerical examples confirm the theoretical results concerning the stability of the TT decomposition and of ALS and MALS but also show that in some cases, high TT ranks are required during the iterative approximation of low-rank tensors, showing some potential of improvement.

SIAM Journal on Scientific Computing•Jan 1, 2012•361 citations

Computing Low-Rank Approximations of Large-Scale Matrices with the Tensor Network Randomized SVD

Kim Batselier, Wenjian Yu, Luca Daniel +1 more

We propose a new algorithm for the computation of a singular value decomposition (SVD) low-rank approximation of a matrix in the matrix product operator (MPO) format, also called the tensor train matrix format. Our tensor network randomized SVD (TNrSVD) algorithm is an MPO implementation of the randomized SVD algorithm that is able to compute dominant singular values and their corresponding singular vectors. In contrast to the state-of-the-art tensor-based alternating least squares SVD (ALS-SVD) and modified alternating least squares SVD (MALS-SVD) matrix approximation methods, TNrSVD can be up to 13 times faster while achieving better accuracy. In addition, our TNrSVD algorithm also produces accurate approximations in particular cases where both ALS-SVD and MALS-SVD fail to converge. We also propose a new algorithm for the fast conversion of a sparse matrix into its corresponding MPO form, which is up to 509 times faster than the standard tensor train SVD method while achieving machine precision accuracy. The efficiency and accuracy of both algorithms are demonstrated in numerical experiments.

arXiv:1707.07803•SIAM Journal on Matrix Analysis and Applications•Jan 1, 2018•32 citations

Tensor Completion by Alternating Minimization under the Tensor Train (TT) Model

Wenqi Wang, Vaneet Aggarwal, Shuchin Aeron

Using the matrix product state (MPS) representation of tensor train decompositions, in this paper we propose a tensor completion algorithm which alternates over the matrices (tensors) in the MPS representation. This development is motivated in part by the success of matrix completion algorithms which alternate over the (low-rank) factors. We comment on the computational complexity of the proposed algorithm and numerically compare it with existing methods employing low rank tensor train approximation for data completion as well as several other recently proposed methods. We show that our method is superior to existing ones for a variety of real settings.

arXiv:1609.05587•Sep 19, 2016•39 citations

Fast elementwise operations on tensor trains with alternating cross interpolation

Marc K. Ritter

Tensor trains (TTs), also known as matrix product states (MPS), are compressed representations of high-dimensional data that can be efficiently manipulated to perform calculations on the data. In many applications, such as TT-based solvers for nonlinear partial differential equations, the most expensive step is an elementwise multiplication or similar elementwise operation on multiple TTs. Known error-controlled algorithms for such operations scale as $O(χ^4)$, where $χ$ is the TT rank. If the rank of the output is smaller than $χ^2$, it is possible to formulate algorithms with better scaling. In this work, we present the alternating cross interpolation (ACI) algorithm that performs such operations in $O(χ^3)$, while maintaining error control. We demonstrate these properties on benchmark problems, achieving a significant speedup for TT ranks that are commonly encountered in practical applications.

math.NACross-listedarXiv:2604.00037•Mar 26, 2026•3 citations
In the present work, a method is proposed in order to compute an approximation of a given tensor as a sum of tensor trains (TTs), where the order of the variates and the values of the ranks can vary from one term to the other in an adaptive way. The numerical scheme is based on a greedy algorithm and an adaptation of the TT-SVD method. It achieves good performance without depending on the variable ordering: we observed that it behaves as the average of the TT-SVDs when considering all possible permutations of the variable order. The proposed approach can also be used in order to compute an approximation of a tensor in a canonical polyadic (CP) format, as an alternative to standard algorithms like alternating linear squares (ALS) or alternating singular value decomposition (ASVD) methods. Some numerical experiments are proposed, in which the proposed method is compared to ALS and ASVD methods for the construction of a CP approximation of a given tensor and performs particularly well for high-order tensors. The interest of approximating a tensor as a sum of TTs is illustrated in several numerical test cases.
The tensor train (TT) is a popular way of representing high-dimensional hyper-rectangular data structures called tensors. It is widely used, for example, in quantum chemistry under the name “matrix product state”. The complexity of the TT model mainly depends on the bond dimensions that connect TT cores, constituting the model. Unlike canonical polyadic decomposition, the TT model complexity may depend on the order of the modes/indices in the data structures or the order of the core tensors in the TT, in general. This letter aims to provide methods for optimizing the order of the modes to reduce the bond dimensions. Since the number of possible orderings of the cores is exponentially high, we propose a greedy algorithm that provides a suboptimal solution. We consider three problem setups, i.e., specifications of the tensor: tensor given by a list of all its elements, tensor described by a TT model with some default order of the modes, and tensor obtained by sampling a multivariate function.
In the context of big data, high-order tensor decompositions have to face a new challenge in terms of storage and computational costs. The tensor train (TT) decomposition provides a very useful graph-based model reduction, whose storage cost grows linearly with the tensor order DDD. The computation of the TT-core tensors and TT-ranks can be done in a stable sequential (i.e., noniterative) way thanks to the popular TT-SVD algorithm. In this paper, we exploit the ideas developed for the hierarchical/tree Tucker decomposition in the context of the TT decomposition. Specifically, a new efficient estimation scheme, called TT-HSVD (Tensor-Train Hierarchical SVD), is proposed as a solution to compute the TT decomposition of a high-order tensor. The new algorithm simultaneously delivers the TT-core tensors and their TT-ranks in a hierarchical way. It is a stable (i.e., noniterative) and computationally more efficient algorithm than TT-SVD, which is very important when dealing with large-scale data. The TT-HSVD algorithm uses a new reshaping strategy and a tailored partial SVD, which allows us to deal with smaller matrices compared to those of the TT-SVD. In addition, TT-HSVD is well suited for a parallel processing architecture. An algebraic analysis of the two algorithms is carried out, showing that TT-SVD and TT-HSVD compute the same TT-ranks and TT-core tensors up to specific bases. Simulation results for different tensor orders and dimensions corroborate the effectiveness of the proposed algorithm.
Recent achievements in the field of tensor product approximation provide promising new formats for the representation of tensors in form of tree tensor networks. In contrast to the canonical r-term representation (CANDECOMP, PARAFAC), these new formats provide stable representations, while the amount of required data is only slightly larger. The tensor train (TT) format [SIAM J. Sci. Comput., 33 (2011), pp. 2295–2317], a simple special case of the hierarchical Tucker format [J. Fourier Anal. Appl., 5 (2009), p. 706], is a useful prototype for practical low-rank tensor representation. In this article, we show how optimization tasks can be treated in the TT format by a generalization of the well-known alternating least squares (ALS) algorithm and by a modified approach (MALS) that enables dynamical rank adaptation. A formulation of the component equations in terms of so-called retraction operators helps to show that many structural properties of the original problems transfer to the micro-iterations, giving what is to our knowledge the first stable generic algorithm for the treatment of optimization tasks in the tensor format. For the examples of linear equations and eigenvalue equations, we derive concrete working equations for the micro-iteration steps; numerical examples confirm the theoretical results concerning the stability of the TT decomposition and of ALS and MALS but also show that in some cases, high TT ranks are required during the iterative approximation of low-rank tensors, showing some potential of improvement.
We propose a new algorithm for the computation of a singular value decomposition (SVD) low-rank approximation of a matrix in the matrix product operator (MPO) format, also called the tensor train matrix format. Our tensor network randomized SVD (TNrSVD) algorithm is an MPO implementation of the randomized SVD algorithm that is able to compute dominant singular values and their corresponding singular vectors. In contrast to the state-of-the-art tensor-based alternating least squares SVD (ALS-SVD) and modified alternating least squares SVD (MALS-SVD) matrix approximation methods, TNrSVD can be up to 13 times faster while achieving better accuracy. In addition, our TNrSVD algorithm also produces accurate approximations in particular cases where both ALS-SVD and MALS-SVD fail to converge. We also propose a new algorithm for the fast conversion of a sparse matrix into its corresponding MPO form, which is up to 509 times faster than the standard tensor train SVD method while achieving machine precision accuracy. The efficiency and accuracy of both algorithms are demonstrated in numerical experiments.
Using the matrix product state (MPS) representation of tensor train decompositions, in this paper we propose a tensor completion algorithm which alternates over the matrices (tensors) in the MPS representation. This development is motivated in part by the success of matrix completion algorithms which alternate over the (low-rank) factors. We comment on the computational complexity of the proposed algorithm and numerically compare it with existing methods employing low rank tensor train approximation for data completion as well as several other recently proposed methods. We show that our method is superior to existing ones for a variety of real settings.
Tensor trains (TTs), also known as matrix product states (MPS), are compressed representations of high-dimensional data that can be efficiently manipulated to perform calculations on the data. In many applications, such as TT-based solvers for nonlinear partial differential equations, the most expensive step is an elementwise multiplication or similar elementwise operation on multiple TTs. Known error-controlled algorithms for such operations scale as O(χ4)O(χ^4)O(χ4), where χχχ is the TT rank. If the rank of the output is smaller than χ2χ^2χ2, it is possible to formulate algorithms with better scaling. In this work, we present the alternating cross interpolation (ACI) algorithm that performs such operations in O(χ3)O(χ^3)O(χ3), while maintaining error control. We demonstrate these properties on benchmark problems, achieving a significant speedup for TT ranks that are commonly encountered in practical applications.