Low complexity damped Gauss-Newton algorithms for CANDECOMP/PARAFAC

DOI10.1137/100808034zbMATH Open1365.65071DBLPjournals/siammax/PhanTC13arXiv1205.2584OpenAlexW2066392792WikidataQ60486587 ScholiaQ60486587MaRDI QIDQ5300549FDOQ5300549

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)

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.

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

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

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)

Cited In (19)

• A seminorm regularized alternating least squares algorithm for canonical tensor 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
• 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
• An alternating shifted higher order power method based algorithm for rank-\(R\) Hermitian approximation and solving Hermitian CP-decomposition problems
• Numerical CP decomposition of some difficult tensors
• 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
• A block-randomized stochastic method with importance sampling for CP tensor decomposition

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)