Real eigenvalues of nonsymmetric tensors. (English) Zbl 1397.65057
The authors first define the space of \(m\)-order \(n\)-dimensional tensors \(T^m(\mathbb R^n)\). For a tensor \(\mathcal A\in T^m(\mathbb R^n)\), they define a real \(Z\)-eigenpair and a real \(H\)-eigenpair of \(\mathcal A\). There are different techniques for computing these eigenpairs depending on the properties of \(T^m(\mathbb R^n)\).
The authors focus on the computation of real \(Z\)- and \(H\)-eigenvalues and corresponding eigenvectors. For a symmetric tensor, the computation of real \(Z\)- and \(H\)-eigenpairs is discussed in quite a lot of papers (references are given in the paper). The situation is different for the case of real nonsymmetric tensors.
The authors propose numerical methods for computing all real \(Z\)-eigenvalues (if there are finitely many ones) and all real \(H\)-eigenvalues (those are always a finite number).
As a motivation, the authors study an \(m\)th order Markov chain that fits observed data by an \(m\)-order nonsymmetric tensor \(\mathcal P\in T^m(\mathbb R^n)\), the so called transition probability tensor. The stationary probability distributions can be obtained by computing the \(Z\)-eigenvalues of the nonsymmetric tensor \(\mathcal P\).
In Section 3, the authors reformulate the \(Z\)-eigenvalue computation as a polynomial optimization problem. The set of \(Z\)-eigenvalues of \(\mathcal A\) is denoted \(Z(\mathbb R,\mathcal A)\). If \(Z(\mathbb R,\mathcal A)\) is a finite set the \(Z\)-eigenvalues will be computed monotonically \(\lambda_1<\lambda_2<\dots <\lambda_N\), from the smallest to the largest one. The properties of the set \(Z(\mathbb R,\mathcal A)\) are formulated and proven. The authors propose Lasserre-type semidefinite relaxations for computing \(Z\)-eigenvalues. If there are finitely many real \(Z\)-eigenvalues, each of them can be computed by solving a finite sequence of semidefinite relaxations. Section 4 proposes Lasserre-type semidefinite relaxations for computing all \(H\)-eigenvalues. Each of them can be also computed by solving a finite sequence of semidefinite relaxations.
The paper contains algorithms for computing \(Z\) and \(H\)-eigenvalues for nonsymmetric tensors using Lasserre-type semidefinite relaxations. Many examples are provided. The authors also include a comparison with other methods.
The authors focus on the computation of real \(Z\)- and \(H\)-eigenvalues and corresponding eigenvectors. For a symmetric tensor, the computation of real \(Z\)- and \(H\)-eigenpairs is discussed in quite a lot of papers (references are given in the paper). The situation is different for the case of real nonsymmetric tensors.
The authors propose numerical methods for computing all real \(Z\)-eigenvalues (if there are finitely many ones) and all real \(H\)-eigenvalues (those are always a finite number).
As a motivation, the authors study an \(m\)th order Markov chain that fits observed data by an \(m\)-order nonsymmetric tensor \(\mathcal P\in T^m(\mathbb R^n)\), the so called transition probability tensor. The stationary probability distributions can be obtained by computing the \(Z\)-eigenvalues of the nonsymmetric tensor \(\mathcal P\).
In Section 3, the authors reformulate the \(Z\)-eigenvalue computation as a polynomial optimization problem. The set of \(Z\)-eigenvalues of \(\mathcal A\) is denoted \(Z(\mathbb R,\mathcal A)\). If \(Z(\mathbb R,\mathcal A)\) is a finite set the \(Z\)-eigenvalues will be computed monotonically \(\lambda_1<\lambda_2<\dots <\lambda_N\), from the smallest to the largest one. The properties of the set \(Z(\mathbb R,\mathcal A)\) are formulated and proven. The authors propose Lasserre-type semidefinite relaxations for computing \(Z\)-eigenvalues. If there are finitely many real \(Z\)-eigenvalues, each of them can be computed by solving a finite sequence of semidefinite relaxations. Section 4 proposes Lasserre-type semidefinite relaxations for computing all \(H\)-eigenvalues. Each of them can be also computed by solving a finite sequence of semidefinite relaxations.
The paper contains algorithms for computing \(Z\) and \(H\)-eigenvalues for nonsymmetric tensors using Lasserre-type semidefinite relaxations. Many examples are provided. The authors also include a comparison with other methods.
Reviewer: Drahoslava Janovská (Praha)
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 15A69 | Multilinear algebra, tensor calculus |
| 90C22 | Semidefinite programming |
Software:
GloptiPolyReferences:
| [1] | Berchtold, A., Raftery, A.: The mixture transition distribution model for high-order Markov chains and non-Gaussian time series. Stat. Sci. 17, 328-356 (2002) · Zbl 1013.62088 · doi:10.1214/ss/1042727943 |
| [2] | Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry. Springer, New York (1998) · Zbl 0912.14023 · doi:10.1007/978-3-662-03718-8 |
| [3] | Cartwright, D., Stumfels, B.: The number of eigenvalues of a tensor. Linear Algebra Appl. 438, 942-952 (2013) · Zbl 1277.15007 · doi:10.1016/j.laa.2011.05.040 |
| [4] | Chang, K., Pearson, K., Zhang, T.: Perron-Frobenius theorem for nonnegative tensors. Commun. Math. Sci. 6, 507-520 (2008) · Zbl 1147.15006 · doi:10.4310/CMS.2008.v6.n2.a12 |
| [5] | Cui, C., Dai, Y., Nie, J.: All real eigenvalues of symmetric tensors. SIAM J. Matrix Anal. Appl. 35, 1582-1601 (2014) · Zbl 1312.65053 · doi:10.1137/140962292 |
| [6] | Curto, R., Fialkow, L.: Truncated K-moment problems in several variables. J. Oper. Theory 54, 189-226 (2005) · Zbl 1119.47304 |
| [7] | Decarolis, F., Mayer, R., Santamaria, M.: Homotopy continuation methods: an algorithm for the fixed point and Newton homotopy methods with some examples. http://home.chicago.edu/ fdc/H-topy.pdf · Zbl 1023.90064 |
| [8] | Demmel, J.: Applied Numerical Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia (1997) · Zbl 0879.65017 · doi:10.1137/1.9781611971446 |
| [9] | De Lathauwer, L., De Moor, B., Vandewalle, J.: On the best rank-1 and rank-(R1, R \(2,\cdots \), RN) approximation of higher-order tensors. SIAM J. Matrix Anal. Appl. 21, 1324-1342 (2000) · Zbl 0958.15026 · doi:10.1137/S0895479898346995 |
| [10] | Henrion, D., Lasserre, J.B.: Detecting global optimality and extracting solutions in GloptiPoly. In: Positive Polynomials in Control. Lecture Notes in Control and Information Science, vol. 312, pp. 293-310. Springer, Berlin (2005) · Zbl 1119.93301 |
| [11] | Henrion, D., Lasserre, J.B., Lofberg, Y.: GloptiPoly 3: moments, optimization and semidfinite programming. Optim. Methods Softw. 24, 761-779 (2009) · Zbl 1178.90277 · doi:10.1080/10556780802699201 |
| [12] | Hillar, C., Lim, L.H.: Most tensor problems are NP-hard. J. ACM 60(6), 45 (2013) · Zbl 1281.68126 · doi:10.1145/2512329 |
| [13] | Hu, S., Qi, L.: Convergence of a second order Markov chain. Appl. Math. Comput. 241, 183-192 (2014) · Zbl 1334.60143 |
| [14] | Ishteva, M., Absil, P.-A., Van Dooren, P.: Jacobi algorithm for the best low multilinear rank approximation of symmetric tensors. SIAM J. Matrix Anal. Appl. 34, 651-672 (2013) · Zbl 1273.15031 · doi:10.1137/11085743X |
| [15] | Kolda, T.G., Mayo, J.R.: Shifted power method for computing tensor eigenpairs. SIAM J. Matrix Anal. Appl. 32, 1095-1124 (2011) · Zbl 1247.65048 · doi:10.1137/100801482 |
| [16] | Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796-817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802 |
| [17] | Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2009) · doi:10.1142/p665 |
| [18] | Laurent, M.; Putinar, M. (ed.); Sullivant, S. (ed.), Sums of squares, moment matrices and optimization over polynomials, No. 149, 157-270 (2009), New York · Zbl 1163.13021 · doi:10.1007/978-0-387-09686-5_7 |
| [19] | Li, W., Ng, M.: On the limiting probability distribution of a transition probability tensor. Linear Multilinear Algebra 62, 362-385 (2014) · Zbl 1301.60049 · doi:10.1080/03081087.2013.777436 |
| [20] | Li, X., Ng, M., Ye, Y.: Finding stationary probability vector of a transition probability tensor arising from a higher-order Markov chain. Technical Report, Department of Mathematics, Hong Kong Baptist University (2011). http://www.math.hkbu.edu.hk/ mng/tensor-research/report1.pdf · Zbl 1305.65134 |
| [21] | Lim, L.H.: Singular values and eigenvalues of tensors: a variational approach. In: Proceedings of IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP’05), vol. 1, pp. 129-132 (2005) · Zbl 1197.65036 |
| [22] | Lim, L-H; Hogben, L. (ed.), Tensors and hypermatrices (2013), Boca Raton |
| [23] | Ng, M., Qi, L., Zhou, G.: Finding the largest eigenvalue of a non-negative tensor. SIAM J. Matrix Anal. Appl. 31, 1090-1099 (2009) · Zbl 1197.65036 · doi:10.1137/09074838X |
| [24] | Nie, J., Wang, L.: Semidefinite relaxations for best rank-1 tensor approximations. SIAM J. Matrix Anal. Appl. 35, 1155-1179 (2014) · Zbl 1305.65134 · doi:10.1137/130935112 |
| [25] | Nie, J.: Polynomial optimization with real varieties. SIAM J. Optim. 23, 1634-1646 (2013) · Zbl 1286.65079 · doi:10.1137/120898772 |
| [26] | Nie, J.: An exact Jacobian SDP relaxation for polynomial optimization. Math. Program. 137, 225-255 (2013) · Zbl 1266.65094 · doi:10.1007/s10107-011-0489-4 |
| [27] | Nie, J.: Certifying convergence of Lasserre’s hierarchy via flat truncation. Math. Program. 142, 485-510 (2013) · Zbl 1305.65151 · doi:10.1007/s10107-012-0589-9 |
| [28] | Nie, J.: Optimality conditions and finite convergence of Lasserre’s hierarchy. Math. Program. 146, 97-121 (2014) · Zbl 1300.65041 · doi:10.1007/s10107-013-0680-x |
| [29] | Nie, J.: The hierarchy of local minimums in polynomial optimizaion. Math. Program. 151, 555-583 (2015) · Zbl 1323.65071 · doi:10.1007/s10107-014-0845-2 |
| [30] | Nie, J.: Generating polynomials and symmetric tensor decomposition. Found. Comput. Math. 17, 423-465 (2017) · Zbl 1381.15017 · doi:10.1007/s10208-015-9291-7 |
| [31] | Qi, L.: Eigenvalues of a real supersymmetric tensor. J. Symb. Comput. 40, 1302-1324 (2005) · Zbl 1125.15014 · doi:10.1016/j.jsc.2005.05.007 |
| [32] | Qi, L.: Eigenvalues and invariants of tensors. J. Math. Anal. Appl. 325, 1363-1377 (2007) · Zbl 1113.15020 · doi:10.1016/j.jmaa.2006.02.071 |
| [33] | Qi, L.: The best rank-one approximation ratio of a tensor space. SIAM J. Matrix Anal. Appl. 32, 430-442 (2011) · Zbl 1228.15010 · doi:10.1137/100795802 |
| [34] | Qi, L., Sun, W., Wang, Y.: Numerical multilinear algebra and its applications. Front. Math. China 2, 501-526 (2007) · Zbl 1134.65033 · doi:10.1007/s11464-007-0031-4 |
| [35] | Qi, L., Teo, K.L.: Multivariate polynomial minimization and its application in signal processing. J. Glob. Optim. 26, 419-433 (2003) · Zbl 1023.90064 · doi:10.1023/A:1024778309049 |
| [36] | Qi, L., Wang, F., Wang, Y.: Z-eigenvalue methods for a global polynomial optimization problem. Math. Program. 118, 301-316 (2009) · Zbl 1169.90022 · doi:10.1007/s10107-007-0193-6 |
| [37] | Qi, L., Wang, Y., Wu, E.X.: D-eigenvalues of diffusion kurtosis tensor. J. Comput. Appl. Math. 221, 150-157 (2008) · Zbl 1176.65046 · doi:10.1016/j.cam.2007.10.012 |
| [38] | Qi, L., Yu, G., Wu, E.X.: Higher order positive semidefinite diffusion tensor imaging. SIAM J. Imaging Sci. 3, 416-433 (2010) · Zbl 1197.92032 · doi:10.1137/090755138 |
| [39] | Sturmfels, B.: Solving Systems of Polynomial Equations, CBMS Regional Conference Series in Mathematics, 97. American Mathematical Society, Providence (2002) · Zbl 1101.13040 · doi:10.1090/cbms/097 |
| [40] | Zhang, X., Qi, L., Ye, Y.: The cubic spherical optimization problems. Math. Comput. 81, 1513-1526 (2012) · Zbl 1252.65101 · doi:10.1090/S0025-5718-2012-02577-4 |
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.
