A NONLINEAR GMRES OPTIMIZATION ALGORITHM FOR CANONICAL TENSOR DECOMPOSITION*

摘要

A new algorithm is presented for computing a canonical rank-R tensor approximation that has minimal distance to a given tensor in the Frobenius norm,where the canonical rank-R tensor consists of the sum of R rank-one tensors. Each iteration of the method consists of three steps. In the first step,a tentative new iterate is generated by a stand-alone one-step process,for which we use alternating least squares(ALS). In the second step,an accelerated iterate is generated by a nonlinear generalized minimal residual(GMRES)approach,recombining previous iterates in an optimal way,and essentially using the stand-alone one-step process as a preconditioner. In particular,the nonlinear extension of GMRES we use that was proposed by Washio and Oosterlee in[Electron. Trans. Numer. Anal.,15(2003),pp. 165-185]for nonlinear partial differential equation problems(which is itself related to other existing acceleration methods for nonlinear equation systems). In the third step,a line search is performed for globalization. The resulting nonlinear GMRES(N-GMRES)optimization algorithm is applied to dense and sparse tensor decomposition test problems. The numerical tests show that ALS accelerated by N-GMRES may significantly outperform stand-alone ALS when highly accurate stationary points are desired for difficult problems. Further comparison tests show that N-GMRES is competitive with the well-known nonlinear conjugate gradient method for the test problems considered and outperforms it in many cases. The proposed N-GMRES optimization algorithm is based on general concepts and may be applied to other nonlinear optimization problems.