Nonlinearly preconditioned optimization on grassmann manifolds for computing approximate tucker tensor decompositions

Two accelerated optimization algorithms are presented for computing approximate Tucker tensor decompositions, formulated using orthonormal factor matrices, by minimizing error as measured by the Frobenius norm. The first is a nonlinearly preconditioned conjugate gradient (NPCG) algorithm, wherein a nonlinear preconditioner is used to generate a direction which replaces the gradient in the nonlinear conjugate gradient iteration. The second is a nonlinear GMRES (NGMRES) algorithm, in which a linear combination of past iterates and a tentative new iterate, generated by a nonlinear preconditioner, is minimized to produce an improved search direction. The Euclidean versions of these methods are extended to the manifold setting, where optimization on Grassmann manifolds is used to handle orthonormality constraints and to allow isolated minimizers. Several modifications are required for use on manifolds: logarithmic maps are used to determine required tangent vectors, retraction mappings are used in the line search update step, vector transport operators are used to compute linear combinations of tangent vectors, and the Euclidean gradient and Hessian operators are replaced by their manifold equivalents. The higher order orthogonal iteration (HOOI), the workhorse algorithm for computing approximate Tucker decompositions, is used as the nonlinear preconditioner in NPCG and N-GMRES. Several variants are provided for the update parameter β in NPCG, two for each of the Polak-Ribìere, Hestenes-Stiefel, and Hager- Zhang formulas. Variations for N-GMRES are based on how to approximate the Hessian operator applied to a vector. NPCG and N-GMRES are compared to HOOI, nonlinear conjugate gradient, limited memory BFGS, and a manifold trust region algorithm using randomly generated and real life tensor data with and without noise, arising from applications in computer vision and handwritten digit recognition. Numerical results show that N-GMRES with the Hessian approximated by a difference of gradients and NPCG with update parameters determined by modified Polak-Ribìere and Hestenes-Stiefel rules accelerate HOOI significantly for large tensors, in cases where there are significant amounts of noise in the data, and when high accuracy results are required. For these problems, the proposed methods converge much faster and more robustly than HOOI and recently developed state-of-the-art methods.