×

Convergence analysis of an SVD-based algorithm for the best rank-1 tensor approximation. (English) Zbl 1397.65055

Summary: This paper revisits the classical problem of finding the best rank-1 approximation to a generic tensor. The main focus is on providing a mathematical proof for the convergence of the iterates of an SVD-based algorithm. In contrast to the conventional approach by the so called alternating least squares (ALS) method that works to adjust one factor a time, the SVD-based algorithms improve two factors simultaneously. The ALS method is easy to implement, but suffers from slow convergence and easy stagnation at a local solution. It has been suggested recently that the SVD-algorithm might have a better limiting behavior leading to better approximations, yet a theory of convergence has been elusive in the literature. This note proposes a simple tactic to partially close that gap.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A69 Multilinear algebra, tensor calculus
15A15 Determinants, permanents, traces, other special matrix functions
15A09 Theory of matrix inversion and generalized inverses
15A23 Factorization of matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Attouch, H.; Bolte, J.; Svaiter, B. F., Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., 137, 91-129, (2013) · Zbl 1260.49048
[2] Bader, B. W.; Kolda, T. G., Algorithm 862: MATLAB tensor classes for fast algorithm prototyping, ACM Trans. Math. Software, 32, 635-653, (2006) · Zbl 1230.65054
[3] Brachat, J.; Comon, P.; Mourrain, B.; Tsigaridas, E., Symmetric tensor decomposition, Linear Algebra Appl., 433, 1851-1872, (2010) · Zbl 1206.65141
[4] Bunse-Gerstner, A.; Byers, R.; Mehrmann, V.; Nichols, N. K., Numerical computation of an analytic singular value decomposition of a matrix valued function, Numer. Math., 60, 1-40, (1991) · Zbl 0743.65035
[5] Chill, R., On the łojasiewicz-Simon gradient inequality, J. Funct. Anal., 201, 572-601, (2003) · Zbl 1036.26015
[6] Comon, P.; Luciani, X.; de Almeida, A. L.F., Tensor decompositions, alternating least squares and other tales, J. Chemom., 23, 393-405, (2009)
[7] Comon, P.; Golub, G.; Lim, L.-H.; Mourrain, B., Symmetric tensors and symmetric tensor rank, SIAM J. Matrix Anal. Appl., 30, 1254-1279, (2008) · Zbl 1181.15014
[8] Dana, M.; Ikramov, K. D., On the codimension of the variety of symmetric matrices with multiple eigenvalues, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 323, 34-46, (2005), 224 · Zbl 1081.15526
[9] De Lathauwer, L.; De Moor, B.; Vandewalle, J., On the best rank-1 and rank-\((R_1, R_2, \cdots, R_N)\) approximation of higher-order tensors, SIAM J. Matrix Anal. Appl., 21, 1324-1342, (2000), (electronic) · Zbl 0958.15026
[10] Eckart, C.; Young, G., The approximation of one matrix by another of lower rank, Psychometrika, 1, 211-218, (1936) · JFM 62.1075.02
[11] Friedland, S.; Mehrmann, V.; Pajarola, R.; Suter, S. K., On best rank one approximation of tensors, Numer. Linear Algebra Appl., 20, 942-955, (2013) · Zbl 1313.65085
[12] Guan, Y.; Chu, M. T.; Chu, D., SVD-based algorithms for the best rank-1 approximation of a symmetric tensor, SIAM J. Matrix Anal. Appl., (2018), in press · Zbl 1451.65055
[13] 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
[14] Kofidis, E.; Regalia, P. A., On the best rank-1 approximation of higher-order supersymmetric tensors, SIAM J. Matrix Anal. Appl., 23, 863-884, (2001) · Zbl 1001.65035
[15] Kolda, T. G., Numerical optimization for symmetric tensor decomposition, Math. Program., 151, 225-248, (2015) · Zbl 1328.90139
[16] Kolda, T. G.; Bader, B. W., Tensor decompositions and applications, SIAM Rev., 51, 455-500, (2009) · Zbl 1173.65029
[17] Łojasiewicz, S., Une propriété topologique des sous-ensembles analytiques réels, (Les Équations aux Dérivées Partielles, Paris, 1962, (1963), Éditions du Centre National de la Recherche Scientifique Paris), 87-89 · Zbl 0234.57007
[18] Łojasiewicz, S.; Zurro, M.-A., On the gradient inequality, Bull. Pol. Acad. Sci. Math., 47, 143-145, (1999) · Zbl 0932.32009
[19] Moré, J. J.; Sorensen, D. C., Computing a trust region step, SIAM J. Sci. Statist. Comput., 4, 553-572, (1983) · Zbl 0551.65042
[20] Sommese, A. J.; Wampler, C. W., The numerical solution of systems of polynomials arising in engineering and science, (2005), World Scientific Publishing Co. Pte. Ltd. Hackensack, NJ · Zbl 1091.65049
[21] Uschmajew, A., Local convergence of the alternating least squares algorithm for canonical tensor approximation, SIAM J. Matrix Anal. Appl., 33, 639-652, (2012) · Zbl 1252.65085
[22] Wang, L.; Chu, M. T., On the global convergence of the alternating least squares method for rank-one approximation to generic tensors, SIAM J. Matrix Anal. Appl., 35, 1058-1072, (2014) · Zbl 1305.65129
[23] Wright, K., Differential equations for the analytic singular value decomposition of a matrix, Numer. Math., 3, 283-295, (1992) · Zbl 0756.65060
[24] Yang, Y.; Hu, S.; De Lathauwer, L.; Suykens, J. A., Convergence study of block singular value maximization methods for rank-1 approximation to higher order tensors, (2016), ESAT-SISTA, KU Leuven, Tech. rep., Internal Report 16-149
[25] Zhang, T.; Golub, G. H., Rank-one approximation to high order tensors, SIAM J. Matrix Anal. Appl., 23, 534-550, (2001), (electronic) · 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.