Nonlinear Perron-Frobenius theorems for nonnegative tensors

Abstract

We present a unifying Perron–Frobenius theory for nonlinear spectral problems defined in terms of nonnegative tensors. By using the concept of tensor shape partition, our results include, as a special case, a wide variety of particular tensor spectral problems considered in the literature and can be applied to a broad set of problems involving tensors (and matrices), including the computation of operator norms, graph and hypergraph matching in computer vision, hypergraph spectral theory, higher-order network analysis, and multimarginal optimal transport. The key to our approach is to recast the eigenvalue problem as a fixed point problem on a suitable product of projective spaces. This allows us to use the theory of multihomogeneous order-preserving maps to derive new and unifying Perron–Frobenius theorems for nonnegative tensors, which either imply earlier results of this kind or improve them, as weaker assumptions are required. We introduce a general power method for the computation of the dominant tensor eigenpair and provide a detailed convergence analysis. This paper is directly based on our previous work [A. Gautier, F. Tudisco, and M. Hein, SIAM J. Matrix Anal. Appl., 40 (2019), pp. 1206–1231] and complements it by providing an extended introduction and several new results.

Please cite this paper as:

@article{gautier2013nonlinear,
	author = {Gautier, Antoine and Tudisco, Francesco and Hein, Matthias},
	doi = {10.1137/23M1557489},
	journal = {SIAM Review},
	number = {2},
	pages = {495-536},
	title = {Nonlinear Perron--Frobenius Theorems for Nonnegative Tensors},
	volume = {65},
	year = {2023}
}

Keywords: Perron-Frobenius theory nonlinear eigenvalues nonnegative tensors Hilbert metric Thompson metric power method multi-homogeneous maps