Tensor-based Dinkelbach method for computing generalized tensor eigenvalues and its applications
Haibin Chen, Wenqi Zhu, Coralia Cartis · 2025
Read Tensor-based Dinkelbach method for computing generalized tensor eigenvalues and its applications by Haibin Chen, Wenqi Zhu, Coralia Cartis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-09735.txt.
Introduction
Haibin Chen, Wenqi Zhu, and Coralia Cartis wrote a 2025 mathematics paper on computing special values for tensors. Tensors are multi-way arrays of numbers used across physics and data science. Their eigenvalues, in a generalized sense, mark extreme behaviors of the system the tensor describes. Finding the largest or smallest such value is a hard problem with uses in other tasks, such as trust-region steps in optimization.
The authors adapt a classic method for fractions, the Dinkelbach approach, to tensors. The extreme value problem becomes a linked chain of smaller problems, each a multilinear optimization under a simple round constraint. They solve those with an efficient alternating method and prove it settles to the answer from any start. A second form of the problem, without constraints, lets them pin down how fast the method converges. Early computer tests on eigenvalue problems and trust-region tasks support the theory.
Catalog record
| CREATOR | Haibin Chen, Wenqi Zhu, Coralia Cartis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-09735
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tensor-based Dinkelbach method for computing generalized tensor eigenvalues and its applications Haibin Chen, Wenqi Zhu, Coralia Cartis Abstract In this paper, we propose a novel tensor-based Dinkelbach–Type method for computing extremal tensor generalized eigenvalues. We show that the extremal tensor generalized eigenvalue can be reformulated as a critical subproblem of the classical Dinkelbach–Type method, which can subsequently be expressed as a multilinear optimization problem (MOP). The MOP is solved under a spherical constraint using an efficient proximal alternative minimization method which we rigorously establish the global convergence. Additionally, the equivalent MOP is reformulated as an unconstrained optimization problem, allowing for the analysis of the Kurdyka-Łojasiewicz (KL) exponent and providing an explicit expression for the convergence rate of the proposed algorithm. Preliminary numerical experiments on solving extremal tensor generalized eigenvalues and minimizing high-order trust-region subproblems are provided, validating the efficacy and practical utility of the proposed method. ∎ MSC 65H17 - 15A18 - 90C3 1 Introduction With the growing research interest in efficient methods for processing large-scale and high-dimensional datasets, researchers have been actively developing algorithms for analyzing high-order tensors, which are multi-dimensional arrays of data. As a fundamental component of tensor analysis, tensor eigenvalues, and eigenvectors, along with their potential applications and computational methods, have been extensively studied in the literature, for example, in [ 9 , 22 , 34 ] . Several types of tensor eigenvalues have been introduced through different generalizations of the matrix case, each with specific applications. These include Z-eigenvalues [ 29 , 35 ] , H-eigenvalues [ 14 , 35 ] , D-eigenvalues, and others [ 36 ] . The concept of tensor generalized eigenvalues was defined by Chang, Pearson, and Zhang [ 14 ] . For given m th-order, n -dimensional real-valued symmetric tensors {\cal A} and {\cal B} , the objective is to find \lambda\in\mathbb{R} and {\bf x}\in\mathbb{R}^{n}\setminus\{{\bf 0}\} such that \displaystyle{\cal A}{\bf x}^{m-1}=\lambda{\cal B}{\bf x}^{m-1}. (1) A key advantage of the generalized eigenpair framework is its flexibility: by appropriately choosing {\cal B} , it can encompass multiple definitions of tensor eigenvalues, such as Z-eigenvalues, H-eigenvalues, and D-eigenvalues. For further details on selecting {\cal B} , we have constructed a summary table in Appendix D . We also refer readers to [ 25 ] for additional insights. Computing eigenvalues of high-order tensors is an NP-hard problem, even for tensors with special structures [ 19 , 33 ] . Consequently, researchers have primarily focused on computing their extremal eigenvalues. To the best of our knowledge, various numerical algorithms have been developed to compute extremal Z-eigenvalues, H-eigenvalues, or D-eigenvalues. These include the high-order power method [ 33 ] , the SOS polynomial algorithm [ 19 ] , and the Newton method, among others [ 17 ] . However, when m is even and {\cal B} is positive definite, the well-known numerical method for computing generalized tensor eigenvalues is the generalized eigenproblem adaptive power (GEAP) method, proposed by Kolda et al. in [ 25 ] . After that, an adaptive gradient (AG) approach was presented by Yu et al. in 2016 to establish both global convergence and linear convergence rates under certain appropriate conditions [ 44 ] . Moreover, for the generalized eigenvalue of tensors with certain special structures, Zhao et al. proposed two convergent gradient projection techniques to address weakly symmetric tensors [ 46 ] . Very recently, a normalized Newton method named NNGEM was presented to compute the generalized tensor eigenvalue problem in [ 30 ] . It was proved that the NNGEM approach has a higher rate of convergence than the AP and GEAM approaches. Note that, the algorithms above mainly focus on solving as many eigenpairs as possible, rather than the extreme eigenpairs. In this paper, we reformulate the extremal generalized tensor eigenvalue problem in ( 1 ) as a subproblem of the classical Dinkelbach–Type method. We outline this reformulation through the following analysis. By taking the dot product with {\bf x} on both sides of ( 1 ), any solution to ( 1 ) satisfies \lambda=\frac{{\cal A}{\bf x}^{m}}{{\cal B}{\bf x}^{m}}. The extremal generalized eigenpairs can thus be computed by solving the following nonlinear program [ 25 ] \min_{{\bf x}\in S}\frac{{\cal A}{\bf x}^{m}}{{\cal B}{\bf x}^{m}},\quad\text{and}\quad\max_{{\bf x}\in S}\frac{{\cal A}{\bf x}^{m}}{{\cal B}{\bf x}^{m}}, where S=\{{\bf x}:\|{\bf x}\|^{m}=1\} . These relates to a class of single-ratio fractional programming problems in the form \bar{\theta}=\min_{{\bf x}\in S}\frac{f({\bf x})}{g({\bf x})}, (2) and can be addressed using the classical Dinkelbach–Type method [ 21 ] . Using this tensor representation of homogeneous polynomials in ( 2 ), we propose a tensor-based Dinkelbach–Type method for computing the minimal generalized eigenvalue of two symmetric tensors. The proposed algorithm involves finding the root of the equation F(\bar{\theta})=0 , where F(\bar{\theta}) is the optimal value of the following parametric program F(\bar{\theta})=\min_{{\bf x}\in S}\left(f({\bf x})-\bar{\theta}g({\bf x})\right). (3) which shares the same global optimal solutions as ( 2 ). Note that are homogeneous polynomials f({\bf x}) and g({\bf x}) of even degree d . It is well known that homogeneous polynomials can be reformulated as high-order symmetric tensors applied to a vector of variables. Therefore, we show that ( 3 ) can be solved by a proximal alternative minimization algorithm through a multilinear optimization framework. The PAM algorithm alternates between updating each variable (or block of variables) while keeping the others fixed, incorporating a proximal step to ensure both convergence and stability. The subproblems in PAM are of lower dimensions, and each subproblem has a closed-form solution. The main contributions of this paper are twofold: 1. First, we establish that ( 3 ) is equivalent to a multilinear optimization problem (MOP) under the condition that F(\bar{\theta}) is concave. For cases where the objective function is not concave, we introduce an augmented model with a regularization term to ensure the concavity of the resulting model. Furthermore, we prove that the augmented model and ( 3 ) share the same optimal solutions under unit spherical constraints. 2. Second, leveraging the multilinear model corresponding to the augmented concave model, we propose a proximal alternating minimization (PAM) algorithm. Notably, the PAM algorithm can be interpreted as a block coordinate descent (BCD) method (see [ 38 ] ) with a cyclic update rule and proximal terms tailored for polynomial optimization models. When applied to ( 3 ) under unit spherical constraints, the subproblems of the PAM algorithm have analytic optimal solutions. We rigorously establish the global convergence of the PAM algorithm, using the analysis of the Kurdyka-Łojasiewicz (KL) exponent, under mild assumptions, we provide an explicit expression for the convergence rate of the proposed algorithm. Numerical experiments are conducted to compute the minimal generalized eigenvalue of symmetric tensors. Additionally, with slight modifications, the PAM algorithm can also be applied to the minimization of the high-order trust-region subproblems on the boundary. The remainder of this paper is organized as follows. Section 2 provides a review of relevant symbols, definitions of tensors, and the Dinkelbach–Type method. In Section 3 , we present the proposed PAM algorithm and establish its convergence and convergence rate under mild assumptions. Section 4 presents preliminary numerical results, demonstrating the application of the proposed algorithm for computing the minimal generalized eigenvalue of symmetric tensors and minimizing high-order trust-region subproblems on the boundary. Finally, Section 5 offers concluding remarks and