Robust Eigenvectors of Symmetric Tensors

Tommi Muller, Elina Robeva, Konstantin Usevich

TL;DR

This paper investigates the robustness of eigenvectors for symmetric tensors, particularly in the context of the tensor power method. The authors show that eigenvectors that are part of a symmetric decomposition of a tensor become robust (i.e., attractors for the power method) when the tensor's order is sufficiently high. They then introduce and analyze specific classes of tensors, like equiangular tensors, that guarantee this property, offering a way to reliably recover these eigenvectors.

What Problem Does This Paper Address?

In fields dealing with high-dimensional data, such as machine learning and signal processing, tensors (multidimensional arrays) are increasingly used to represent complex datasets. A fundamental task is tensor decomposition, which aims to break down a tensor into simpler components. Similar to matrices, eigenvectors play a crucial role in understanding the structure and properties of symmetric tensors. The tensor power method is a popular algorithm for finding these eigenvectors, analogous to the matrix power method. However, unlike matrices, where eigenvectors are always stable fixed points of the power method, for symmetric tensors, this is not always the case. Some eigenvectors might not be robust, meaning the power method might not converge to them, or might converge to other vectors. This paper addresses the question of when eigenvectors of symmetric tensors are robust and can be reliably recovered using the tensor power method, especially when the tensor's order is high.

Methods

The core of the paper revolves around analyzing the tensor power method and its convergence properties for symmetric tensors. The authors leverage linear algebra and functional analysis to prove their main results.

  • Tensor Power Method: This iterative algorithm is defined as $x_{k+1} = \frac{T \cdot x_k^{d-1}}{||T \cdot x_k^{d-1}||}$, where $T$ is a $d$-th order tensor and $x_k$ is a vector. The fixed points of this iteration are related to the eigenvectors of the tensor.
  • Jacobian Analysis: A key technique is analyzing the Jacobian matrix of the tensor power method iteration map at an eigenvector. By studying the spectral radius of this Jacobian, the authors determine whether an eigenvector is an attracting fixed point (i.e., robust). Lemma 3.2 provides the criterion: an eigenvector is robust if the spectral radius of the Jacobian at that eigenvector is less than 1.
  • Symmetric Decomposition: The paper heavily relies on the concept of a symmetric decomposition of a tensor, $T = \sum_{i=1}^r \lambda_i v_i^{\otimes d}$, where $v_i$ are unit vectors and $\lambda_i$ are scalars. The main theorem connects the eigenvectors of $T$ to the vectors $v_i$ in its decomposition.
  • Equiangular Sets (ES) and Equiangular Tight Frames (ETF): To demonstrate their theoretical results, the authors introduce and study specific classes of tensors generated by vectors forming equiangular sets and equiangular tight frames. These structures are generalizations of orthonormal bases and have specific geometric properties (constant angle between vectors).

Datasets

Not discussed in the paper. The paper focuses on theoretical results and numerical experiments with synthetically generated tensors based on specific mathematical structures (equiangular sets, regular simplex frames, icosahedral frames).

Key Insights and Ideas

  • High Order Implies Robustness: The most significant insight is that for a symmetric tensor $T$ with a symmetric decomposition $T = \sum \lambda_i v_i^{\otimes d}$, if a vector $v_j$ from the decomposition is an eigenvector of $T$ (with a non-zero eigenvalue), then for a sufficiently high order $d$, $v_j$ is guaranteed to be a robust eigenvector. This is a powerful theoretical result that bridges tensor decomposition and iterative methods.
  • Eigenvectors as Generators: The paper establishes a strong link between the vectors that generate a symmetric decomposition of a tensor and its eigenvectors. When these generating vectors are also eigenvectors, their robustness is ensured for high-order tensors.
  • Equiangular Structures as a Source of Robust Eigenvectors: The authors show that tensors generated by equiangular sets (ES) and equiangular tight frames (ETF) are excellent candidates for having robust eigenvectors that are also the generating vectors. This provides concrete examples and constructions where the theory applies.
  • Generalization of Orthogonal Decomposition: Orthogonally decomposable tensors (where the generating vectors form an orthonormal basis) are a special case. The paper extends the understanding of robust eigenvectors to more general equiangular structures, which are less restrictive than orthonormal bases.
  • Numerical Verification: The numerical experiments, particularly with Mercedes-Benz frames, visually demonstrate the regions of convergence for the tensor power method, supporting the theoretical findings about robustness and the fractal nature of these regions for odd-order tensors.

