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.
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.
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)
This paper introduces matrix product state (MPS) decomposition as a computational tool for extracting features of multidimensional data represented by higher-order tensors. Regardless of tensor order, MPS extracts its relevant features to the so-called core tensor of maximum order three which can be used for classification. Mainly based on a successive sequence of singular value decompositions (SVD), MPS is quite simple to implement without any recursive procedure needed for optimizing local tensors. Thus, it leads to substantial computational savings compared to other tensor feature extraction methods such as higher-order orthogonal iteration (HOOI) underlying the Tucker decomposition (TD). Benchmark results show that MPS can reduce significantly the feature space of data while achieving better classification performance compared to HOOI.
Big data consists of large multidimensional datasets that would often be difficult to analyze if working with the original tensor. There is a rising interest in the use of tensor decompositions for feature extraction due to the ability to extract necessary features from a large dimensional feature space. In this paper the matrix product state (MPS) decomposition is used for feature extraction of large tensors. The novelty of the paper is the introduction of a single core tensor obtained from the MPS that not only contains a significantly reduced feature space, but can perform classification with high accuracy without the need of feature selection methods.
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.
Many problems in computational neuroscience, neuroinformatics, pattern/image recognition, signal processing and machine learning generate massive amounts of multidimensional data with multiple aspects and high dimensionality. Tensors (i.e., multi-way arrays) provide often a natural and compact representation for such massive multidimensional data via suitable low-rank approximations. Big data analytics require novel technologies to efficiently process huge datasets within tolerable elapsed times. Such a new emerging technology for multidimensional big data is a multiway analysis via tensor networks (TNs) and tensor decompositions (TDs) which represent tensors by sets of factor (component) matrices and lower-order (core) tensors. Dynamic tensor analysis allows us to discover meaningful hidden structures of complex data and to perform generalizations by capturing multi-linear and multi-aspect relationships. We will discuss some fundamental TN models, their mathematical and graphical descriptions and associated learning algorithms for large-scale TDs and TNs, with many potential applications including: Anomaly detection, feature extraction, classification, cluster analysis, data fusion and integration, pattern recognition, predictive modeling, regression, time series analysis and multiway component analysis. Keywords: Large-scale HOSVD, Tensor decompositions, CPD, Tucker models, Hierarchical Tucker (HT) decomposition, low-rank tensor approximations (LRA), Tensorization/Quantization, tensor train (TT/QTT) - Matrix Product States (MPS), Matrix Product Operator (MPO), DMRG, Strong Kronecker Product (SKP).
Quantification of stochastic or quantum systems by a joint probability density or wave function is a notoriously difficult computational problem, since the solution depends on all possible states (or realizations) of the system. Due to this combinatorial flavor, even a system containing as few as ten particles may yield as many as 1010 discretized states. None of even modern supercomputers are capable to cope with this curse of dimensionality straightforwardly, when the amount of quantum particles, for example, grows up to more or less interesting order of hundreds. A traditional approach for a long time was to avoid models formulated in terms of probabilistic functions, and simulate particular system realizations in a randomized process. Since different times in different communities, data-sparse methods came into play. Generally, they aim to define all data points indirectly, by a map from a low amount of representers, and recast all operations (e.g. linear system solution) from the initial data to the effective parameters. The most advanced techniques can be applied (at least, tried) to any given array, and do not rely explicitly on its origin. The current work contributes further progress to this area in the particular direction: tensor product methods for separation of variables. The separation of variables has a long history, and is based on the following elementary concept: a function of many variables may be expanded as a product of univariate functions. On the discrete level, a function is encoded by an array of its values, or a tensor. Therefore, instead of a huge initial array, the separation of variables allows to work with univariate factors with much less efforts. The dissertation contains a short overview of existing tensor representations: canonical PARAFAC, Hierarchical Tucker, Tensor Train (TT) formats, as well as the artificial tensorisation, resulting in the Quantized Tensor Train (QTT) approximation method. The contribution of the dissertation consists in both theoretical constructions and practical numerical algorithms for high-dimensional models, illustrated on the examples of the Fokker-Planck and the chemical master equations. Both arise from stochastic dynamical processes in multiconfigurational systems, and govern the evolution of the probability function in time. A special focus is put on time propagation schemes and their properties related to tensor product methods. We show that these applications yield large-scale systems of linear equations, and prove analytical separable representations of the involved functions and operators. We propose a new combined tensor format (QTT-Tucker), which descends from the TT format (hence TT algorithms may be generalized smoothly), but provides complexity reduction by an order of magnitude. We develop a robust iterative solution algorithm, constituting most advantageous properties of the classical iterative methods from numerical analysis and alternating density matrix renormalization group (DMRG) techniques from quantum physics. Numerical experiments confirm that the new method is preferable to DMRG algorithms. It is as fast as the simplest alternating schemes, but as reliable and accurate as the Krylov methods in linear algebra.