Tensor decomposition

Last updated

In multilinear algebra, a tensor decomposition is any scheme for expressing a "data tensor" (M-way array) as a sequence of elementary operations acting on other, often simpler tensors. [1] [2] [3] Many tensor decompositions generalize some matrix decompositions. [4]

Contents

Tensors are generalizations of matrices to higher dimensions (or rather to higher orders, i.e. the higher number of dimensions) and can consequently be treated as multidimensional fields. [1] [5] The main tensor decompositions are:

Notation

This section introduces basic notations and operations that are widely used in the field.

Table of symbols and their description.
SymbolsDefinition
scalar, vector, row, matrix, tensor
vectorizing either a matrix or a tensor
matrixized tensor
mode-m product

Introduction

A multi-way graph with K perspectives is a collection of K matrices with dimensions I × J (where I, J are the number of nodes). This collection of matrices is naturally represented as a tensor X of size I × J × K. In order to avoid overloading the term “dimension”, we call an I × J × K tensor a three “mode” tensor, where “modes” are the numbers of indices used to index the tensor.

Related Research Articles

<span class="mw-page-title-main">Principal component analysis</span> Method of data analysis

Principal component analysis (PCA) is a linear dimensionality reduction technique with applications in exploratory data analysis, visualization and data preprocessing.

In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix:

Dimensionality reduction, or dimension reduction, is the transformation of data from a high-dimensional space into a low-dimensional space so that the low-dimensional representation retains some meaningful properties of the original data, ideally close to its intrinsic dimension. Working in high-dimensional spaces can be undesirable for many reasons; raw data are often sparse as a consequence of the curse of dimensionality, and analyzing the data is usually computationally intractable. Dimensionality reduction is common in fields that deal with large numbers of observations and/or large numbers of variables, such as signal processing, speech recognition, neuroinformatics, and bioinformatics.

Non-negative matrix factorization, also non-negative matrix approximation is a group of algorithms in multivariate analysis and linear algebra where a matrix V is factorized into (usually) two matrices W and H, with the property that all three matrices have no negative elements. This non-negativity makes the resulting matrices easier to inspect. Also, in applications such as processing of audio spectrograms or muscular activity, non-negativity is inherent to the data being considered. Since the problem is not exactly solvable in general, it is commonly approximated numerically.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

<span class="mw-page-title-main">Computational complexity of mathematical operations</span> Algorithmic runtime requirements for common math procedures

The following tables list the computational complexity of various algorithms for common mathematical operations.

In multilinear algebra, the tensor rank decomposition or the decomposition of a tensor is the decomposition of a tensor in terms of a sum of minimum tensors. This is an open problem.

In multilinear algebra, the higher-order singular value decomposition (HOSVD) of a tensor is a specific orthogonal Tucker decomposition. It may be regarded as one type of generalization of the matrix singular value decomposition. It has applications in computer vision, computer graphics, machine learning, scientific computing, and signal processing. Some aspects can be traced as far back as F. L. Hitchcock in 1928, but it was L. R. Tucker who developed for third-order tensors the general Tucker decomposition in the 1960s, further advocated by L. De Lathauwer et al. in their Multilinear SVD work that employs the power method, or advocated by Vasilescu and Terzopoulos that developed M-mode SVD a parallel algorithm that employs the matrix SVD.

In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the fastest algorithm for matrix multiplication is of major practical relevance.

<span class="mw-page-title-main">Multilinear subspace learning</span> Approach to dimensionality reduction

Multilinear subspace learning is an approach for disentangling the causal factor of data formation and performing dimensionality reduction. The Dimensionality reduction can be performed on a data tensor that contains a collection of observations have been vectorized, or observations that are treated as matrices and concatenated into a data tensor. Here are some examples of data tensors whose observations are vectorized or whose observations are matrices concatenated into data tensor images (2D/3D), video sequences (3D/4D), and hyperspectral cubes (3D/4D).

