This dissertation reviews classical vector - tensor analysis, building up to the necessary techniques required to decompose a tensor into a tensor train and to reconstruct it back into the original tensor with minimal error. The tensor train decomposition decomposes a tensor of dimensionality d into a train of d third order tensors, whose sizes are dependent upon the rank and chosen error bound. I will be reviewing the required operations of matricization, tensor - matrix, vector and tensor multiplication to be able to compute this decomposition. I then move onto analysing the tensor train decomposition by ap-plying it to different types of tensor, of differing dimensionality with a variety of accuracy bounds to investigate their influence on the time taken to complete the decomposition and the final absolute error. Finally I explore a method to compute a d-dimensional integration from the tensor train, which will allow larger tensors to be integrated with the memory required dramatically reduced after the tensor is decomposed. I will be applying this technique to two tensors with different ranks and compare the efficiency and accuracy of integrating directly from the tensor to that of the tensor train decomposition.
This dissertation reviews classical vector - tensor analysis, building up to the necessary techniques required to decompose a tensor into a tensor train and to reconstruct it back into the original tensor with minimal error. The tensor train decomposition decomposes a tensor of dimensionality d into a train of d third order tensors, whose sizes are dependent upon the rank and chosen error bound. I will be reviewing the required operations of matricization, tensor - matrix, vector and tensor multiplication to be able to compute this decomposition. I then move onto analysing the tensor train decomposition by ap-plying it to different types of tensor, of differing dimensionality with a variety of accuracy bounds to investigate their influence on the time taken to complete the decomposition and the final absolute error. Finally I explore a method to compute a d-dimensional integration from the tensor train, which will allow larger tensors to be integrated with the memory required dramatically reduced after the tensor is decomposed. I will be applying this technique to two tensors with different ranks and compare the efficiency and accuracy of integrating directly from the tensor to that of the tensor train decomposition.
The tensor train decomposition decomposes a tensor into a "train" of 3-way tensors that are interconnected through the summation of auxiliary indices. The decomposition is stable, has a well-defined notion of rank and enables the user to perform various linear algebra operations on vectors and matrices of exponential size in a computationally efficient manner. The tensor ring decomposition replaces the train by a ring through the introduction of one additional auxiliary variable. This article discusses a major issue with the tensor ring decomposition: its inability to compute an exact minimal-rank decomposition from a decomposition with sub-optimal ranks. Both the contraction operation and Hadamard product are motivated from applications and it is shown through simple examples how the tensor ring-rounding procedure fails to retrieve minimal-rank decompositions with these operations. These observations, together with the already known issue of not being able to find a best low-rank tensor ring approximation to a given tensor indicate that the applicability of tensor rings is severely limited.
The simulation and analysis of high-dimensional problems is often infeasible due to the curse of dimensionality. In this thesis, we investigate the potential of tensor decompositions for mitigating this curse when considering systems from several application areas. Using tensor-based solvers, we directly compute numerical solutions of master equations associated with Markov processes on extremely large state spaces. Furthermore, we exploit the tensor-train format to approximate eigenvalues and corresponding eigentensors of linear tensor operators. In order to analyze the dominant dynamics of high- dimensional stochastic processes, we propose several decomposition techniques for highly diverse problems. These include tensor representations for operators based on nearest-neighbor interactions, construction of pseudoinverses for tensor-based reformulations of dimensionality reduction methods, and the approximation of transfer operators of dynamical systems. The results show that the tensor-train format enables us to compute low-rank approximations for various numerical problems as well as to reduce the memory consumption and the computational costs compared to classical approaches significantly. We demonstrate that tensor decompositions are a powerful tool for solving high-dimensional problems from various application areas.
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)
Tensors with unit Frobenius norm are fundamental objects in many fields, including scientific computing and quantum physics, which are able to represent normalized eigenvectors and pure quantum states. While the tensor train decomposition provides a powerful low-rank format for tackling high-dimensional problems, it does not intrinsically enforce the unit-norm constraint. To address this, we introduce the normalized tensor train (NTT) decomposition, which aims to approximate a tensor by unit-norm tensors in tensor train format. The low-rank structure of NTT decomposition not only saves storage and computational cost but also preserves the underlying unit-norm structure. We prove that the set of fixed-rank NTT tensors forms a smooth manifold, and the corresponding Riemannian geometry is derived, paving the way for geometric methods. We propose NTT-based methods for low-rank tensor recovery, high-dimensional eigenvalue problem, estimation of stabilizer rank, and calculation of the minimum output Rényi 2-entropy of quantum channels. Numerical experiments demonstrate the superior efficiency and scalability of the proposed NTT-based methods.
There has been a surge of interest in the study of multidimensional arrays, known as tensors. This is due to the fact that many real-world datasets can be represented as tensors. For example, colour images are naturally third-order tensors, which include two indices (or modes) for their spatial index, and one mode for colour. Also, a colour video is a fourth-order tensor comprised of frames, which are colour images, and an additional temporal index. Traditional tools for matrix analysis does not generalise so well in tensor analysis. The main issue is that tensors prescribe a natural structure, which is destroyed when they are vectorised. Many mathematical techniques such as principal component analysis (PCA) or linear discriminant analysis (LDA) used extensively in machine learning rely on vectorised samples of data. Additionally, since tensors may often be large in dimensionality and size, vectorising these samples and applying them to PCA or LDA may not lead to the most efficient results, and the computational time of the algorithms can increase significantly. This problem is known as the so-called curse of dimensionality.
Tensor decompositions and their interesting properties are needed to circumvent this problem. The Tucker (TD) or CANDECOMP/PARAFAC (CP) decompositions have been predominantly used for tensor-based machine learning and signal processing. Both utilise common factor matrices and a core tensor, which retains the dimensionality of the original tensor. A main problem with these type of decompositions is that they essentially rely on an unbalanced matricization scheme, which potentially converts a tensor to a highly unbalanced matrix, where the row size is attributed to always one mode and the column size is the product of the remaining modes. This method is not optimal for problems that rely on retaining as much correlations within the data, which is very important for tensor-based machine learning and signal processing.
In this thesis, we are interested in utilising the matrix product state (MPS) decomposition. MPS has the property that it can retain much of the correlations within a tensor because it is based on a balanced matricization scheme, which consists of permutations of matrix sizes that can investigate the different correlations amongst all modes of a tensor. Several new algorithms are proposed for tensor object classification, which demonstrate an MPS-based approach as an efficient method against other tensor-based approaches. Additionally, new methods for colour image and video completion are introduced, which outperform the current state-of-the-art tensor completion algorithms.