Algebraic methods for tensor data. (English) Zbl 1457.15026
Summary: We develop algebraic methods for computations with tensor data. We give three applications: extracting features that are invariant under the orthogonal symmetries in each of the modes, approximation of the tensor spectral norm, and amplification of low rank tensor structure. We introduce colored Brauer diagrams, which are used for algebraic computations and in analyzing their computational complexity. We present numerical experiments whose results show that the performance of the alternating least squares algorithm for rank 1 approximations for tensors can be improved using tensor amplification.
MSC:
| 15A72 | Vector and tensor algebra, theory of invariants |
| 15A69 | Multilinear algebra, tensor calculus |
| 22E45 | Representations of Lie and linear algebraic groups over real fields: analytic methods |
| 20G05 | Representation theory for linear algebraic groups |
Online Encyclopedia of Integer Sequences:
Double factorial of odd numbers: a(n) = (2*n-1)!! = 1*3*5*...*(2*n-1).Number of 3-edge-colored connected trivalent graphs with 2n nodes.
References:
| [1] | B. W. Bader, T. G. Kolda, et al., MATLAB Tensor Toolbox, Version 2.6, https://www.tensortoolbox.org, 2015. |
| [2] | R. Brauer, On algebras which are connected with the semisimple continuous groups, Ann. Math., 38 (1937), pp. 857-872. · Zbl 0017.39105 |
| [3] | D. Callan, A Combinatorial Survey of Identities for the Double Factorial, preprint, arXiv:0906.1317, 2009. |
| [4] | E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), https://doi.org/10.1007/s10208-009-9045-5. · Zbl 1219.90124 |
| [5] | E. J. Candès and T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Trans. Inform. Theory, 56 (2010), https://doi.org/10.1109/TIT.2010.2044061. · Zbl 1366.15021 |
| [6] | H. Derksen, On the nuclear norm and the singular value decomposition of tensor, Found. Comput. Math., 16 (2016), pp. 779-811. · Zbl 1343.15016 |
| [7] | S. Friedland and L.-H. Lim, Nuclear norm of higher-order tensors, Math. Comp., 87 (2018), pp. 1255-1281. · Zbl 1383.15018 |
| [8] | R. Goodman and N. R. Wallach, Representations and Invariants of Classical Groups, Cambridge University Press, Cambridge, 1998. · Zbl 0901.22001 |
| [9] | A. Grothendieck, Produits tensoriels topologiques et espaces nucléares, Mem. Amer. Math. Soc., (1955). · Zbl 0064.35501 |
| [10] | J. H\aastad, Tensor rank is NP-complete, J. Algorithms, 11 (1990), pp. 644-654. · Zbl 0716.65043 |
| [11] | J. H\aastad, Tensor Rank Is NP-Complete, Automata, Languages, and Programming (Stresa, 1989), Lecture Notes in Comput. Sci. 372, Springer, Berlin, 1989, pp. 451-460. |
| [12] | C. J. Hillar and L.-H. Lim, Most tensor problems are NP-hard, J. ACM, 60 (2013), Art. 45. · Zbl 1281.68126 |
| [13] | F. L. Hitchcock, The expression of a tensor or a polyadic as a sum of products, J. Math. Phys., 6 (1927), pp. 164-189. · JFM 53.0095.01 |
| [14] | F. L. Hitchcock, Multiple invariants and generalized rank of a p-way matrix or tensor, J. Math. Phys., 7 (1928), pp. 39-79. · JFM 53.0097.01 |
| [15] | T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Rev., 51 (2009), pp. 455-500. · Zbl 1173.65029 |
| [16] | X. Kong, A concise proof to the spectral and nuclear norm bounds through tensor partitions, Open Math., 17 (2019), pp. 365-373. · Zbl 1430.15017 |
| [17] | J. M. Landsberg, Tensors: Geometry and Applications, Grad. Stud. Math. 128, American Mathematical Society, Providence, RI, 2012. · Zbl 1238.15013 |
| [18] | S. Lang, Algebra, 3rd ed., Grad. Texts in Math. 211, Springer-Verlag, New York, 2002. · Zbl 0984.00001 |
| [19] | L. De Lathauwer and B. De Moor, A Multilinear Singular Value Decomposition, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1253-1278, https://doi.org/10.1137/S0895479896305696. · Zbl 0962.15005 |
| [20] | Z. Li, The spectral norm and the nuclear norm of a tensor based on tensor partitions, Matrix Anal. Appl., 37 (2016), pp. 1440-1452. · Zbl 1348.15018 |
| [21] | Z. Li, Y. Nakatsukasa, et al., On orthogonal tensors and best rank-one approximation ratio, SIAM J. Matrix Anal. Appl., 39 (2017), https://doi.org/10.1137/17M1144349. · Zbl 1390.15081 |
| [22] | OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A001147, 2020. · Zbl 1044.11108 |
| [23] | OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A002831, 2019. |
| [24] | V. L. Popov and E. B. Vinberg, Invariant Theory, Encyclopaedia Math. Sci. 55, A. Parshin and I. R. Shafarevich, eds., Springer-Verlag, Berlin, 1994. · Zbl 0788.00015 |
| [25] | L. Qi and S. Hu, Spectral Norm and Nuclear Norm of a Third Order Tensor, preprint, arXiv:1909.01529, 2019. |
| [26] | A. Ramlatchan, M. Yang, et al., A survey of matrix completion methods for recommendation systems, Big Data Mining Analytics, 1 (2018), pp. 308-323. |
| [27] | R. Schatten, A Theory of Cross-Spaces, Princeton University Press, Princeton, NJ, 1950. · Zbl 0041.43502 |
| [28] | A. P. Da Silva, P. Comon, et al., A finite algorithm to compute rank-\(1\) tensor approximations, IEEE Signal Process. Lett., 23 (2016), pp. 959-963. |
| [29] | V. De Silva and L.-H. Lim, Tensor rank and the ill-posedness of the best low-rank approximation problem, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 1084-1127. · Zbl 1167.14038 |
| [30] | L. R. Tucker, Some mathematical notes on three-mode factor analysis, Psychometrika, 31 (1966), pp. 279-311, https://doi.org/10.1007/BF02289464. |
| [31] | H. Weyl, The Classical Groups. Their Invariants and Representations, Princeton University Press, Princeton, NJ, 1939. · Zbl 0020.20601 |
| [32] | L. K. Williams, Invariant Polynomials on Tensors under the Action of a Product of Orthogonal Groups, Ph.D. Thesis, University of Wisconsin, Milwaukee, 2013. |
| [33] | M. Yuan and C. Zhang, On Tensor Completion via Nuclear Norm Minimization, Found. Comput. Math., 16 (2016), pp. 1031-1068, https://doi.org/10.1007/s10208-015-9269-5. · Zbl 1378.90066 |
| [34] | T. Zhang and G. H. Golub, Rank-One Approximation to High Order Tensors, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 534-550, https://doi.org/10.1137/S0895479899352045. · Zbl 1001.65036 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
