Low Rank Tensor Decompositions and Approximations

doi:10.1007/s40305-023-00455-7

Abstract

Abstract: There exist linear relations among tensor entries of low rank tensors. These linear relations can be expressed by multi-linear polynomials, which are called generating polynomials. We use generating polynomials to compute tensor rank decompositions and low rank tensor approximations. We prove that this gives a quasi-optimal low rank tensor approximation if the given tensor is sufficiently close to a low rank one.

Key words: Tensor, Decomposition, Rank, Approximation, Generating polynomial

CLC Number:

15A69
65F99

Jiawang Nie, Li Wang, Zequn Zheng. Low Rank Tensor Decompositions and Approximations[J]. Journal of the Operations Research Society of China, 2024, 12(4): 847-873.

TrendMD

References

[1] Landsberg, J.: Tensors: Geometry and Applications, Grad. Stud. Math., 128, AMS, Providence, RI, (2012)
[2] Lim, L.H.: Tensors and hypermatrices. In: Hogben, L. (ed.) Handbook of Linear Algebra, 2nd edn. CRC Press, Boca Raton (2013)
[3] Breiding, P., Vannieuwenhoven, N.: A Riemannian trust region method for the canonical tensor rank approximation problem. SIAM J. Optim. 28(3), 2435-2465(2018)
[4] Lathauwer, L., de Moor, B., Vandewalle, J.: Computation of the canonical decomposition by means of a simultaneous generalized Schur decomposition. SIAM J. Matrix Anal. Appl. 26(2), 295-327(2004)
[5] Lathauwer, L.: A link between the canonical decomposition in multilinear algebra and simultaneous matrix diagonalization. SIAM J. Matrix Anal. Appl. 28(3), 642-666(2006)
[6] Domanov, I., de Lathauwer, L.: Canonical polyadic decomposition of third-order tensors: Reduction to generalized eigenvalue decomposition. SIAM J. Matrix Anal. Appl. 35(2), 636-660(2014)
[7] Nie, J.: Generating polynomials and symmetric tensor decompositions. Found. Comput. Math. 17(2), 423-465(2017)
[8] Sorber, L., van Barel, M., de Lathauwer, L.: Optimization-based algorithms for tensor decompositions: canonical polyadic decomposition, decomposition in rank-(Lr, Lr, 1) terms, and a new generalization. SIAM J. Optim. 23(2), 695-720(2013)
[9] Telen, S., Vannieuwenhoven, N.: Normal forms for tensor rank decomposition. (2021) arXiv:2103.07411
[10] Cui, C.F., Dai, Y.H., Nie, J.: All real eigenvalues of symmetric tensors. SIAM J. Matrix Anal. Appl. 35(4), 1582-1601(2014)
[11] Fan, J., Nie, J., Zhou, A.: Tensor eigenvalue complementarity problems. Math. Progr. 170(2), 507-539(2018)
[12] Nie, J., Wang, L.: Semidefinite relaxations for best rank-1 tensor approximations. SIAM J. Matrix Anal. Appl. 35(3), 1155-1179(2014)
[13] Nie, J., Zhang, X.: Real eigenvalues of nonsymmetric tensors. Comput. Opt. Appl. 70(1), 1-32(2018)
[14] Nie, J., Yang, Z., Zhang, X.: A complete semidefinite algorithm for detecting copositive matrices and tensors. SIAM J. Optim. 28(4), 2902-2921(2018)
[15] Xiong, L., Chen, X., Huang, T.-K., Schneider, J., Carbonell, J. G.: Temporal collaborative filtering with bayesian probabilistic tensor factorization. In: Proceedings of the 2010 SIAM International Conference on Data Mining, 211-222, (2010)
[16] Dunlavy, D.M., Kolda, T.G., Acar, E.: Temporal link prediction using matrix and tensor factorizations. ACM Trans. Knowl. Discov. Data 5(2), 1-27(2011)
[17] Araujo, M., Papadimitriou, S., Gunnemann, S., Faloutsos, C., Basu, P., Swami, A., Papalexakis, E. E., Koutra, D.: Com2: fast automatic discovery of temporal (‘comet’) communities. In: Pacific-Asia Conference on Knowledge Discovery and Data Mining, 271-283, (2014)
[18] Nickel, M., Tresp, V., Kriegel, H.-P.: A three-way model for collective learning on multi-relational data. In: Proceedings of the 28th International Conference on Machine Learning, 809-816, (2011)
[19] Jenatton, R., Roux, N., Bordes, A., Obozinski, G.R.: A latent factor model for highly multi-relational data. Adv. Neural. Inf. Process. Syst. 25, 3167-3175(2012)
[20] Boden, B., Gunnemann, S., Hoffmann, H., Seidl, T.: Mining coherent subgraphs in multi-layer graphs with edge labels. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, 1258-1266, (2012)
[21] Kofidis, E., Regalia, P.A.: Tensor approximation and signal processing applications. Contemp. Math. 280, 103-134(2001)
[22] Pajarola, R., Suter, S. K., Ballester-Ripoll, R., Yang, H.: Tensor approximation for multidimensional and multivariate data. In: Anisotropy Across Fields and Scales, 73-98, (2021)
[23] Guo, B., Nie, J., Yang, Z.: Learning diagonal gaussian mixture models and incomplete tensor decompositions. Vietnam J. Math. (2021). https://doi.org/10.1007/s10013-021-00534-3
[24] Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455-500(2009)
[25] Nie, J., Yang, Z.: Hermitian tensor decompositions. SIAM J. Matrix Anal. Appl. 41(3), 1115-1144(2020)
[26] Friedland, S., Wang, L.: Spectral norm of a symmetric tensor and its computation. Math. Comput. 89, 2175-2215(2020)
[27] Qi, L., Hu, S.: Spectral norm and nuclear norm of a third order tensor (2019). arXiv:1909.01529
[28] de Silva, V., Lim, L.-H.: Tensor rank and the ill-posedness of the best low rank approximation problem. SIAM J. Matrix Anal. Appl. 30(3), 1084-1127(2008)
[29] Comon, P., Luciani, X., de Almeida, A.L.F.: Tensor decompositions, alternating least squares and other tales. J. Chemom. 23, 393-405(2009)
[30] Mao, X., Yuan, G., Yang, Y.: A self-adaptive regularized alternating least squares method for tensor decomposition problems. Anal. Appl. 18(01), 129-147(2020)
[31] Yang, Y.: The epsilon-alternating least squares for orthogonal low-rank tensor approximation and its global convergence. SIAM J. Matrix Anal. Appl. 41(4), 1797-1825(2020)
[32] Lathauwer, L., de Moor, B., Vandewalle, J.: On the best rank-1 and rank-(R₁, R₂, · · ·, R_n) approximation of higher-order tensors. SIAM J. Matrix Anal. Appl. 21(4), 1324-1342(2000)
[33] Guan, Y., Chu, M.T., Chu, D.: Convergence analysis of an svd-based algorithm for the best rank-1 tensor approximation. Linear Algebra Appl. 555, 53-69(2018)
[34] Friedland, S.,Tammali,V.:Low-rank approximation of tensors.In:NumericalAlgebra,MatrixTheory, Differential-Algebraic Equations and Control Theory. 377-411, Springer, (2015)
[35] Nie, J.: Low rank symmetric tensor approximations. SIAM J. Matrix Anal. Appl. 38(4), 1517-1540(2017)
[36] Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, Berlin (2013)
[37] Schafarevich, I.: Basic Algebraic Geometry I: Varieties in Projective Space. Springer-Verlag, Berlin (1988)
[38] Kruskal, J.B.: Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear Algebra Appl. 18(2), 95-138(1977)
[39] Chiantini, L., Ottaviani, G., Vannieuwenhoven, N.: Effective criteria for specific identifiability of tensors and forms. SIAM J. Matrix Anal. Appl. 38(2), 656-681(2017)
[40] Nie, J.: Nearly low rank tensors and their approximations (2014). arXiv:1412.7270
[41] Nie, J., Wang, L., Zheng, Z.: Higher Order Correlation Analysis for Multi-View Learning, Pacific Journal of Optimization, to appear, (2022)
[42] Demmel, J.: Applied Numerical Linear Algebra. SIAM, New Delhi (1997)
[43] Chatelin, F.: Eigenvalues of Matrices. SIAM, New Delhi (2012)
[44] Vervliet, N., Debals, O., de Lathauwer, L.: Tensorlab 3.0- numerical optimization strategies for large-scale constrained and coupled matrix/tensor factorization, In 201650th Asilomar Conference on Signals, Systems and Computers, 1733-1738, (2016)
[45] Leurgans, S.E., Ross, R.T., Abel, R.B.: A decomposition for three-way arrays. SIAM J. Matrix Anal. Appl. 14, 1064-1083(1993)
[46] Sanchez, E., Kowalski, B.R.: Tensorial resolution: a direct trilinear decomposition. J. Chemometrics 4, 29-45(1990)