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 squaresCANDECOMP/PARAFACcanonical decompositioncomplex-valued tensor factorizationGauss-Newtoninverse problemsLevenberg-Marquardtline searchlow-rank approximationtensor factorization

Mathematics Subject Classification ID

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

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

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)