On Fast Computation of Gradients for CANDECOMP/PARAFAC Algorithms

Anh Huy Phan, Petr Tichavský, Andrzej CichockiarXiv 2012 · OpenReview

TL;DR

This paper introduces a novel, computationally efficient method for calculating the gradients required by CANDECOMP/PARAFAC (CP) tensor decomposition algorithms. By avoiding expensive tensor unfolding operations, their approach significantly speeds up CP algorithms, leading to substantial performance gains, especially for high-dimensional tensors.

What Problem Does This Paper Address?

The CANDECOMP/PARAFAC (CP) decomposition is a powerful tool for analyzing multi-way data, finding applications in fields like chemometrics, neuroscience, and signal processing. However, a major bottleneck in many CP algorithms, particularly the widely used Alternating Least Squares (ALS) method, is the computation of gradients. These gradients involve calculating products between tensor unfoldings and Khatri-Rao products of factor matrices. This operation is computationally intensive, with its complexity growing rapidly with the tensor's dimensions and rank. For high-dimensional tensors (e.g., 4D and above), this gradient computation can take hours, rendering the algorithms impractical. This paper tackles this computational bottleneck by proposing a faster way to compute these essential CP gradients.

Methods

The core contribution of this paper is a new algorithm for efficiently computing the CP gradients. The standard approach involves computing mode-$n$ unfoldings of the tensor, which are time-consuming, especially for modes other than the first or last. The proposed method cleverly avoids these expensive unfoldings by reformulating the gradient computation. Instead of directly unfolding the tensor, it leverages relationships between different tensor unfoldings and uses a recursive approach.

Specifically, the authors introduce two main strategies:

  • Right-to-left projections: This method is efficient when the dimension $J_n$ (product of dimensions before mode $n$) is smaller than $K_n$ (product of dimensions after mode $n$). It involves computing intermediate tensors and then performing tensor-vector products.
  • Left-to-right projections: This method is preferred when $J_n$ is larger than $K_n$. It also involves intermediate tensor computations but in a different order.

The algorithm intelligently chooses between these two strategies based on the tensor's dimensions to minimize computations. Furthermore, they propose an "all-at-once" algorithm that computes all gradients recursively, avoiding repeated computations and further enhancing efficiency.

Datasets

The paper does not introduce new datasets. Instead, it uses randomly generated tensors with various dimensions ($N=3, 4, 5, 6$) and sizes ($I_n = I = 10, 20, ..., 100$) to evaluate the performance of their proposed algorithm. They also mention an example of decomposing a 7-D tensor.

Key Insights and Ideas

  • The gradient computation is the true bottleneck: The paper highlights that the largest computational workload in CP algorithms lies in calculating the CP gradients, not necessarily in the tensor unfolding itself, but in the specific products involved.
  • Avoiding explicit tensor unfolding is key: The most significant insight is that by reformulating the gradient calculation, one can bypass the expensive mode-$n$ unfolding operations for $1 < n < N$.
  • Recursive computation offers substantial gains: The proposed recursive approach to compute gradients for all modes sequentially, rather than independently, leads to significant computational savings.
  • Dimension ordering matters: The choice between the "left-to-right" and "right-to-left" projection strategies depends on the relative sizes of dimension products, suggesting that pre-sorting dimensions can further optimize performance.

Key Results

The paper demonstrates significant speedups in CP algorithms by using their fast gradient computation method.

  • CP-ALS Acceleration: The fast CP-ALS algorithm, utilizing the proposed fast CP gradients, was found to be 2 times faster for 3-D tensors and 8 times faster for 4-D tensors compared to the standard CP-ALS.
  • High-Dimensional Performance: For higher dimensional tensors (5-D and 6-D), the speed-up ratios were even more impressive, reaching 20-30 times faster.
  • Extreme Cases: In an example with a 7-D tensor, the fast ALS achieved an average speed-up ratio of 42.2 times.
  • Practical Implications: The authors note that for problems that might take hours with the standard algorithm, their method can complete the task in minutes, making it practical for large-scale tensor decomposition.

Limitations and Future Work

  • Stopping Criteria: The simulations were performed without any specific stopping criteria for the algorithms, which might influence the total execution time in real-world scenarios.
  • Tucker Compression: The simulations did not utilize Tucker compression, which could potentially offer further speedups in some contexts.
  • Future Work: The authors suggest that their fast gradient computation method can be used to accelerate other CP and Nonnegative Tensor Factorization (NTF) algorithms. They also imply that further optimizations might be possible by exploring different strategies for dimension ordering and algorithm implementation.

Summary updated

Abstract

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.
BibTeX
@misc{phan2012fast,
  author = {Anh Huy Phan and Petr Tichavský and Andrzej Cichocki},
  title = {{On Fast Computation of Gradients for CANDECOMP/PARAFAC Algorithms}},
  year = {2012},
  eprint = {1204.1586},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1204.1586},
}
Figure