Source-linked AI summary
Shifted Power Method for Computing Tensor Eigenpairs
Tamara G. Kolda, Jackson R. Mayo
TL;DR
Tensor eigenpair computation is nonlinear, application-relevant, and closely tied to constrained optimization and rank-1 approximation. The paper introduces SS-HOPM, proves convergence for a suitable shift, and uses fixed-point analysis to identify its reachable eigenpairs, with limited complex-valued experiments.
Problem
Computing real symmetric-tensor eigenpairs is a nonlinear problem important for applications and related to best symmetric rank-1 approximation, while S-HOPM lacks guaranteed convergence.
Method
SS-HOPM adds a shift to the symmetric higher-order power method and analyzes its fixed points through convexity, concavity, and stability.
Results
SS-HOPM always converges to a real eigenpair for an appropriate shift and exactly characterizes the positive- or negative-stable eigenpairs it can find.
Takeaways & Limitations
The method is useful when eigenpairs among the largest magnitudes are primary targets, including best rank-1 approximation, while unstable eigenpairs require alternative methods.
Takeaways & Limitations
The complex extension has only limited experimental support, and its analysis remains future work; more generally, unstable real eigenpairs are not found by SS-HOPM.
Abstract
from arXiv · showhide
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.
1. Introduction.
The paper studies real symmetric-tensor eigenpairs linked to constrained optimization and best symmetric rank-1 approximation. It introduces SS-HOPM, a shifted method guaranteed to converge to an eigenpair while characterizing which eigenpairs it can find.
- The paper defines eigenpairs for symmetric real tensors through a tensor-vector equation with a unit-norm eigenvector.
- These eigenpairs are equivalent to Z-eigenpairs and l2-eigenpairs and correspond to KKT points of a constrained tensor optimization problem.
- The eigenpair problem is also equivalent to finding the best symmetric rank-1 approximation of a symmetric tensor.
- S-HOPM is not guaranteed to converge, motivating SS-HOPM, whose shifted formulation is guaranteed to converge to a constrained stationary point for odd- and even-order tensors.
- Fixed-point analysis characterizes the eigenpairs SS-HOPM can find, while a complex-valued extension is demonstrated experimentally.
2. Preliminaries.
The preliminaries define symmetric tensors, tensor-vector products, and the constrained optimization framework underlying tensor eigenpairs. They also introduce convexity, S-HOPM, and fixed-point criteria used to analyze convergence.
- Tensors: A tensor is an m-way array, and a symmetric tensor is invariant under every permutation of its indices.
- Tensors: The symmetric tensor-vector multiply contracts selected tensor modes with powers of a vector, producing a lower-order tensor.
- Tensors: For even-order tensors, an identity tensor can satisfy Ex^(m−1) = x on the unit sphere, but no such identity tensor exists for odd order.
- Convexity: For a convex differentiable function, normalizing its nonzero gradient at a unit vector increases the function unless the normalized gradient is unchanged.
- Constrained optimization: Tensor eigenpairs are constrained stationary points characterized by a Lagrange multiplier and KKT conditions for optimization on the unit sphere.
- Fixed-point theory: A fixed point is attracting when nearby iterates converge to it, with Jacobian spectral radius below one providing a sufficient condition and linear convergence rate.
- S-HOPM: S-HOPM seeks the constrained tensor optimization solution, and adding a shift can guarantee convergence when the modified function is convex or concave.
3. Symmetric higher-order power method (S-HOPM).
S-HOPM reformulates symmetric tensor eigenpair computation as constrained optimization of f(x)=Ax^m, but its convergence depends on convexity or concavity conditions. The paper analyzes the resulting stationary points and motivates a shifted method that guarantees convergence.
- Optimization formulation: S-HOPM seeks extrema of f(x)=Ax^m over the unit sphere, a problem equivalent to finding a best symmetric rank-1 approximation.Eigenpairs are exactly the constrained stationary points of this optimization problem.
- Algorithm: S-HOPM applies normalized tensor contractions iteratively to generate successive unit-norm vectors and associated values.The algorithm is introduced as the symmetric generalization of the higher-order power method.
- Fixed-point structure: The eigenpair classification uses the projected Hessian C(λ,x): positive definite indicates positive stability, negative definite indicates negative stability, and indefiniteness indicates instability.The classification is used to analyze which fixed points can attract the iteration.
- Convergence analysis: For even-order tensors, S-HOPM convergence is established when f is convex or concave on R^n, with λ_k respectively increasing or decreasing.These conditions can be checked through the definiteness of the Hessian of f.
- Numerical behavior: For the Example 3.5 tensor, 7 eigenpairs are possible, but 100 S-HOPM trials found only 2 eigenvalues; another tensor example showed complete nonconvergence.The results illustrate that S-HOPM may miss eigenpairs or fail to converge under unfavorable conditions.
- Shifted method: Adding a shift modifies S-HOPM so that the resulting method is guaranteed to converge to an eigenpair for both odd- and even-order tensors.For even orders, the shifted tensor preserves eigenvectors while shifting eigenvalues by α and enforces the relevant convexity property.
4. Shifted symmetric higher-order power method (SS-HOPM).
SS-HOPM modifies the objective with a shift so convexity or concavity guarantees convergence to tensor eigenpairs. Fixed-point analysis identifies which eigenpairs attract the convex and concave iterations, while also clarifying the method’s scope and limitations.
- Method: The shifted objective forces convexity or concavity, guaranteeing convergence to a KKT point rather than necessarily a global extremum.The shift preserves the optimization objective up to a constant while changing its curvature.
- Method: For even-order tensors, SS-HOPM is equivalent to applying S-HOPM to a modified tensor whose eigenvectors match those of A and whose eigenvalues are shifted by α.The identity tensor satisfies Ex^{m−1}=x on the unit sphere.
- Fixed-point analysis: Fixed-point analysis shows that convex SS-HOPM generically converges to negative stable eigenpairs, whereas concave SS-HOPM generically converges to positive stable eigenpairs.Unstable eigenpairs are generally not reached by either version.
- Convergence guarantees: For α > β(A), the convex iteration produces a nondecreasing convergent eigenvalue sequence, with accumulation points corresponding to eigenpairs.If A has finitely many real eigenvectors, the iterates themselves converge to one such point.
- Convergence guarantees: For α < −β(A), the concave iteration produces a nonincreasing convergent eigenvalue sequence, with accumulation points corresponding to eigenpairs.If the eigenvalues are isolated, the iterates converge to an eigenvector.
- Scope and limitations: SS-HOPM can find multiple eigenpairs, but it converges only to a subset, so multiple starting points may be needed and some eigenvalues remain inaccessible.This selectivity benefits rank-1 approximation when large-magnitude eigenvalues are the main target, but disadvantages users seeking other eigenpairs.
5. Complex case.
The paper extends tensor eigenpair analysis and SS-HOPM to complex vectors, introducing eigenrings and reporting numerical evidence for real and complex eigenpairs.
- Complex tensor eigenpairs are normalized with x†x = 1 and extend the real l2-eigenpair concept, while differing from Qi’s E-eigenpairs in the constraint.
- Multiplying an eigenvector by e^iϕ rotates the eigenvalue by e^i(m−2)ϕ, so eigenvalues with equal magnitude form eigenrings.
- Generic symmetric tensors have ((m−1)n −1)/(m−2) distinct eigenvalue equivalence classes.
- The polynomial solver can recover nonreal eigenpairs but becomes prohibitively expensive for large m or n; for Example 3.5, it found all 13 guaranteed classes.
- The complex SS-HOPM extension preserves phase through division by λk + α, but lacks convex-case convergence theory and may converge to random complex rotations of real eigenpairs.
- With 100 complex random starts on A ∈R[4,3], complex SS-HOPM found 7 distinct eigenrings, including 6 stable real eigenpairs and one ring of two complex eigenpairs.
- With α = 0, 95 trials converged to non-eigenpairs with |λ| = 0.3656, while the vector iterates failed to converge.
6. Conclusions.
The conclusions establish real SS-HOPM’s convergence and fixed-point characterization, while presenting complex SS-HOPM as promising but theoretically incomplete.
- SS-HOPM converges to a real eigenpair for an appropriate shift α, and fixed-point analysis identifies exactly the positive- or negative-stable eigenpairs it can find.
- Unstable real eigenpairs, for which C(λ, x) is indefinite, require alternative methods; basin boundaries may be defined by non-attracting eigenvectors.
- The complex SS-HOPM extension has limited numerical evidence of finding real and complex eigenpairs, while its analysis remains future work.
- Open questions include perturbation behavior, tensor eigendecomposition, convergence-rate acceleration, unstable-eigenpair computation, and efficient symmetric-tensor storage.
Appendix A. Further examples.
The appendix analyzes two small tensors with analytically characterized eigenpairs and evaluates SS-HOPM across shift parameters. The examples relate stability, Jacobian spectral radius, singular shifts, and empirical convergence.
- The first tensor has 7 analytically computable real eigenpairs, including 4 negative stable eigenpairs identifiable by SS-HOPM.
- For the first tensor, the Jacobian spectral-radius curve is identical across all 4 negative stable eigenpairs.
- The appendix also defines a 4th-order, 2-dimensional tensor with only a1111 = 1 and a2222 = −1 nonzero.
- For λ = 1 in the first tensor, the Jacobian spectral radius is α/(1+α), producing a singularity at α = −1.
- With α = 0, none of 100 trials converged for the first tensor, whereas α = 1/2 and α = 1 produced convergent trials toward stable eigenpairs.
- For the second tensor, experiments with α = 0.5 and α = −0.5 recovered the negative stable and positive stable eigenvalues as expected.