Low Complexity Damped Gauss--Newton Algorithms for CANDECOMP/PARAFAC

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

Andrzej Cichocki, Anh-Huy Phan, Petr Tichavský

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

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)

• Computing the Gradient in Optimization Algorithms for the CP Decomposition in Constant Memory through Tensor Blocking
• A seminorm regularized alternating least squares algorithm for canonical tensor decomposition
• Rank-1 Tensor Properties with Applications to a Class of Tensor Optimization Problems
• Tensor decomposition for learning Gaussian mixtures from moments
• Generalized Canonical Polyadic Tensor Decomposition
• Comparison of Accuracy and Scalability of Gauss--Newton and Alternating Least Squares for CANDECOMC/PARAFAC Decomposition
• A Riemannian Trust Region Method for the Canonical Tensor Rank Approximation Problem
• The Dynamics of Swamps in the Canonical Tensor Approximation Problem
• 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
• The Optimization Landscape for Fitting a Rank-2 Tensor with a Rank-1 Tensor
• 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
• On the Uniqueness and Perturbation to the Best Rank-One Approximation of a Tensor
• 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)