Abstract We show that the recent tensor-train (TT) decompositions of matrices come up from its recursive Kronecker-product representations with a systematic use of common bases. The names TTM and QTT used in this case stress the relation with multilevel matrices or quantization that increases artificially the number of levels. Then we investigate how the tensor-train ranks of a matrix can be related to those of its inverse. In the case of a banded Toeplitz matrix, we prove that the tensor-train ranks of its inverse are bounded above by 1+(l+u)^2, where l and u are the bandwidths in the lower and upper parts of the matrix without the main diagonal.
Abstract We show that the recent tensor-train (TT) decompositions of matrices come up from its recursive Kronecker-product representations with a systematic use of common bases. The names TTM and QTT used in this case stress the relation with multilevel matrices or quantization that increases artificially the number of levels. Then we investigate how the tensor-train ranks of a matrix can be related to those of its inverse. In the case of a banded Toeplitz matrix, we prove that the tensor-train ranks of its inverse are bounded above by 1+(l+u)^2, where l and u are the bandwidths in the lower and upper parts of the matrix without the main diagonal.
We focus on the construction of explicit low-rank representations of matrices in the tensor train (TT) and quantized tensor train (QTT) formats which have been proposed recently for the low-parametric structured representation of large-scale tensors. The matrices under consideration are discretizations of the Laplace operator in a hypercube (in one and many dimensions) and their inverses (in one dimension). For these matrices we derive explicit and exact QTT representations of low QTT ranks independent of the numbers d and n2 of dimensions and entries in each dimension. This implies that for the matrices considered the storage cost is O(dlogn), i.e., logarithmic with respect to the total number n2d of entries. The same applies to the computational complexity of the QTT-structured operations with these matrices, which now depends on the QTT ranks of the other operands. The general result of the paper is the notation and technique we introduce in order to examine the QTT structure of matrices analytically. They prove to be an efficient tool of studying other tensors related to particular computational problems, which are not considered in this paper.
We study the tensor structure of two operations: the transformation of a given multidimensional vector into a multilevel Toeplitz matrix and the convolution of two given multidimensional vectors. We show that the low-rank tensor structure of the input is preserved in the output and propose efficient algorithms for these operations in the newly introduced quantized tensor train (QTT) format. Consider a d-dimensional 2n×⋯×2n-vector x. If it is represented elementwise, the number of parameters is (2n)d. However, if we assume that x is given in a QTT representation with ranks bounded by p, the number of parameters is reduced to O(dp2logn). Under this assumption we show how the multilevel Toeplitz matrix generated by x can be obtained in the QTT format with ranks bounded by 2p in O(dp2logn) operations. We also describe how the convolution x⋆y of x and a d-dimensional n×⋯×n-vector y can be computed in the QTT format with ranks bounded by 2t in O(dt2logn) operations, provided that the matrix xy′ is given in the same format with ranks bounded by t. We exploit an algorithm for the inexact matrix-vector multiplication in the QTT format to accelerate the convolution algorithm dramatically. The performance of our approach to convolution is demonstrated with numerical examples, including the computation of the Newton potential of a strong cusp on fine grids with up to 220×220×220 points in three dimensions.
We discuss extended definitions of linear and multilinear operations such as Kronecker, Hadamard, and contracted products, and establish links between them for tensor calculus. Then we introduce effective low-rank tensor approximation techniques including Candecomp/Parafac (CP), Tucker, and tensor train (TT) decompositions with a number of mathematical and graphical representations. We also provide a brief review of mathematical properties of the TT decomposition as a low-rank approximation technique. With the aim of breaking the curse-of-dimensionality in large-scale numerical analysis, we describe basic operations on large-scale vectors, matrices, and high-order tensors represented by TT decomposition. The proposed representations can be used for describing numerical methods based on TT decomposition for solving large-scale optimization problems such as systems of linear equations and symmetric eigenvalue problems.
Machine learning and data mining algorithms are becoming increasingly important in analyzing large volume, multi-relational and multi--modal datasets, which are often conveniently represented as multiway arrays or tensors. It is therefore timely and valuable for the multidisciplinary research community to review tensor decompositions and tensor networks as emerging tools for large-scale data analysis and data mining. We provide the mathematical and graphical representations and interpretation of tensor networks, with the main focus on the Tucker and Tensor Train (TT) decompositions and their extensions or generalizations. Keywords: Tensor networks, Function-related tensors, CP decomposition, Tucker models, tensor train (TT) decompositions, matrix product states (MPS), matrix product operators (MPO), basic tensor operations, multiway component analysis, multilinear blind source separation, tensor completion, linear/multilinear dimensionality reduction, large-scale optimization problems, symmetric eigenvalue decomposition (EVD), PCA/SVD, huge systems of linear equations, pseudo-inverse of very large matrices, Lasso and Canonical Correlation Analysis (CCA) (This is Part 1)
Tensor network methods have been a key ingredient of advances in condensed matter physics and have recently sparked interest in the machine learning community for their ability to compactly represent very high-dimensional objects. Tensor network methods can for example be used to efficiently learn linear models in exponentially large feature spaces [Stoudenmire and Schwab, 2016]. In this work, we derive upper and lower bounds on the VC dimension and pseudo-dimension of a large class of tensor network models for classification, regression and completion. Our upper bounds hold for linear models parameterized by arbitrary tensor network structures, and we derive lower bounds for common tensor decomposition models~(CP, Tensor Train, Tensor Ring and Tucker) showing the tightness of our general upper bound. These results are used to derive a generalization bound which can be applied to classification with low rank matrices as well as linear classifiers based on any of the commonly used tensor decomposition models. As a corollary of our results, we obtain a bound on the VC dimension of the matrix product state classifier introduced in [Stoudenmire and Schwab, 2016] as a function of the so-called bond dimension~(i.e. tensor train rank), which answers an open problem listed by Cirac, Garre-Rubio and Pérez-García in [Cirac et al., 2019].
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.