Low Complexity Damped Gauss-Newton Algorithms for CANDECOMP/PARAFAC

By Anh Huy Phan, Petr Tichavský, Andrzej S. Cichocki. 2012

125 citations recorded by the source corpus.

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 order-$N$ tensor of size $I_1\times\cdots\times I_N$ with rank $R$, the algorithm is computationally demanding due to construction of a large approximate Hessian of size $(RT \times RT)$ and its inversion where $T = \sum_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 $NR^2\times NR^2$, which is much smaller than the whole approximate Hessian, if $T \gg NR$. In addition, the implementation has lower memory requirements, because neither the Hessian nor its inverse never needs to be stored in its entirety. A varia...

Subfields: Artificial Intelligence, Computational Mathematics, Hardware and Architecture

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mathematics

In Hardware and Architecture

Citations in the corpus

On Fast Computation of Gradients for CANDECOMP/PARAFAC Algorithms (2012, methodology): “ or simply adding a small diagonal matrix [10]. Instead of alternating estimation, all-at-once algorithms such as the OPT algorithm [1], the PMF3, dampedGauss-Newton(dGN) algorithms[24,33] andfast dGN[25,26,32] are studied to deal with problems of a slow convergence of the ALS in some cases. Another”
Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 1 Low-Rank Tensor Decompositions (2016, unknown): “For ill-conditioned problems, advanced algorithms typically exploit the rank-1 structure of the terms within CP decomposition to perform efficient computation and storage of the Jacobian and Hessian of the cost function [223,242].”
Tensors for Data Mining and Data Fusion (2016, methodology): “Acar et al. [2011] apply ALGORITHM 1: Alternating Least Squares for CP g., at random) 2: while convergence criterion is not met do 3: Normalize columns of B 7: Normalize columns of C and store norm in λ 9: end while ﬁrst-order gradient optimization methods such as limited-memory BFGS. Phan et al. [2”
CANDECOMP/PARAFAC Decomposition of High-Order Tensors Through Tensor Reshaping (2012, background): “Fast (approximate) Hessian and its inverse [31], [37] O ( R2T + N3R6 )”
Tensor Decompositions for Signal Processing Applications: From two-way to multiway component analysis (2014, methodology): “More sophisticated versions use the rank-1 structure of the terms within CPD to perform efficient computation and storage of the Jacobian and (approximate) Hessian; their complexity is on par with ALS while for ill-conditioned cases the performance is often superior [60, 61].”