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

arXiv:1609.05587

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

Wenqi Wang, Vaneet Aggarwal, Shuchin Aeron

Published Sep 19, 2016• 25 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1609.05587

Related papers

Efficient Low Rank Tensor Ring Completion

Wenqi Wang, Vaneet Aggarwal, Shuchin Aeron

Using the matrix product state (MPS) representation of the recently proposed tensor ring (TR) decompositions, in this paper we propose a TR completion algorithm, which is an alternating minimization algorithm that alternates over the factors in the MPS representation. This development is motivated in part by the success of matrix completion algorithms that alternate over the (low-rank) factors. We propose a novel initialization method and analyze the computational complexity of the TR completion algorithm. The numerical comparison between the TR completion algorithm and the existing algorithms that employ a low rank tensor train (TT) approximation for data completion shows that our method outperforms the existing ones for a variety of real computer vision settings, and thus demonstrates the improved expressive power of tensor ring as compared to tensor train.

arXiv:1707.08184•IEEE/CVF International Conference on Computer Vision (ICCV)•Oct 1, 2017•183 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•336 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•0 citations

Exploring Near-Optimal Contraction Strategies for the Scalar Product in the Tensor-Train Format

Przemysław Dominikowski, Atte Torri, Brice Pointal +3 more

Tensor-train (TT) decomposition has gained tremendous popularity due to its efficiency in handling high-dimensional data arising in scientific and quantum computing as well as machine learning applications. It provides a compact representation of matrices and vectors with a Kronecker product-like low-rank structure, and hence enables efficient matrix-vector operations in this compressed form. The vector scalar product is among such key operations, comprising a series of tensor contractions in a specific TT network where the order of contractions significantly impacts the computational cost. In this work, we introduce fast algorithms for finding a near-optimal contraction ordering for such networks. We show that our algorithms find such contraction orderings efficiently, outperforming the ordering methods for general tensor networks. Compared to our approaches, the best existing method incurs a higher cost of up to 15% for xTy, twice for xTAy, and more than ten times for xTABy scalar products, where A and B are matrices expressed in TT format.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•Jun 3, 2025•0 citations

Algebraic Operations on Tensor Trains

Petr Tichavský

The tensor train (TT) model is widely used to approximate high-dimensional tensors, enabling efficient handling of data that may exceed available memory. TT helps address the curse of dimensionality in applications such as system identification and dynamic programming. In some applications, TT is known as a ``matrix product state" (MPS). The last product is also known under the acronym MPO--MPS. The proposed algorithms achieve an improved trade-off between computational efficiency and accuracy compared to state-of-the-art methods.

arXiv:2606.14627•Jun 12, 2026•0 citations

Nonnegative Tensor Train Factorization with DMRG Technique

E. M. Shcherbakova

Tensor train is one of the modern decompositions used as low-rank tensor approximations of multidimensional arrays. If the original data is nonnegative we sometimes want the approximant to keep this property. In this work new methods for nonnegative tensor train factorization are proposed. Low-rank approximation approach helps to speed up the computations whereas DMRG technique allows to adapt nonnegative TT ranks for better accuracy. The performance analysis of the proposed algorithms as well as comparison with other nonnegative TT factorization method are presented.

Lobachevskii Journal of Mathematics•Nov 1, 2019•6 citations
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.
Using the matrix product state (MPS) representation of the recently proposed tensor ring (TR) decompositions, in this paper we propose a TR completion algorithm, which is an alternating minimization algorithm that alternates over the factors in the MPS representation. This development is motivated in part by the success of matrix completion algorithms that alternate over the (low-rank) factors. We propose a novel initialization method and analyze the computational complexity of the TR completion algorithm. The numerical comparison between the TR completion algorithm and the existing algorithms that employ a low rank tensor train (TT) approximation for data completion shows that our method outperforms the existing ones for a variety of real computer vision settings, and thus demonstrates the improved expressive power of tensor ring as compared to tensor train.
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.
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.
Tensor-train (TT) decomposition has gained tremendous popularity due to its efficiency in handling high-dimensional data arising in scientific and quantum computing as well as machine learning applications. It provides a compact representation of matrices and vectors with a Kronecker product-like low-rank structure, and hence enables efficient matrix-vector operations in this compressed form. The vector scalar product is among such key operations, comprising a series of tensor contractions in a specific TT network where the order of contractions significantly impacts the computational cost. In this work, we introduce fast algorithms for finding a near-optimal contraction ordering for such networks. We show that our algorithms find such contraction orderings efficiently, outperforming the ordering methods for general tensor networks. Compared to our approaches, the best existing method incurs a higher cost of up to 15% for xTy, twice for xTAy, and more than ten times for xTABy scalar products, where A and B are matrices expressed in TT format.
The tensor train (TT) model is widely used to approximate high-dimensional tensors, enabling efficient handling of data that may exceed available memory. TT helps address the curse of dimensionality in applications such as system identification and dynamic programming. In some applications, TT is known as a ``matrix product state" (MPS). The last product is also known under the acronym MPO--MPS. The proposed algorithms achieve an improved trade-off between computational efficiency and accuracy compared to state-of-the-art methods.
Tensor train is one of the modern decompositions used as low-rank tensor approximations of multidimensional arrays. If the original data is nonnegative we sometimes want the approximant to keep this property. In this work new methods for nonnegative tensor train factorization are proposed. Low-rank approximation approach helps to speed up the computations whereas DMRG technique allows to adapt nonnegative TT ranks for better accuracy. The performance analysis of the proposed algorithms as well as comparison with other nonnegative TT factorization method are presented.