TL;DR
This paper introduces a new algorithm, the Shifted Symmetric Higher-Order Power Method (SS-HOPM), for finding eigenvalues and eigenvectors of symmetric tensors. This method is guaranteed to converge and offers a robust way to tackle problems in areas like blind source separation and medical imaging, extending the well-known power method for matrices to higher-order tensors.
What Problem Does This Paper Address?
The paper addresses the challenge of computing eigenvalues and eigenvectors (eigenpairs) for symmetric tensors, which are multi-dimensional arrays. These eigenpairs are crucial for various applications, including blind source separation, magnetic resonance imaging, and molecular conformation analysis. While methods for matrices exist, extending them to tensors is complex due to the higher dimensionality and the existence of multiple definitions for tensor eigenpairs. The authors focus on a specific definition of tensor eigenpairs that relates to finding optimal rank-1 approximations of tensors. Existing methods, like the Symmetric Higher-Order Power Method (S-HOPM), are not always guaranteed to converge, especially for certain types of tensors. This paper aims to provide a reliable and convergent method for computing these tensor eigenpairs.
Methods
The core contribution is the Shifted Symmetric Higher-Order Power Method (SS-HOPM). This method is a modification of the existing Symmetric Higher-Order Power Method (S-HOPM). The key innovation is the introduction of a "shift" parameter ($\alpha$). This shift is added to a modified version of the function being optimized, which effectively forces the underlying function to be either convex or concave. This convexity/concavity property, combined with fixed-point analysis, guarantees convergence. The paper also provides a theoretical framework using convex analysis and fixed-point theory to characterize which eigenpairs the SS-HOPM can find and under what conditions. An extension to handle complex eigenpairs is also proposed.
Datasets
Not discussed in the paper. The paper uses synthetic tensors defined by specific coefficient values for numerical examples and experiments.
Key Insights and Ideas
- Guaranteed Convergence: The introduction of a shift parameter ($\alpha$) in SS-HOPM is the key to ensuring convergence, overcoming a major limitation of previous methods like S-HOPM.
- Convexity/Concavity as a Tool: By modifying the objective function with a shift, the authors leverage the properties of convex and concave functions to guarantee convergence, even though the original tensor problem might not be inherently convex.
- Characterizing Eigenpairs: The paper provides a theoretical understanding of which eigenpairs SS-HOPM finds, classifying them as "stable" (positive or negative) based on the properties of the projected Hessian of the Lagrangian. Unstable eigenpairs are generally not found.
- Matrix Power Method Analogy: SS-HOPM is presented as a natural generalization of the power iteration method for matrices, extending its utility to higher-order tensors.
- Complex Eigenpairs: The paper proposes an extension for complex eigenpairs, suggesting that similar shifting techniques might be applicable, though theoretical guarantees are more limited.
Key Results
- The proposed SS-HOPM algorithm is guaranteed to converge to a tensor eigenpair for a suitable choice of the shift parameter $\alpha$.
- The paper provides a theoretical framework that characterizes the stability of the found eigenpairs (positive stable, negative stable, or unstable). SS-HOPM is shown to converge to stable eigenpairs.
- Numerical experiments demonstrate that SS-HOPM can successfully find multiple eigenpairs, including cases where S-HOPM fails to converge.
- The method's complexity per iteration is $O(nm)$, comparable to matrix-vector multiplication in the matrix power method.
- An extension to complex eigenpairs is proposed and demonstrated with numerical examples, showing it can find complex eigenrings.
Limitations and Future Work
- Finding All Eigenpairs: SS-HOPM, like the matrix power method, does not guarantee finding all eigenpairs. It tends to find eigenpairs with the largest magnitudes. Finding unstable eigenpairs requires different methods.
- Convergence Rate: While convergence is guaranteed, the rate of convergence can be slow, especially with large shifts. The paper suggests further analysis of convergence rates.
- Complex Case Theory: The theoretical analysis for the complex SS-HOPM is less developed than for the real case, with convergence guarantees primarily based on numerical evidence.
- Future Research Directions: The authors suggest investigating:
- How tensor eigenpairs change with small perturbations.
- The existence of a general tensor eigendecomposition.
- Methods to accelerate the convergence rate.
- Efficient numerical computation of unstable eigenpairs.
- Optimal storage strategies for symmetric tensors.
- Further analysis and development of the complex SS-HOPM.
Summary updated