An Adaptive Shifted Power Method for Computing Generalized Tensor Eigenpairs

Tamara G. Kolda, Jackson R. Mayo

TL;DR

This paper introduces the Generalized Eigenproblem Adaptive Power (GEAP) method, an extension of the shifted power method for finding generalized tensor eigenpairs. GEAP addresses a key limitation of its predecessor by adaptively selecting the "shift" parameter, leading to faster and more robust convergence across various tensor eigenvalue problems.

What Problem Does This Paper Address?

The paper tackles the challenge of finding generalized tensor eigenpairs, a concept that unifies several existing definitions of tensor eigenvalues. While previous methods like the Shifted Symmetric Higher-Order Power Method (SS-HOPM) could compute these eigenpairs, their performance was highly sensitive to the choice of a "shift" parameter. A poorly chosen shift could lead to slow convergence or even failure to converge. This paper aims to overcome this limitation by developing an adaptive strategy for selecting this crucial parameter.

Methods

The core of this work is the Generalized Eigenproblem Adaptive Power (GEAP) method. GEAP builds upon the SS-HOPM by reformulating the generalized tensor eigenproblem as a nonlinear optimization problem. It then employs a novel adaptive shift selection strategy. This strategy dynamically adjusts the shift parameter at each iteration to ensure the underlying function is locally convex or concave, thereby guaranteeing monotonic convergence. The method is presented as an algorithm (Algorithm 1) and then specialized for Z-eigenpairs (Algorithm 2).

Datasets

Not discussed in the paper. The paper focuses on numerical experiments using synthetic tensors generated for specific examples from existing literature and randomly generated tensors.

Key Insights and Ideas

  • Unification of Tensor Eigenpairs: The generalized tensor eigenpair framework elegantly unifies various definitions (Z-eigenpairs, H-eigenpairs, D-eigenpairs), providing a single framework for their computation.
  • Adaptive Shift is Crucial: The paper highlights that the performance of power-iteration-like methods for tensor eigenproblems is critically dependent on the shift parameter. An adaptive approach is shown to be significantly more robust and efficient than fixed shifts.
  • Monotonic Convergence Guarantee: By adaptively adjusting the shift to ensure local convexity/concavity of the objective function, GEAP guarantees monotonic convergence of the eigenvalue at each step.
  • Efficiency Gains: The adaptive shift selection not only improves robustness but also leads to faster convergence, as demonstrated by experimental results.

Key Results

  • The GEAP method successfully computes generalized tensor eigenpairs (Z-, H-, and D-eigenpairs) across various examples.
  • Experimental results show that GEAP is significantly faster than SS-HOPM with fixed shifts for computing Z-eigenpairs.
  • The adaptive shift selection in GEAP requires fewer iterations for convergence compared to fixed, non-adaptive shifts.
  • GEAP demonstrates robustness, finding all local maxima and minima in the tested examples, with only minor monotonicity violations that do not prevent convergence.
  • The method is shown to be competitive with or superior to other numerical optimization approaches for tensor eigenproblems.

Limitations and Future Work

  • Local Optima: Like its predecessor, GEAP can only converge to local maxima and minima of the objective function, potentially missing saddle point solutions.
  • Computational Cost: While GEAP is efficient, the dominant cost per iteration is the computation of tensor-vector products, which can be expensive for large tensors.
  • Future Work: The authors mention that comparing GEAP to methods based on Jacobian semidefinite programming relaxations for computing all real eigenvalues is a topic for future study. They also note that exploring tighter tolerances for the Hessian's definiteness could potentially avoid monotonicity violations, though this might slow convergence.

Summary updated

Abstract

Several tensor eigenpair definitions have been put forth in the past decade, but these can all be unified under generalized tensor eigenpair framework, introduced by Chang, Pearson, and Zhang (2009). Given mth-order, n-dimensional real-valued symmetric tensors A and B, the goal is to find $λ\in R$ and $x \in R^n$, $x \neq 0$, such that $Ax^{m-1} = λBx^{m-1}$. Different choices for B yield different versions of the tensor eigenvalue problem. We present our generalized eigenproblem adaptive power method (GEAP) method for solving the problem, which is an extension of the shifted symmetric higher-order power method (SS-HOPM) for finding Z-eigenpairs. A major drawback of SS-HOPM was that its performance depended in choosing an appropriate shift, but our GEAP method also includes an adaptive method for choosing the shift automatically.
BibTeX
@article{kolda2014adaptive,
  author = {Tamara G. Kolda and Jackson R. Mayo},
  title = {{An Adaptive Shifted Power Method for Computing Generalized Tensor Eigenpairs}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2014},
  doi = {10.1137/140951758},
}
Figure