A Nonlinear GMRES Optimization Algorithm for Canonical Tensor Decomposition

By Hans De Sterck. 2011

74 citations recorded by the source corpus.

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 components. 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 is used that was proposed by Washio and Oosterlee in [ETNA Vol. 15 (2003), pp. 165-185] for nonlinear partial differential equation problems. 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 both stand-alone ALS and a standard nonlinear conjugate gradient optimization method, especially when highly accurate stationary points are desired for difficult problems. The proposed N-GMRES optimization algorithm is based on general concepts and may be applied to other nonlinear optimization problems.

Subfields: Computational Mathematics, Computational Theory and Mathematics, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “…and robustness of gradient-based and Newton-like methods [2,72,74,140,223,224], modifying and improving ALS (alternating least squares) [41, 57, 58, 90, 225], studying the convergence of ALS [51, 194, 253] and reducing the cost of the unfolding operations required during the approximation…”
An Adaptive Algebraic Multigrid Algorithm for Low-Rank Canonical Tensor Decomposition (2011, unknown): “Along the same vein, a new method for computing the CP decomposition was recently developed by combining a nonlinear generalized minimal residual method with a line search [30].”
Fast and Robust Iterative Closest Point (2020, background): “Anderson acceleration was originally proposed in [37] for iterative solution of nonlinear integral equations, and has proved effective for accelerating ﬁxed-point iterations [8], [38], [39], [40], [41], [42], [43], [44], [45].”