Tensor decomposition explained

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]

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:

• Tensor rank decomposition;^[6]
• Higher-order singular value decomposition;^[7]
• Tucker decomposition;
• matrix product states, and operators or tensor trains;
• Online Tensor Decompositions^{[8] [9] [10]}
• hierarchical Tucker decomposition;^[11]
• block term decomposition^{[12] [13]}

Notation

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

Table of symbols and their description.

Symbols	Definition
{a, {\bf a},{\bf a} ^{T,A,{lA}}}	scalar, vector, row, matrix, tensor
{\bf a} = {vec(.)}	vectorizing either a matrix or a tensor
{\bf A} _{[m]}	matrixized tensor l A
x _{m}	mode-m product

Introduction

A multi-way graph with K perspectives is a collection of K matrices

{X _{1,X} _{2.....X} _{K}} 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.

Notes and References

1. MAO. Vasilescu. D. Terzopoulos. 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 . en . 51 . 3 . 455–500 . 10.1137/07070111X . 2009SIAMR..51..455K . 16074195 . 0036-1445.
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 . 10.1109/TSP.2017.2690524 . 1607.01668 . 2017ITSP...65.3551S . 16321768 . 1053-587X.
4. 2013-05-01. General tensor decomposition, moment matrices and applications. Journal of Symbolic Computation. en. 52. 51–71. 10.1016/j.jsc.2012.05.012. 0747-7171. 1105.1229. Bernardi . A. . Brachat . J. . Comon . P. . Mourrain . B. . 14181289 .
5. Rabanser . Stephan . Shchur . Oleksandr . Günnemann . Stephan . 2017 . Introduction to Tensor Decompositions and their Applications in Machine Learning . stat.ML . 1711.10781.
6. Papalexakis . Evangelos E. . 2016-06-30 . Automatic Unsupervised Tensor Mining with Quality Assessment . Proceedings of the 2016 SIAM International Conference on Data Mining . en . Society for Industrial and Applied Mathematics . 711–719 . 10.1137/1.9781611974348.80 . 1503.03355 . 978-1-61197-434-8. 10147789 .
7. Book: M.A.O.. Vasilescu . D.. Terzopoulos . Multilinear Analysis of Image Ensembles: TensorFaces . Lecture Notes in Computer Science; (Presented at Proc. 7th European Conference on Computer Vision (ECCV'02), Copenhagen, Denmark) . Springer, Berlin, Heidelberg . 2350 . 10.1007/3-540-47969-4_30 . 978-3-540-43745-1 . 2002 .
8. Gujral . Ekta . Pasricha . Ravdeep . Papalexakis . Evangelos E. . Martin . Dino . Ester . Pedreschi . SamBaTen: Sampling-based Batch Incremental Tensor Decomposition. Proceedings of the 2018 SIAM International Conference on Data Mining . 7 May 2018 . 10.1137/1.9781611975321. 978-1-61197-532-1 . 21674935 . 10536/DRO/DU:30109588 . free .
9. Book: Gujral . Ekta . Papalexakis . Evangelos E. . 2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA) . OnlineBTD: Streaming Algorithms to Track the Block Term Decomposition of Large Tensors . 9 October 2020 . 168–177 . 10.1109/DSAA49011.2020.00029. 978-1-7281-8206-3 . 227123356 .
10. Gujral . Ekta . 2022 . Modeling and Mining Multi-Aspect Graphs With Scalable Streaming Tensor Decomposition . cs.SI . 2210.04404.
11. M.A.O.. Vasilescu. E.. Kim. 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 . 1911.04180 .
12. De Lathauwer. Lieven . Decompositions of a Higher-Order Tensor in Block Terms—Part II: Definitions and Uniqueness . SIAM Journal on Matrix Analysis and Applications . 2008 . 30 . 3 . 1033–1066 . en . 10.1137/070690729.
13. Book: Gujral . Ekta . Pasricha . Ravdeep . Papalexakis . Evangelos . Proceedings of the Web Conference 2020 . Beyond Rank-1: Discovering Rich Community Structure in Multi-Aspect Graphs . 2020-04-20 . https://dl.acm.org/doi/10.1145/3366423.3380129 . en . Taipei Taiwan . ACM . 452–462 . 10.1145/3366423.3380129 . 978-1-4503-7023-3. 212745714 .