Best Rank-One Tensor Approximation and Parallel Update Algorithm for CPD

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

TL;DR

This paper introduces a novel parallel algorithm (PARO) for CANDECOMP/PARAFAC (CPD) tensor decomposition, enabling simultaneous updates of rank-1 tensors. It achieves this by developing new Levenberg-Marquardt (LM) and rotational algorithms for best rank-1 tensor approximation, offering competitive computational costs with existing methods while enabling parallel processing for higher-rank decompositions.

What Problem Does This Paper Address?

The CANDECOMP/PARAFAC (CPD) decomposition is a powerful tool for analyzing multi-way data, aiming to represent a tensor as a sum of rank-1 tensors. However, existing methods for updating these rank-1 components, such as Alternating Least Squares (ALS), typically update them sequentially. This sequential nature limits the ability to parallelize the decomposition process, especially for high-rank tensors. While tensor deflation offers parallelization, it imposes additional constraints. This paper addresses the challenge of efficiently updating rank-1 tensors in parallel for CPD, aiming to improve computational speed and scalability for high-rank tensor decomposition.

Methods

The core contribution is the PArallel Rank-One Update (PARO) algorithm. PARO leverages novel algorithms for best rank-1 tensor approximation:

  • Levenberg-Marquardt (LM) Algorithm: The paper derives a new LM algorithm for best rank-1 tensor approximation. It's shown to have a computational complexity similar to first-order optimization methods and is particularly efficient for tensors of size $2 \times 2 \times \cdots \times 2$.
  • Rotational Algorithm (RORO): A new rotational algorithm is proposed for best rank-1 tensor approximation. This algorithm is particularly effective for tensors of size $2 \times 2 \times \cdots \times 2$, for which it provides a closed-form solution. For higher-order tensors, it can be efficiently solved by leveraging solutions for lower-order tensors.

These rank-1 approximation methods are then integrated into the PARO framework, which uses an augmented Lagrangian approach to update rank-1 tensors simultaneously. The algorithm also incorporates a regularization parameter ($\gamma$ or $\mu$) that can be fixed or adaptively adjusted to improve convergence.

Datasets

The paper evaluates the proposed algorithms on:

  • Tensors associated with matrix multiplication: Specifically, tensors representing the multiplication of two matrices of sizes $2 \times 2$, $2 \times 3$, and $3 \times 3$. These are challenging tensors due to their structure.
  • Random tensors: Tensors of various orders (N=3, 4) and dimensions (I=5, 10, ..., 30) are used to assess the general performance and success rates of the algorithms.
  • Synthesized tensors with highly collinear loading components: These tensors are designed to test the robustness of the algorithms in challenging scenarios where factor matrices have highly correlated columns.

No new benchmarks are introduced; rather, existing types of challenging tensors are used for evaluation.

Key Insights and Ideas

  • Parallelism in Rank-1 Updates: The most significant insight is that rank-1 tensor updates within CPD can be performed in parallel. This breaks the sequential bottleneck of traditional methods like ALS.
  • LM and Rotational Algorithms for Rank-1 Approximation: The development of efficient LM and rotational algorithms for best rank-1 tensor approximation provides powerful building blocks for parallel CPD. The closed-form solution for $2 \times 2 \times \cdots \times 2$ tensors is a notable theoretical achievement.
  • Adaptive Regularization: The paper highlights the importance of the regularization parameter ($\gamma$ or $\mu$) and demonstrates that adaptive adjustment can significantly speed up convergence and improve performance, especially for difficult tensors.
  • Equivalence of LM and First-Order Methods: The LM algorithm for best rank-1 approximation is shown to have a computational cost comparable to first-order optimization methods, making it an attractive option.

Key Results

  • Improved Convergence Speed: The PARO algorithm, especially with adaptive regularization, consistently outperforms ALS in terms of convergence speed for various tensor decomposition tasks, often achieving better results in fewer iterations.
  • High Success Ratios: PARO, particularly when using the sequential projection and truncation method for initialization, achieves high success ratios (e.g., >90% at $10^{-6}$ error for orders 3 and 4) in finding the best rank-1 tensor approximation.
  • Robustness to Collinearity: PARO demonstrates superior performance compared to ALS in decomposing tensors with highly collinear loading components, achieving significantly smaller approximation errors.
  • Scalability: The parallel nature of PARO makes it suitable for decomposing high-rank tensors, which can be implemented in distributed systems.

Limitations and Future Work

  • Convergence to Local Minima: While PARO generally performs well, the paper acknowledges that initialization methods (like SVD-based) can still lead to local minima, though PARO's adaptive strategies and the RORO algorithm with sequential projection show promise in mitigating this.
  • Parameter Tuning: The performance of PARO is sensitive to the choice of regularization parameters ($\gamma$ and $\mu$). While adaptive strategies are proposed, finding optimal settings can still require experimentation.
  • Extension to Nonnegativity and Incomplete Data: The authors suggest that the PARO algorithm can be extended to handle nonnegativity constraints and tensors with incomplete entries, which would broaden its applicability.
  • Further Optimization of Rank-1 Algorithms: While efficient LM and rotational algorithms are presented, further research into optimizing these for specific tensor structures or computational platforms could be beneficial.

Summary updated

Abstract

A novel algorithm is proposed for CANDECOMP/PARAFAC tensor decomposition to exploit best rank-1 tensor approximation. Different from the existing algorithms, our algorithm updates rank-1 tensors simultaneously in parallel. In order to achieve this, we develop new all-at-once algorithms for best rank-1 tensor approximation based on the Levenberg-Marquardt method and the rotational update. We show that the LM algorithm has the same complexity of first-order optimisation algorithms, while the rotational method leads to solving the best rank-1 approximation of tensors of size $2 \times 2 \times \cdots \times 2$. We derive a closed-form expression of the best rank-1 tensor of $2\times 2 \times 2$ tensors and present an ALS algorithm which updates 3 component at a time for higher order tensors. The proposed algorithm is illustrated in decomposition of difficult tensors which are associated with multiplication of two matrices.
BibTeX
@misc{phan2017best,
  author = {Anh Huy Phan and Petr Tichavský and Andrzej Cichocki},
  title = {{Best Rank-One Tensor Approximation and Parallel Update Algorithm for CPD}},
  year = {2017},
  eprint = {1709.08336},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.08336},
}
Figure