On Fast Computation of Gradients for CANDECOMP/PARAFAC Algorithms

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

18 citations recorded by the source corpus.

Product between mode-$n$ unfolding $\bY_{(n)}$ of an $N$-D tensor $\tY$ and Khatri-Rao products of $(N-1)$ factor matrices $\bA^{(m)}$, $m = 1,..., n-1, n+1, ..., N$ exists in algorithms for CANDECOMP/PARAFAC (CP). If $\tY$ is an error tensor of a tensor approximation, this product is the gradient of a cost function with respect to factors, and has the largest workload in most CP algorithms. In this paper, a fast method to compute this product is proposed. Experimental verification shows that the fast CP gradient can accelerate the CP_ALS algorithm 2 times and 8 times faster for factorizations of 3-D and 4-D tensors, and the speed-up ratios can be 20-30 times for higher dimensional tensors.

How researchers see this paper

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

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “…developments for general tensors include work on increasing the efﬁciency and robustness of gradient-based and Newton-like methods [2,72,74,140,223,224], modifying and improving ALS (alternating least squares) [41, 57, 58, 90, 225], studying the convergence of ALS [51, 194, 253] and reducing…”
CANDECOMP/PARAFAC Decomposition of High-Order Tensors Through Tensor Reshaping (2012, background): “Gradient [1], [2] O ( NRJ ) Fast gradient [42] O ( RJ ) (Approximate) Hessian and its inverse [5], [29] O R 3 T 3 Fast (approximate) Hessian and its inverse [31], [37] where Y = ~ λ ; A (1) , A (2) , . . . , A ( N ) , so that k Y − b Y k 2 F is minimized.”