×

Greedy approaches to symmetric orthogonal tensor decomposition. (English) Zbl 1386.15051

Summary: Finding the symmetric and orthogonal decomposition of a tensor is a recurring problem in signal processing, machine learning, and statistics. In this paper, we review, establish, and compare the perturbation bounds for two natural types of incremental rank-one approximation approaches. Numerical experiments and open questions are also presented and discussed.

MSC:

15A69 Multilinear algebra, tensor calculus
15A18 Eigenvalues, singular values, and eigenvectors
49M27 Decomposition methods
65F99 Numerical linear algebra

Software:

GloptiPoly; Sostools
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky, {\it Tensor decompositions for learning latent variable models}, J. Mach. Learn. Res., 15 (2014), pp. 2773-2832. · Zbl 1319.62109
[2] B. Chen, S. He, Z. Li, and S. Zhang, {\it Maximum block improvement and polynomial optimization}, SIAM J. Optim., 22 (2012), pp. 87-107, . · Zbl 1250.90069
[3] P. Comon, {\it Independent component analysis, A new concept?}, Signal Process., 36 (1994), pp. 287-314, . · Zbl 0791.62004
[4] P. Comon and C. Jutten, {\it Handbook of Blind Source Separation: Independent Component Analysis and Applications}, Academic Press, New York, 2010.
[5] A. P. da Silva, P. Comon, and A. L. F. de Almeida, {\it A finite algorithm to compute rank-\(1\) tensor approximations}, IEEE Signal Process. Lett., 23 (2016), pp. 959-963.
[6] C. Davis and W. Kahan, {\it The rotation of eigenvectors by a perturbation. III}, SIAM J. Numer. Anal., 7 (1970), pp. 1-46, . · Zbl 0198.47201
[7] L. De Lathauwer, B. De Moor, and J. Vandewalle, {\it On the best rank-\(1\) and rank-\((R_1, R_2, …, R_n)\) approximation of higher-order tensors}, SIAM J. Matrix Anal. A., 21 (2000), pp. 1324-1342, . · Zbl 0958.15026
[8] J. Friedman, T. Hastie, and R. Tibshirani, {\it The Elements of Statistical Learning}, Springer Ser. Statist. 1, Springer, Berlin, 2001. · Zbl 0973.62007
[9] L. Han, {\it An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors}, Numer. Algebra Control Optim., 3 (2013), pp. 583-599, . · Zbl 1271.65064
[10] C. Hao, C. Cui, and Y. Dai, {\it A sequential subspace projection method for extreme Z-eigenvalues of supersymmetric tensors}, Numer. Linear Algebra Appl., (2014), . · Zbl 1363.65063
[11] D. Henrion, J. B. Lasserre, and J. Löfberg, {\it Gloptipoly 3: Moments, optimization, and semidefinite programming}, Optim. Methods Softw., 24 (2009), pp. 761-779, . · Zbl 1178.90277
[12] J. Hu, B. Jiang, X. Liu, and Z. Wen, {\it A note on semidefinite programming relaxations for polynomial optimization over a single sphere}, Sci. China Math., 59 (2016), pp. 1543-1560, . · Zbl 1354.65123
[13] B. Jiang, S. Ma, and S. Zhang, {\it Tensor principal component analysis via convex optimization}, Math. Program., (2014), pp. 1-35, .
[14] E. Kofidis and P. A. Regalia, {\it On the best rank-1 approximation of higher-order supersymmetric tensors}, SIAM J. Matrix Anal. A., 23 (2002), pp. 863-884, . · Zbl 1001.65035
[15] T. G. Kolda, {\it Orthogonal tensor decompositions}, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 243-255, . · Zbl 1005.15020
[16] T. G. Kolda and J. R. Mayo, {\it Shifted power method for computing tensor eigenpairs}, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1095-1124, . · Zbl 1247.65048
[17] J. B. Lasserre, {\it Global optimization with polynomials and the problem of moments}, SIAM J. Optim., 11 (2001), pp. 796-817, . · Zbl 1010.90061
[18] L.-H. Lim, {\it Singular values and eigenvalues of tensors: A variational approach}, in Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, Vol. 1, 2005, pp. 129-132.
[19] P. McCullagh, {\it Tensor Methods in Statistics}, Chapman and Hall, London, 1987. · Zbl 0732.62003
[20] C. Mu, D. Hsu, and D. Goldfarb, {\it Successive rank-one approximations for nearly orthogonally decomposable symmetric tensors}, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 1638-1659, . · Zbl 1330.15030
[21] Y. Nesterov, {\it Squared Functional Systems and Optimization Problems}, in High Performance Optimization, Springer, New York, 2000, pp. 405-440. · Zbl 0958.90090
[22] J. Nie and L. Wang, {\it Semidefinite relaxations for best rank-\(1\) tensor approximations}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 1155––1179, . · Zbl 1305.65134
[23] A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler, and P. A. Parrilo, {\it SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB}, , 2013.
[24] P. A. Parrilo, {\it Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization}, Ph.D. thesis, California Institute of Technology, 2000.
[25] P. A. Parrilo, {\it Semidefinite programming relaxations for semialgebraic problems}, Math. Program., 96 (2003), pp. 293-320, . · Zbl 1043.14018
[26] E. Robeva, {\it Orthogonal decomposition of symmetric tensors}, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 86-102, .
[27] N. Z. Shor, {\it An approach to obtaining global extremums in polynomial mathematical programming problems}, Cybernetics, 23 (1987), pp. 695-700. · Zbl 0654.90076
[28] D. A. Spielman, H. Wang, and J. Wright, {\it Exact recovery of sparsely-used dictionaries}, in Proceedings of COLT, 2012.
[29] J. Sun, Q. Qu, and J. Wright, {\it Complete dictionary recovery over the sphere}, in Proceedings of the 2015 International Conference on Sampling Theory and Applications, IEEE, 2015, pp. 407-410.
[30] M. Wang and Y. S. Song, {\it Orthogonal Tensor Decompositions via Two-Mode Higher-Order SVD (HOSVD)}, , 2016.
[31] Y. Wang and L. Qi, {\it On the successive supersymmetric rank-1 decomposition of higher-order supersymmetric tensors}, Numer. Linear Algebra Appl., 14 (2007), pp. 503-519, . · Zbl 1199.65150
[32] H. Weyl, {\it Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung)}, Math. Ann., 71 (1912), pp. 441-479, . · JFM 43.0436.01
[33] S. J. Wright and J. Nocedal, {\it Numerical Optimization}, Vol. 2, Springer, New York, 1999. · Zbl 0930.65067
[34] Y. Yang, Q. Yang, and L. Qi, {\it Properties and methods for finding the best rank-one approximation to higher-order tensors}, Comput. Optim. Appl., 58 (2014), pp. 105-132, . · Zbl 1321.90134
[35] T. Zhang and G. Golub, {\it Rank-one approximation to high order tensors}, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 534-550, . · Zbl 1001.65036
[36] X. Zhang, C. Ling, and L. Qi, {\it The best rank-1 approximation of a symmetric tensor and related spherical optimization problems}, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 806-821, . · Zbl 1269.15026
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.