×

Rank-1 tensor properties with applications to a class of tensor optimization problems. (English) Zbl 1329.90114

Summary: This paper studies models and algorithms for a class of tensor optimization problems, based on a rank-1 equivalence property between a tensor and certain unfoldings. It is first shown that in \(d\)th order tensor space, the set of rank-1 tensors is the same as the intersection of \(\lceil \log_2(d) \rceil\) tensor sets, of which tensors have a specific rank-1 balanced unfolding matrix. Moreover, the number \(\lceil \log_2(d) \rceil\) is proved to be optimal in some sense. Based on the above equivalence property, three relaxation approaches for solving the best rank-1 tensor approximation problems are proposed, including two convex relaxations and a nonconvex one. The two convex relaxations utilize the matrix nuclear norm regularization/constraints. They have the advantage of identifying whether the solution is a global optimizer of the original problem, by computing the nuclear norm or the Frobenius norm of a certain matrix. Under certain assumptions, the optimal solution of the original problem is characterized by the solution to the dual of the nuclear norm constrained problem. The nonconvex relaxation can be solved via the conventional alternating minimization scheme, with the output being always a rank-1 tensor. Numerical experiments demonstrate the effectiveness of the proposed methods.

MSC:

90C26 Nonconvex programming, global optimization
15A18 Eigenvalues, singular values, and eigenvectors
15A69 Multilinear algebra, tensor calculus
41A50 Best approximation, Chebyshev systems
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] E. Acar, D. M. Dunlavy, T. G. Kolda, and M. Mørup, {\it Scalable tensor factorizations for incomplete data}, Chemometrics Intell. Lab. Syst., 106 (2011), pp. 41-56.
[2] C. M. Andersen and R. Bro, {\it Practical aspects of PARAFAC modeling of fluorescence excitation-emission data}, J. Chemometrics, 17 (2003), pp. 200-215.
[3] B. W. Bader, M. W. Berry, and M. Browne, {\it Discussion tracking in enron email using PARAFAC}, in Survey of Text Mining II, Springer, New York, 2008, pp. 147-163.
[4] B. W. Bader, et al., {\it MATLAB Tensor Toolbox Version} 2.5, http://www.sandia.gov/ tgkolda/TensorToolbox (2012).
[5] D. P. Bertsekas, {\it Nonlinear Programming}, Athena Scientific, Belmont, MA, 1999. · Zbl 1015.90077
[6] I. M. Bomze and L. Palagi, {\it Quartic formulation of standard quadratic optimization problems}, J. Global Optim., 32 (2005), pp. 181-205. · Zbl 1080.90057
[7] J.-F. Cai, E. J. Candès, and Z. Shen, {\it A singular value thresholding algorithm for matrix completion}, SIAM J. Optim., 20 (2010), pp. 1956-1982. · Zbl 1201.90155
[8] E. Carlini and J. Kleppe, {\it Ranks derived from multilinear maps}, J. Pure Appl. Algebra, 215 (2011), pp. 1999-2004. · Zbl 1215.15029
[9] J. D. Carroll and J. J. Chang, {\it Analysis of individual differences in multidimensional scaling via an n-way generalization of “Eckart-Young” decomposition}, Psychometrika, 35 (1970), pp. 283-319. · Zbl 0202.19101
[10] D. Cartwright and B. Sturmfels, {\it The number of eigenvalues of a tensor}, Linear Algebra Appl., 438 (2011), pp. 942-952. · Zbl 1277.15007
[11] 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
[12] Y.-L. Chen, C.-T. Hsu, and H.-Y. Liao, {\it Simultaneous tensor decomposition and completion using factor priors}, IEEE Trans. Pattern Anal. Mach. Intell., 36 (2014), pp. 577-591.
[13] M. Chertok and Y. Keller, {\it Efficient high order matching}, IEEE Trans. Pattern Anal. Mach. Intell., 32 (2010), pp. 2205-2215.
[14] L. De Lathauwer, {\it A link between the canonical decomposition in multilinear algebra and simultaneous matrix diagonalization}, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 642-666. · Zbl 1126.15007
[15] L. De Lathauwer and J. Castaing, {\it Tensor-based techniques for the blind separation of DS-CDMA signals}, Signal Process., 87 (2007), pp. 322-336. · Zbl 1186.94413
[16] L. De Lathauwer, B. De Moor, and J. Vandewalle, {\it A multilinear singular value decomposition}, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1253-1278. · Zbl 0962.15005
[17] 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 higer-order tensors}, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1324-1342. · Zbl 0958.15026
[18] V. De Silva and L.-H. Lim, {\it 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
[19] S. Friedland and G. Ottaviani, {\it The number of singular vector tuples and uniqueness of best rank-one approximation of tensors}, Found. Comput. Math., 14 (2014), pp. 1209-1242. · Zbl 1326.15036
[20] M. Fumikazu, M.-M. Eduardo, A. V.-S. Pedro, N. Nobuaki, M. Hiroaki, and Y. Yoko, {\it Decomposing EEG data into space-time-frequency components using parallel factor analysis}, NeuroImage, 22 (2004), pp. 1035-1045.
[21] S. Gandy, B. Recht, and I. Yamada, {\it Tensor completion and low-n-rank tensor recovery via convex optimization}, Inverse Problems, 27 (2011), 025010. · Zbl 1211.15036
[22] L. Grasedyck, {\it Hierarchical singular value decomposition of tensors}, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2029-2054. · Zbl 1210.65090
[23] W. Hackbusch, {\it Tensor Spaces and Numerical Tensor Calculus}, Springer Ser. Comput. Math. 42, Springer, Heidelberg, 2012. · Zbl 1244.65061
[24] R. A. Harshman, {\it Foundations of the PARAFAC Procedure: Models and Conditions for an “Explanatory” Multimodal Factor Analysis}, UCLA Working Papers in Phonetics, 16 (1970), pp. 1-84.
[25] J. Hastad, {\it Clique is hard to approximate within \(n^{1-ϵ}\)}, in Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996, IEEE Computer Society, Los Alamitos, CA, 1996, pp. 627-636.
[26] S. He, B. Jiang, Z. Li, and S. Zhang, {\it Probability bounds for polynomial functions in random variables}, Math. Oper. Res., 39 (2014), pp. 889-907. · Zbl 1314.60066
[27] S. He, Z. Li, and S. Zhang, {\it Approximation algorithms for homogeneous polynomial optimization with quadratic constraints}, Math. Program., 125 (2010), pp. 353-383. · Zbl 1206.90124
[28] C. J. Hillar and L.-H. Lim, {\it Most tensor problems are NP-hard}, J. ACM, 60 (2013), 45. · Zbl 1281.68126
[29] B. Jiang, S. Ma, and S. Zhang, {\it Tensor principal component analysis via convex optimization}, Math. Program., 150 (2014), pp. 423-457. · Zbl 1312.65008
[30] E. Kofidis and P. A. Regalia, {\it On the best rank-\(1\) approximation of higher-order supersymmetric tensors}, SIAM J. Matrix Anal. Appl., 23 (2002), pp. 863-884. · Zbl 1001.65035
[31] T. G. Kolda and B. W. Bader, {\it Tensor decompositions and applications}, SIAM Rev., 51 (2009), pp. 455-500. · Zbl 1173.65029
[32] T. G. Kolda, B. W. Bader, and J. P. Kenny, {\it Higher-order web link analysis using multilinear algebra}, in Proceedings of the Fifth IEEE International Conference on Data Mining, IEEE Computer Society, Los Alamitos, CA, 2005, pp. 242-249.
[33] 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
[34] L.-H. Lim, {\it Singular values and eigenvalues of tensors: A variational approach}, in Proceedings of the First IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, Vol. 1, IEEE, Piscataway, NJ, 2005, pp. 129-132.
[35] J. Liu, P. Musialski, P. Wonka, and J. Ye, {\it Tensor completion for estimating missing values in visual data}, IEEE Trans. Pattern Anal. Mach. Intell., 35 (2013), pp. 208-220.
[36] Z.-Q. Luo and S. Zhang, {\it A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints}, SIAM J. Optim., 20 (2010), pp. 1716-1736. · Zbl 1201.90147
[37] T. S. Motzkin and E. G. Straus, {\it Maxima for graphs and a new proof of a theorem of Turán}, Canad. J. Math., 17 (1965), pp. 533-540. · Zbl 0129.39902
[38] C. Mu, B. Huang, J. Wright, and D. Goldfarb, {\it Square deal: Lower bounds and improved relaxations for tensor recovery}, in Proceedings of the 31st International Conference on Machine Learning (ICML-14), 2014, pp. 73-81.
[39] A.-H. Phan, P. Tichavský, and A. Cichocki, {\it Low complexity damped Gauss-Newton algorithms for CANDECOMP/PARAFAC}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 126-147. · Zbl 1365.65071
[40] L. Qi, {\it Eigenvalues of a real supersymmetric tensor}, J. Symbolic Comput., 40 (2005), pp. 1302-1324. · Zbl 1125.15014
[41] L. Qi, H.-H. Dai, and D. Han, {\it Conditions for strong ellipticity and M-eigenvalues}, Front. Math. China, 4 (2009), pp. 349-364. · Zbl 1233.74004
[42] M. Rajih, P. Comon, and R. A. Harshman, {\it Enhanced line search: A novel method to accelerate PARAFAC}, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 1128-1147. · Zbl 1168.65313
[43] B. Recht, M. Fazel, and P. A. Parrilo, {\it Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization}, SIAM Rev., 52 (2010), pp. 471-501. · Zbl 1198.90321
[44] M. Signoretto, Q. T. Dinh, L. De Lathauwer, and J. A. K. Suykens, {\it Learning with tensors: A framework based on convex optimization and spectral regularization}, Mach. Learn., 94 (2014), pp. 303-351. · Zbl 1319.68191
[45] A. M.-C. So, {\it Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems}, Math. Program., 129 (2011), pp. 357-382. · Zbl 1230.90156
[46] M. Signoretto, R. Van de Plas, B. De Moor, and J. A. K. Suykens, {\it Tensor versus matrix completion: A comparison with application to spectral data}, IEEE Signal Process. Lett., 18 (2011), pp. 403-406.
[47] S. Soare, J. W. Yoon, and O. Cazacu, {\it On the use of homogeneous polynomials to develop anisotropic yield functions with applications to sheet forming}, Int. J. Plasticity, 24 (2008), pp. 915-944. · Zbl 1394.74024
[48] L. Sorber, M. Van Barel, and L. De Lathauwer, {\it Tensorlab: A MATLAB Toolbox for Tensor Computations}, http://www.tensorlab.net/ (2014).
[49] Y. Yang, S. Mehrkanoon, and J. A. K. Suykens, {\it Higher Order Matching Pursuit for Low Rank Tensor Learning}, preprint, arXiv:1503.02216, 2015.
[50] Y. Yu, H. Cheng, and X. Zhang, {\it Approximate low-rank tensor learning}, 32nd NIPS Workshop on Optimization for Machine Learning, JMLR Workshop Conf. Proc. 37, 2014.
[51] T. Zhang and G. H. Golub, {\it Rank-one approximation to high order tensors}, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 534-550. · Zbl 1001.65036
[52] X. Zhang, L. Qi, and Y. Ye, {\it The cubic spherical optimization problems}, Math. Comp., 81 (2012), pp. 1513-1525. · Zbl 1252.65101
[53] G. Zhou, L. Caccetta, K. L. Teo, and S.-Y. Wu, {\it Nonnegative polynomial optimization over unit spheres and convex programming relaxations}, SIAM J. Optim., 22 (2012), pp. 987-1008. · Zbl 1263.90104
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.