Low complexity damped Gauss-Newton algorithms for CANDECOMP/PARAFAC

DOI10.1137/100808034MaRDI QIDQ5300549zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Anh-Huy Phan, Petr Tichavský, Andrzej Cichocki

Publication date 27 June 2013

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.2584

zbMATH Keywords

alternating least squareslow-rank approximationinverse problemsline searchcanonical decompositionGauss-NewtonLevenberg-MarquardtCANDECOMP/PARAFACtensor factorizationcomplex-valued tensor factorization

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Multilinear algebra, tensor calculus (15A69)

Abstract: The damped Gauss-Newton (dGN) algorithm for CANDECOMP/PARAFAC (CP) decomposition can handle the challenges of collinearity of factors and different magnitudes of factors; nevertheless, for factorization of an $N$-D tensor of size $I_{1}imes{I}_N$ with rank $R$, the algorithm is computationally demanding due to construction of large approximate Hessian of size $(RTimesRT)$ and its inversion where $T=su{m}_n{I}_n$. In this paper, we propose a fast implementation of the dGN algorithm which is based on novel expressions of the inverse approximate Hessian in block form. The new implementation has lower computational complexity, besides computation of the gradient (this part is common to both methods), requiring the inversion of a matrix of size $N{R}^{2}imesN{R}^2$, which is much smaller than the whole approximate Hessian, if $TggNR$. In addition, the implementation has lower memory requirements, because neither the Hessian nor its inverse never need to be stored in their entirety. A variant of the algorithm working with complex valued data is proposed as well. Complexity and performance of the proposed algorithm is compared with those of dGN and ALS with line search on examples of difficult benchmark tensors.

Recommendations

• A Practical Randomized CP Tensor Decomposition
• A comparison of algorithms for fitting the PARAFAC model
• Optimization-based algorithms for tensor decompositions: canonical polyadic decomposition, decomposition in rank-(L_r,L_r,1) terms, and a new generalization
• Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition
• Structure of the Hessian matrix and an economical implementation of Newton's method in the problem of canonical approximation of tensors

Cited in

(23)

• A block-randomized stochastic method with importance sampling for CP tensor decomposition
• Tensor decompositions for count data that leverage stochastic and deterministic optimization
• A seminorm regularized alternating least squares algorithm for canonical tensor decomposition
• Inertial accelerated stochastic mirror descent for large-scale generalized tensor CP decomposition
• Tensor decomposition for learning Gaussian mixtures from moments
• Comparison of Accuracy and Scalability of Gauss--Newton and Alternating Least Squares for CANDECOMC/PARAFAC Decomposition
• Nonnegative tensor decomposition via collaborative neurodynamic optimization
• The optimization landscape for fitting a rank-2 tensor with a rank-1 tensor
• Computing the gradient in optimization algorithms for the CP decomposition in constant memory through tensor blocking
• Riemannian Newton optimization methods for the symmetric tensor approximation problem
• Condition numbers for the tensor rank decomposition
• Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition
• Generalized canonical polyadic tensor decomposition
• A Riemannian trust region method for the canonical tensor rank approximation problem
• On global convergence of alternating least squares for tensor approximation
• A literature survey of low-rank tensor approximation techniques
• Numerical CP decomposition of some difficult tensors
• An alternating shifted higher order power method based algorithm for rank-R Hermitian approximation and solving Hermitian CP-decomposition problems
• Reducing swamp behavior for the canonical polyadic decomposition problem by rank-1 freezing
• Alternate algorithms to most referenced techniques of numerical optimization to solve the symmetric rank-\(R\) approximation problem of symmetric tensors
• The dynamics of swamps in the canonical tensor approximation problem
• On the Uniqueness and Perturbation to the Best Rank-One Approximation of a Tensor
• Rank-1 tensor properties with applications to a class of tensor optimization problems

This page was built for publication: Low complexity damped Gauss-Newton algorithms for CANDECOMP/PARAFAC

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300549)