Tensor diagonalization - a new tool for PARAFAC and block-term decomposition

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

TL;DR

This paper introduces a novel non-orthogonal tensor diagonalization technique, TEDIA, which generalizes existing methods for signal processing tasks like source separation and component analysis. TEDIA offers a more robust and efficient approach to tensor decomposition, particularly for challenging scenarios with noise or fuzzy block structures, outperforming traditional methods in certain situations.

What Problem Does This Paper Address?

The paper tackles the challenge of decomposing multi-dimensional data represented as tensors. Specifically, it addresses the limitations of existing methods for tensor diagonalization, which aims to transform a tensor into a nearly diagonal form using invertible matrices. This is a generalization of Approximate Joint Diagonalization (AJD) for matrices, a technique widely used in signal processing for tasks like source separation, blind beamforming, and channel identification. While previous work focused on orthogonal diagonalization, this paper introduces non-orthogonal methods, which are more flexible and can lead to better decompositions. The authors also extend these techniques to block diagonalization, a crucial step for block-term decomposition, which represents a tensor as a sum of lower-rank tensors, revealing underlying structures. A key difficulty in these decompositions is avoiding convergence to suboptimal solutions (local minima) and handling noisy or ill-defined block structures.

Methods

The core contribution is the development of iterative algorithms for non-orthogonal tensor diagonalization. The paper proposes:

  • Two-sided symmetric diagonalization for order-three tensors (a novel AJD method).
  • General two-sided diagonalization for order-three tensors (useful for Canonical Polyadic (CP) decomposition).
  • Three-sided diagonalization for order-3 or order-4 tensors (also applicable to CP decomposition).
  • Tensor block diagonalization algorithms, which are generalizations of the above for scenarios where the tensor has a known block structure.
  • Blind block diagonalization, which aims to find the block structure without prior knowledge.

These algorithms are based on a principle of iterative refinement: "diagonalize until a further diagonalization is not possible." This is implemented using a gradient-based approach with an enhanced line search, similar to existing methods but adapted for tensor operations. The paper also introduces the TEDIA (Tensor Diagonalization) algorithm, which cyclically applies elementary rotations or gradient updates to achieve diagonalization. For block diagonalization, a block-off operator is introduced to handle the block structure.

Datasets

Not discussed in the paper. The paper focuses on synthetic data generation for simulations.

Key Insights and Ideas

  • Non-orthogonal diagonalization is powerful: Moving beyond orthogonal matrices allows for more flexible and potentially more accurate decompositions, especially when dealing with complex signal structures.
  • TEDIA's robustness: The proposed TEDIA algorithm is less sensitive to initialization errors compared to traditional methods like Alternating Least Squares (ALS). It can converge to better solutions even when initialized poorly, albeit with more iterations.
  • Block diagonalization for structure discovery: The ability to perform block diagonalization, both with and without prior knowledge of the block structure, is crucial for uncovering hidden structural components in tensors, as seen in block-term decomposition.
  • TEDIA as a building block: The diagonalization techniques can serve as initialization steps for other decomposition methods, potentially improving their performance and convergence.
  • Computational efficiency: While some TEDIA variants might require more iterations than simpler methods, they can achieve better results, especially in challenging scenarios, and their computational complexity is analyzed.

Key Results

The paper presents several numerical examples demonstrating the effectiveness of the proposed algorithms:

  • CP Decomposition: TEDIA (both three-sided and two-sided) shows competitive performance in CP decomposition, particularly in scenarios with high collinearity and noise, where it can outperform traditional methods like DTLD and ALS in terms of factor error at high SNRs.
  • Approximate Joint Block AJD: The block TEDIA algorithm demonstrates strong performance in blind block diagonalization, often achieving results comparable to or better than other state-of-the-art algorithms, especially when initialized with blind TEDIA.
  • Three-Sided Block Diagonalization: The block TEDIA algorithm shows good performance in scenarios with known block structures, outperforming block ALS in certain conditions.
  • Computational Speed: While TEDIA might require more iterations than some methods, its overall performance in terms of accuracy and robustness in difficult scenarios is highlighted. For instance, in one example, TEDIA 3 and TEDIA 2 achieved lower factor error at high SNRs, and the blind TEDIA (1000 iterations) was significantly faster than block ALS.

Limitations and Future Work

  • Permutation and Scaling Ambiguity: Like many tensor decomposition methods, the results can suffer from permutation and scaling ambiguities in the factor matrices, requiring post-processing to match theoretical values.
  • Computational Cost: While TEDIA is efficient, some variants, especially for block diagonalization, can still be computationally intensive, requiring a large number of iterations for convergence.
  • Initialization Sensitivity (for some methods): While TEDIA itself is less sensitive to initialization, some of its applications (e.g., initializing block ALS) rely on good initial estimates.
  • Future Work: The authors suggest that Matlab code for the proposed techniques is available, implying potential for further research and application. The paper also hints at generalizations to higher-order tensors and potential applications in DS-CDMA systems and tensor deconvolution for feature extraction.

Summary updated

Abstract

Tensor diagonalization means transforming a given tensor to an exactly or nearly diagonal form through multiplying the tensor by non-orthogonal invertible matrices along selected dimensions of the tensor. It is generalization of approximate joint diagonalization (AJD) of a set of matrices. In particular, we derive (1) a new algorithm for symmetric AJD, which is called two-sided symmetric diagonalization of order-three tensor, (2) a similar algorithm for non-symmetric AJD, also called general two-sided diagonalization of an order-3 tensor, and (3) an algorithm for three-sided diagonalization of order-3 or order-4 tensors. The latter two algorithms may serve for canonical polyadic (CP) tensor decomposition, and they can outperform other CP tensor decomposition methods in terms of computational speed under the restriction that the tensor rank does not exceed the tensor multilinear rank. Finally, we propose (4) similar algorithms for tensor block diagonalization, which is related to the tensor block-term decomposition.
BibTeX
@misc{tichavsky2014tensor,
  author = {Petr Tichavský and Anh Huy Phan and Andrzej Cichocki},
  title = {{Tensor diagonalization - a new tool for PARAFAC and block-term decomposition}},
  year = {2014},
  eprint = {1402.1673},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1402.1673},
}
Figure