Source-linked AI summary
All Real Eigenvalues of Symmetric Tensors
Chun-Feng Cui, Yu-Hong Dai, Jiawang Nie
TL;DR
Existing methods mostly target the largest or smallest eigenvalues of symmetric tensors, leaving middle eigenvalues comparatively difficult to compute despite their applications. The paper applies Jacobian SDP relaxations to compute real eigenvalues sequentially, proving finite-hierarchy recovery and demonstrating the approach numerically, subject to computational limits.
Problem
Existing approaches mostly compute the largest or smallest eigenvalues, while middle eigenvalues remain important in applications.
Method
The paper reformulates eigenvalue computation as constrained polynomial optimization and applies Jacobian SDP relaxations sequentially from the largest eigenvalue downward.
Results
Each real eigenvalue can be computed by solving a finite hierarchy of semidefinite relaxations, with rank conditions supporting eigenvector recovery.
Takeaways & Limitations
The approach offers a systematic way to compute all real eigenvalues sequentially when the required relaxation sizes fit available computational resources.
Takeaways & Limitations
Relaxation size grows rapidly with order, and larger or special tensors may require too much memory for complete computation.
Abstract
from arXiv · showhide
This paper studies how to compute all real eigenvalues of a symmetric tensor. As is well known, the largest or smallest eigenvalue can be found by solving a polynomial optimization problem, while the other middle eigenvalues can not. We propose a new approach for computing all real eigenvalues sequentially, from the largest to the smallest. It uses Jacobian SDP relaxations in polynomial optimization. We show that each eigenvalue can be computed by solving a finite hierarchy of semidefinite relaxations. Numerical experiments are presented to show how to do this.
1. Introduction
The paper unifies several tensor-eigenvalue notions and frames computing all real eigenvalues as finding real critical values of a polynomial optimization problem. It targets the middle eigenvalues that existing methods largely do not compute, using sequential Jacobian semidefinite relaxations.
- Background: Tensor eigenvalues include H-, Z-, and D-eigenvalues, with applications in signal processing, diffusion tensor imaging, and automatic control.The paper uses a unified B-eigenvalue definition to encompass these cases.
- Definitions: A real eigenvalue is defined here as a real eigenvalue having a real eigenvector, and real eigenpairs require both components to be real.This convention distinguishes real eigenvalues from real scalar eigenvalues whose eigenvectors may be nonreal.
- Motivation: Existing methods mainly compute the largest or smallest eigenvalues, while middle eigenvalues remain comparatively underserved despite applications.Examples include diffusion coefficients in different directions and lower bounds for hypergraph bipartition width.
- Contribution: The proposed approach computes all real eigenvalues sequentially using Jacobian SDP relaxations, and each eigenvalue is obtainable from a finite hierarchy of semidefinite relaxations.The procedure proceeds from the largest eigenvalue toward the smallest.
- Polynomial optimization formulation: Eigenpairs correspond to critical points of maximizing Ax^m subject to Bx^m′ = 1, with the critical value equal to the eigenvalue.The optimization problem has finitely many complex and real critical values.
2. Preliminaries
The preliminaries establish polynomial, moment, localizing-matrix, ideal, SOS, and quadratic-module notation used to formulate semidefinite relaxations. These objects provide the algebraic language for representing polynomial constraints and nonnegativity.
- Algebraic constraints: An ideal collects polynomial multiples of generators, and its degree-truncated version restricts those multiples to a prescribed degree.This truncation is used in finite-degree relaxation constructions.
- Nonnegativity certificates: SOS polynomials are globally nonnegative, whereas not every globally nonnegative polynomial is SOS; quadratic modules combine SOS terms with polynomial constraints.The paper uses truncated quadratic modules in semidefinite relaxation theory.
- Polynomial notation: The paper represents tensor forms as homogeneous polynomials in x and uses multi-index notation for monomials and degrees.For a multi-index α, x^α denotes a monomial and |α| its total degree.
- Moment notation: Truncated multi-sequences define linear functionals on bounded-degree polynomial spaces, which underlie moment-based semidefinite formulations.The dual space of bounded-degree polynomials is represented by truncated multi-sequences.
- Semidefinite representations: Moment and localizing matrices are symmetric matrices generated linearly from a truncated sequence and encode quadratic forms associated with polynomials and constraints.Localizing matrices are defined for a polynomial q, while moment matrices correspond to q = 1.
3. Semidefinite relaxations for computing all real eigenvalues
The paper converts tensor eigenvalue computation into constrained polynomial optimization and uses Jacobian SDP relaxations to enumerate real critical values sequentially. Under smoothness and finite-eigenvector conditions, the resulting hierarchies converge finitely, while rank conditions certify extraction and practical computation remains size-limited.
- Formulation: Jacobian equations characterize critical points of the constrained tensor polynomial optimization problem without introducing a Lagrange multiplier.For smooth Bx^m′ = 1, feasible points of the Jacobian system correspond to B-eigenvectors.
- Formulation: The feasible objective values of the Jacobian-constrained problem are precisely the real eigenvalues λ1, …, λK.The largest eigenvalue is obtained by maximizing the tensor polynomial over this feasible set.
- Sequential computation: The algorithm computes λ1 first and then tests successive relaxations to obtain λ2, λ3, and later eigenvalues in descending order.Infeasibility can certify that no lower eigenvalue remains, while feasibility leads to the next eigenvalue.
- Finite convergence: Under a smooth constraint hypersurface, the largest-eigenvalue hierarchy reaches λ1 in finitely many steps, and finite eigenvector sets support rank-based extraction.The same finite-convergence and rank-condition logic is extended to successive eigenvalues.
- Numerical extraction: Flatness provides a practical convergence test and enables recovery of eigenvectors from moment matrices, although numerical rank decisions are sensitive to round-off and tolerances.Approximate SDP solutions make equalities and rank conditions only approximately valid.
4. Numerical experiments
The numerical experiments apply Algorithm 3.6 to compute real Z- and H-eigenvalues and associated eigenvectors across several tensors. Results show successful computation in examples of varying size, while memory and relaxation order limit larger cases.
- Numerical results: The reported runtimes range from about 1 second for small examples to about 400 seconds for a fifth-order tensor with 30 real Z-eigenvalues.Examples include about 1 second for two eigenvalues, about 9 seconds for several three-dimensional cases, and about 400 seconds for the 30-eigenvalue example.
- Numerical results: Algorithm 3.6 computes all real eigenvalues in the reported examples, including Z-eigenvalues, H-eigenvalues, and their eigenvectors when the rank condition permits.The experiments use semidefinite relaxations and report eigenvectors or multiplicities when the relevant rank condition is satisfied.
- Numerical results: For a sixth-dimensional cubic tensor, the experiments find 19 nonnegative Z-eigenvalues, with the largest equal to 16.2345.Because the eigenvalues occur in ± pairs, the experiment reports the nonnegative values.
- Numerical results: The experiments confirm that M(m, n) bounds the number of real Z-eigenvalues, while observed counts are not evenly distributed across tested cases.The authors state that they do not know the reason for the observed distributions.
- Computational limitations: In larger problems, memory and relaxation order constrain computation: only the three largest Z-eigenvalues are obtained for n = 8, 9, 10, and none for n > 10.The reported limitation arises because the required relaxation order causes the computer to run out of memory.