TL;DR
This paper introduces a novel "rank splitting" technique for decomposing high-rank tensors, extending previous "rank-1 deflation" methods. Their new Alternating Subspace Update (ASU) algorithm efficiently extracts multiple rank-1 components simultaneously, significantly reducing computational cost and improving accuracy, especially for challenging datasets with collinear components.
What Problem Does This Paper Address?
The CANDECOMP/PARAFAC (CPD) model is a powerful tool for decomposing multiway data (tensors) into a sum of rank-1 tensors. However, sequentially extracting these rank-1 components, a process known as tensor deflation, can be computationally expensive and unstable, particularly when components are nearly collinear. Existing methods struggle with this, leading to potential inaccuracies or prohibitive computational demands for large, high-rank tensors. This paper addresses the challenge of efficiently and accurately decomposing such tensors by developing a "block deflation" or "rank splitting" method that can extract multiple rank-1 components at once.
Methods
The core contribution is the development of an Alternating Subspace Update (ASU) algorithm for rank-2 block deflation. This algorithm extends previous rank-1 deflation techniques by allowing the simultaneous extraction of two rank-1 components. The ASU algorithm is designed for order-3 tensors of size R x R x R and rank-R.
Key aspects of the method include:
- Rank Splitting: The fundamental idea is to split a high-rank tensor into two lower-rank tensors. Specifically, a rank-R tensor is decomposed into a rank-K tensor and a rank-(R-K) tensor. In this paper, the focus is on K=2, meaning two rank-1 components are extracted simultaneously.
- Orthogonal Normalization: A crucial preprocessing step involves orthogonalizing the factor matrices to simplify the optimization problem.
- Alternating Subspace Update: The algorithm iteratively updates parameters related to the two components being extracted. This involves optimizing for scalar parameters ($\sigma_n$) and orthogonal matrices ($W^{(n)}, V^{(n)}$) that represent the components.
- Closed-Form Expressions: For the core tensors (G and H), closed-form expressions are derived, which helps in simplifying the optimization.
- Efficient Computation: The ASU algorithm aims for a computational complexity of O(R³) per iteration, which is significantly lower than the O(R⁴) complexity of standard ALS algorithms for CPD, especially for large R.
Datasets
The paper uses synthetic datasets for evaluation. These tensors are generated with controlled rank and collinearity of factor matrices. The specific parameters for generating these tensors are detailed in Appendix F of reference [6] and involve setting collinearity degrees between components. No new benchmarks are introduced; rather, existing synthetic tensor generation methods are utilized to test the algorithm's performance under various challenging conditions.
Key Insights and Ideas
- Block Deflation is More Robust: For tensors with highly collinear components, extracting multiple components simultaneously (block deflation) is shown to be more accurate and stable than extracting them one by one (rank-1 deflation).
- Computational Efficiency: The ASU algorithm achieves a significant speedup (up to 8 times faster than ALS for R=10) and handles large-scale tensors much more efficiently (seconds vs. hours for R=300 and R=500) compared to existing methods. This is attributed to its O(R³) complexity and its ability to avoid estimating all parameters of the full CP model.
- Handling Collinearity: The ASU algorithm is particularly effective when factor matrices have nearly collinear components, a scenario where rank-1 deflation methods often struggle.
- Reduced Parameter Estimation: The algorithm estimates only 4 vectors and 2 scalars per dimension, a substantial reduction compared to methods that estimate all factor matrices and core tensors.
Key Results
- Accuracy: The ASU algorithm demonstrates comparable or superior accuracy to ALS, especially in scenarios with high collinearity. For instance, in Example 3, ASU-2 (block deflation) showed a loss of accuracy of only 0.37 dB to 2.5 dB compared to ASU-1 (rank-1 deflation) when collinearity increased.
- Speed: The ASU algorithm is significantly faster than existing methods like ALS and FastALS. For R=10, it was on average 8 times faster than ALS. For large-scale tensors (R=300 and R=500), ASU completed decomposition in seconds, while FastALS took hours.
- Scalability: The algorithm scales well to large tensors, as demonstrated by its performance on R=300 and R=500 tensors.
Limitations and Future Work
- Order-3 Tensors: The developed ASU algorithm is specifically detailed for order-3 tensors. While the paper mentions it can be extended to higher-order tensors, this extension is not elaborated upon.
- Rank-2 Block Deflation: The primary focus is on rank-2 block deflation (extracting two components at a time). The paper suggests this can be extended to extract more components simultaneously, but this is a direction for future research.
- Constraints: The paper notes that the algorithm can be extended to decomposition with additional constraints, but this is not explored in detail.
- Implementation Availability: The authors provide a MATLAB package TENSORBOX for the block tensor deflation algorithms, which is a valuable resource for researchers.
Summary updated