Key Results

  • Theorem 3.1: If $v_j$ is an eigenvector of a symmetric tensor $T = \sum \lambda_i v_i^{\otimes d}$ with a non-zero eigenvalue, then for $d$ sufficiently large, $v_j$ is a robust eigenvector.
  • Equiangular Tensors: Tensors generated by equiangular sets (ES) and equiangular tight frames (ETF) are shown to have their generating vectors as eigenvectors under certain conditions (Theorem 4.2, Theorem 4.4).
  • Robustness for ETFs: For tensors generated by ETFs, the generating vectors are robust eigenvectors if a specific condition on the tensor order $d$ and the equiangular angle $\alpha$ is met (Theorem 4.4, Theorem 4.6). This condition often holds for large $d$.
  • Regular Simplex Tensors: For tensors generated by regular simplex frames (a specific type of ETF), all generating vectors are robust eigenvectors for $n \ge 2, d \ge 3$ with $n+d \ge 7$ (Theorem 4.6).
  • Mercedes-Benz Frame (n=2): For $d \ge 6$ and even, the tensor power method converges to one of the frame vectors for a specific set of initial vectors, and the regions of convergence are fractal for odd $d$ (Theorem 4.7, Figure 2).

Limitations and Future Work

  • "Sufficiently High Order": While Theorem 3.1 guarantees robustness for high orders, it doesn't specify the exact threshold for $d$. This threshold can depend on the specific tensor.
  • Non-Equiangular Sets: The paper primarily focuses on equiangular sets. Extending the results to non-equiangular sets is mentioned as an interesting direction for future work.
  • Uniqueness of Robust Eigenvectors: A key open problem (Problem 5.1) is to determine the conditions under which the generating vectors of an ES are the only robust eigenvectors. The paper conjectures that for regular simplex tensors, the frame vectors are indeed the only robust eigenvectors.
  • Perturbation Stability: The authors conjecture that eigenvectors of ETF-decomposable tensors are stable under small perturbations of the tensor, and can be recovered by the tensor power method (Conjecture 5.2).
  • Fractal Regions of Convergence: The fractal nature of convergence regions for odd $d$ is observed but not fully explained.

The paper provides a significant theoretical advancement in understanding the robustness of eigenvectors for symmetric tensors, particularly by linking it to tensor decomposition and the order of the tensor. The introduction and analysis of equiangular structures offer practical avenues for applying these findings.

Summary updated

Abstract

The tensor power method generalizes the matrix power method to higher order arrays, or tensors. Like in the matrix case, the fixed points of the tensor power method are the eigenvectors of the tensor. While every real symmetric matrix has an eigendecomposition, the vectors generating a symmetric decomposition of a real symmetric tensor are not always eigenvectors of the tensor. In this paper we show that whenever an eigenvector is a generator of the symmetric decomposition of a symmetric tensor, then (if the order of the tensor is sufficiently high) this eigenvector is robust, i.e., it is an attracting fixed point of the tensor power method. We exhibit new classes of symmetric tensors whose symmetric decomposition consists of eigenvectors. Generalizing orthogonally decomposable tensors, we consider equiangular tight frame decomposable and equiangular set decomposable tensors. Our main result implies that such tensors can be decomposed using the tensor power method.
BibTeX
@article{muller2022robust,
  author = {Tommi Muller and Elina Robeva and Konstantin Usevich},
  title = {{Robust Eigenvectors of Symmetric Tensors}},
  journal = {SIAM J. Matrix Anal. Appl},
  year = {2022},
  doi = {10.1137/21m1462052},
}
Figure