Multilinear principal component analysis (MPCA) is a multilinear extension of principal component analysis (PCA) that is used to analyze M-way arrays, also informally referred to as "data tensors". M-way arrays may be modeled by linear tensor models, such as CANDECOMP/Parafac, or by multilinear tensor models, such as multilinear principal component analysis (MPCA) or multilinear independent component analysis (MICA). The origin of MPCA can be traced back to the tensor rank decomposition introduced by Frank Lauren Hitchcock in 1927; to the Tucker decomposition; and to Peter Kroonenberg's "3-mode PCA" work. In 2000, De Lathauwer et al. restated Tucker and Kroonenberg's work in clear and concise numerical computational terms in their SIAM paper entitled "Multilinear Singular Value Decomposition", (HOSVD) and in their paper "On the Best Rank-1 and Rank-(R1, R2, ..., RN ) Approximation of Higher-order Tensors".

Multiway data analysis is a method of analyzing large data sets by representing a collection of observations as a multiway array, . The proper choice of data organization into (C+1)-way array, and analysis techniques can reveal patterns in the underlying data undetected by other methods.

Robust Principal Component Analysis (RPCA) is a modification of the widely used statistical procedure of principal component analysis (PCA) which works well with respect to grossly corrupted observations. A number of different approaches exist for Robust PCA, including an idealized version of Robust PCA, which aims to recover a low-rank matrix L0 from highly corrupted measurements M = L0 +S0. This decomposition in low-rank and sparse matrices can be achieved by techniques such as Principal Component Pursuit method (PCP), Stable PCP, Quantized PCP, Block based PCP, and Local PCP. Then, optimization methods are used such as the Augmented Lagrange Multiplier Method (ALM), Alternating Direction Method (ADM), Fast Alternating Minimization (FAM), Iteratively Reweighted Least Squares (IRLS ) or alternating projections (AP).

Finsler's lemma is a mathematical result named after Paul Finsler. It states equivalent ways to express the positive definiteness of a quadratic form Q constrained by a linear form L. Since it is equivalent to another lemmas used in optimization and control theory, such as Yakubovich's S-lemma, Finsler's lemma has been given many proofs and has been widely used, particularly in results related to robust optimization and linear matrix inequalities.

<span class="mw-page-title-main">Mode-k flattening</span> Mathematical operation

In multilinear algebra, mode-m flattening, also known as matrixizing, matricizing, or unfolding, is an operation that reshapes a multi-way array into a matrix denoted by .

Tamara G. Kolda is an American applied mathematician and former Distinguished Member of Technical Staff at Sandia National Laboratories. She is noted for her contributions in computational science, multilinear algebra, data mining, graph algorithms, mathematical optimization, parallel computing, and software engineering. She is currently a member of the SIAM Board of Trustees and served as associate editor for both the SIAM Journal on Scientific Computing and the SIAM Journal on Matrix Analysis and Applications.

Shmuel Friedland is an Israeli-American mathematician.

<span class="mw-page-title-main">Tensor network</span> Mathematical wave functions

Tensor networks or tensor network states are a class of variational wave functions used in the study of many-body quantum systems. Tensor networks extend one-dimensional matrix product states to higher dimensions while preserving some of their useful mathematical properties.

<span class="mw-page-title-main">Knowledge graph embedding</span> Dimensionality reduction of graph-based semantic data objects [machine learning task]

In representation learning, knowledge graph embedding (KGE), also referred to as knowledge representation learning (KRL), or multi-relation learning, is a machine learning task of learning a low-dimensional representation of a knowledge graph's entities and relations while preserving their semantic meaning. Leveraging their embedded representation, knowledge graphs (KGs) can be used for various applications such as link prediction, triple classification, entity recognition, clustering, and relation extraction.

Tensor informally refers in machine learning to two different concepts that organize and represent data. Data may be organized in a multidimensional array (M-way array) that is informally referred to as a "data tensor"; however in the strict mathematical sense, a tensor is a multilinear mapping over a set of domain vector spaces to a range vector space. Observations, such as images, movies, volumes, sounds, and relationships among words and concepts, stored in an M-way array ("data tensor") may be analyzed either by artificial neural networks or tensor methods.

