Local convergence of the alternating least squares algorithm for canonical tensor approximation (Q2910973)

The author presents a local convergence result for the alternating least square (ALS) algorithm under the assumption that the Hessian of the loss function at the solution is essentially positive definite, except on a trivial null space caused by the scaling indeterminacy. This assumption necessarily requires the local essential uniqueness of the CP decomposition (that is, uniqueness up to scaling), which is reasonable for tensors of order higher than three. The proof shows that an inbuilt normalization procedure in the ALS algorithm acts (in first order) as a projection onto a subspace complementary to the null space of the Hessian. On this subspace the linear Gauss-Seidel method is known to be contractive.NEWLINENEWLINEThe main ideas are not specifically related to the least squares error as the loss function to be minimized. It turns out that the global minimization in one ALS direction can be replaced by a single Newton step to obtain an approximate scheme which is still convergent (under the same assumptions). One convenient aspect of this approach is that it avoids the explicit use of Lagrange multipliers. It is therefore easily accessible and, in principle, applicable to more delicate types of redundancies as they, for instance, occur in the Tucker format or in the newly developed TT format.