Shifted Power Method for Computing Tensor Eigenpairs

Tamara G. Kolda, Jackson R. Mayo

Abstract

Finding eigenvalues for higher-order tensors is a fundamental challenge in multilinear algebra, as standard iterative methods often fail to converge due to the non-linear nature of the problem. This paper introduces the Shifted Symmetric Higher-Order Power Method (SS-HOPM), a robust algorithm that utilizes a mathematical "shift" to guarantee convergence to a tensor eigenpair. By employing fixed-point analysis, the authors classify the stability of eigenpairs and demonstrate that SS-HOPM reliably identifies specific classes of solutions. The method is further extended to the complex domain, providing a scalable and efficient tool for applications ranging from signal processing to molecular chemistry.

Introduction

In classical linear algebra, the computation of eigenvalues and eigenvectors for matrices is well-understood. However, modern data science increasingly relies on tensors—data arrays with three or more indices. Tensors are essential in fields such as blind source separation, magnetic resonance imaging (MRI), and quantum chemistry.

A central problem in tensor analysis is finding the "best rank-1 approximation" of a symmetric tensor, which is mathematically equivalent to finding its largest eigenvalue. While the Symmetric Higher-Order Power Method (S-HOPM) was developed for this purpose, it is notoriously unreliable. Unlike the matrix power method, S-HOPM frequently oscillates or fails to converge entirely, even for low-dimensional tensors. This instability stems from the complex, non-linear optimization landscape of tensor eigenproblems, which can possess significantly more eigenpairs than their matrix counterparts.

The Shifted Symmetric Higher-Order Power Method (SS-HOPM)

To address the convergence failures of S-HOPM, the authors propose a modified iteration scheme. The core innovation is the introduction of a Shift ($\alpha$) to the underlying scalar function being maximized. By adding a term proportional to $\alpha(x^T x)^{m/2}$, the authors can manipulate the curvature of the optimization landscape.

Algorithmic Mechanism

By selecting a sufficiently large shift $\alpha$, the modified objective function is forced to become either strictly convex or strictly concave. This transformation ensures that the power-iteration update—which maps the gradient of the function back onto the unit sphere—is guaranteed to converge to a stationary point. This stationary point corresponds to a valid tensor eigenpair.

Fixed-Point and Stability Analysis

The paper utilizes the spectral radius of the Jacobian matrix at an eigenpair to classify its stability. Eigenpairs are categorized into three types:

  1. Positive Stable: Attractors for the concave version of the algorithm.
  2. Negative Stable: Attractors for the convex version of the algorithm.
  3. Unstable: Saddle points that act as repellers for the algorithm.

This theoretical framework allows researchers to predict which eigenpairs the algorithm will find and explains why the original S-HOPM (where $\alpha=0$) often fails to reach a stable fixed point.

Experimental Evaluation

As a study in numerical analysis, the researchers evaluated SS-HOPM using a variety of synthetic and analytical benchmarks:

  • Synthetic Symmetric Tensors: The authors tested the method on tensors of order 3 and 4 (e.g., $3 \times 3 \times 3$) specifically designed to cause standard methods to fail.
  • Random Tensors: These were used to measure average computation time and convergence rates across varying dimensions ($n$) and orders ($m$).
  • Analytical Verification: Simple tensors with hand-calculable eigenpairs were used to confirm that the observed numerical convergence matched the theoretical fixed-point analysis.

Key Results

  • Guaranteed Convergence: In trials where the original S-HOPM failed 100% of the time, SS-HOPM achieved a 100% convergence rate to an eigenpair.
  • Predictability: The numerical error reduction per iteration matched the theoretical convergence rates derived from the Jacobian spectral radius with high precision.
  • Scalability: The computational cost per iteration is $O(n^m)$, comparable to a single tensor-vector multiplication. This makes SS-HOPM significantly more efficient than symbolic or polynomial solvers, which suffer from exponential time growth as the dimension $n$ increases.

Discussion and Future Work

While SS-HOPM provides a robust guarantee of convergence, it is not without limitations. The method is a local optimizer; while it is guaranteed to find an eigenpair, it does not necessarily find the global maximum (the largest eigenvalue) in a single run. Users must typically employ multiple random restarts to explore the landscape for the best rank-1 approximation.

Furthermore, the choice of the shift $\alpha$ involves a trade-off. A very large "conservative" shift ensures stability but can significantly slow the rate of convergence. Finding an optimal shift that balances these two factors remains an area for future research. Finally, while the authors proposed a complex-valued extension of the algorithm that performs well in practice, a rigorous convergence theory for the complex case is still being developed.

In conclusion, SS-HOPM bridges the gap between classical matrix power methods and the complexities of multi-linear algebra, offering a reliable, scalable, and theoretically grounded approach to tensor decomposition.

Summary updated

Abstract

Recent work on eigenvalues and eigenvectors for tensors of order m >= 3 has been motivated by applications in blind source separation, magnetic resonance imaging, molecular conformation, and more. In this paper, we consider methods for computing real symmetric-tensor eigenpairs of the form Ax^{m-1} = λx subject to ||x||=1, which is closely related to optimal rank-1 approximation of a symmetric tensor. Our contribution is a shifted symmetric higher-order power method (SS-HOPM), which we show is guaranteed to converge to a tensor eigenpair. SS-HOPM can be viewed as a generalization of the power iteration method for matrices or of the symmetric higher-order power method. Additionally, using fixed point analysis, we can characterize exactly which eigenpairs can and cannot be found by the method. Numerical examples are presented, including examples from an extension of the method to finding complex eigenpairs.
BibTeX
@article{kolda2011shifted,
  author = {Tamara G. Kolda and Jackson R. Mayo},
  title = {{Shifted Power Method for Computing Tensor Eigenpairs}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2011},
  doi = {10.1137/100801482},
}

Loading related content...

Figure