Nonlinear Perron-Frobenius Theorems for Nonnegative Tensors

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.