References

  1. 1 2 Vasilescu, MAO; Terzopoulos, D. "Multilinear (tensor) image synthesis, analysis, and recognition [exploratory dsp]". IEEE Signal Processing Magazine. 24 (6): 118–123.
  2. Kolda, Tamara G.; Bader, Brett W. (2009-08-06). "Tensor Decompositions and Applications". SIAM Review. 51 (3): 455–500. Bibcode:2009SIAMR..51..455K. doi:10.1137/07070111X. ISSN   0036-1445. S2CID   16074195.
  3. Sidiropoulos, Nicholas D.; De Lathauwer, Lieven; Fu, Xiao; Huang, Kejun; Papalexakis, Evangelos E.; Faloutsos, Christos (2017-07-01). "Tensor Decomposition for Signal Processing and Machine Learning". IEEE Transactions on Signal Processing. 65 (13): 3551–3582. arXiv: 1607.01668 . Bibcode:2017ITSP...65.3551S. doi:10.1109/TSP.2017.2690524. ISSN   1053-587X. S2CID   16321768.
  4. Bernardi, A.; Brachat, J.; Comon, P.; Mourrain, B. (2013-05-01). "General tensor decomposition, moment matrices and applications". Journal of Symbolic Computation. 52: 51–71. arXiv: 1105.1229 . doi:10.1016/j.jsc.2012.05.012. ISSN   0747-7171. S2CID   14181289.
  5. Rabanser, Stephan; Shchur, Oleksandr; Günnemann, Stephan (2017). "Introduction to Tensor Decompositions and their Applications in Machine Learning". arXiv: 1711.10781 [stat.ML].
  6. Papalexakis, Evangelos E. (2016-06-30). "Automatic Unsupervised Tensor Mining with Quality Assessment". Proceedings of the 2016 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics: 711–719. arXiv: 1503.03355 . doi:10.1137/1.9781611974348.80. ISBN   978-1-61197-434-8. S2CID   10147789.
  7. Vasilescu, M.A.O.; Terzopoulos, D. (2002). Multilinear Analysis of Image Ensembles: TensorFaces (PDF). Lecture Notes in Computer Science; (Presented at Proc. 7th European Conference on Computer Vision (ECCV'02), Copenhagen, Denmark). Vol. 2350. Springer, Berlin, Heidelberg. doi:10.1007/3-540-47969-4_30. ISBN   978-3-540-43745-1.
  8. Gujral, Ekta; Pasricha, Ravdeep; Papalexakis, Evangelos E. (7 May 2018). Ester, Martin; Pedreschi, Dino (eds.). "SamBaTen: Sampling-based Batch Incremental Tensor Decomposition". Proceedings of the 2018 SIAM International Conference on Data Mining. doi:10.1137/1.9781611975321. hdl: 10536/DRO/DU:30109588 . ISBN   978-1-61197-532-1. S2CID   21674935.
  9. Gujral, Ekta; Papalexakis, Evangelos E. (9 October 2020). "OnlineBTD: Streaming Algorithms to Track the Block Term Decomposition of Large Tensors". 2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA). pp. 168–177. doi:10.1109/DSAA49011.2020.00029. ISBN   978-1-7281-8206-3. S2CID   227123356.
  10. Gujral, Ekta (2022). "Modeling and Mining Multi-Aspect Graphs With Scalable Streaming Tensor Decomposition". arXiv: 2210.04404 [cs.SI].
  11. 1 2 Vasilescu, M.A.O.; Kim, E. (2019). Compositional Hierarchical Tensor Factorization: Representing Hierarchical Intrinsic and Extrinsic Causal Factors. In The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD’19): Tensor Methods for Emerging Data Science Challenges. arXiv: 1911.04180 .
  12. De Lathauwer, Lieven (2008). "Decompositions of a Higher-Order Tensor in Block Terms—Part II: Definitions and Uniqueness". SIAM Journal on Matrix Analysis and Applications. 30 (3): 1033–1066. doi:10.1137/070690729.
  13. Vasilescu, M.A.O.; Kim, E.; Zeng, X.S. (2021), "CausalX: Causal eXplanations and Block Multilinear Factor Analysis", Conference Proc. of the 2020 25th International Conference on Pattern Recognition (ICPR 2020), pp. 10736–10743, arXiv: 2102.12853 , doi:10.1109/ICPR48806.2021.9412780, ISBN   978-1-7281-8808-9, S2CID   232046205
  14. Gujral, Ekta; Pasricha, Ravdeep; Papalexakis, Evangelos (2020-04-20). "Beyond Rank-1: Discovering Rich Community Structure in Multi-Aspect Graphs". Proceedings of the Web Conference 2020. Taipei Taiwan: ACM. pp. 452–462. doi:10.1145/3366423.3380129. ISBN   978-1-4503-7023-3. S2CID   212745714.