Applied Nonlinear Perron-Frobenius Theory

About

This website has the aim to provide a self-contained and relatively detailed overview of the material presented at the SIAM LA and ILAS 2021 conferences minitutorial on Applied Nonlinear Perron-Frobenius Theory.

The slides of the talks can be found here:

Outline
The Perron-Frobenius Theorem
Network Centrality
The Birkhoff-Hopf Theorem
Optimization with nonlinear Perron eigenvectors

Abstract

Nonnegative matrices are pervasive in data mining applications. For example, distance and similarity matrices are fundamental tools for data classification, affinity matrices are key instruments for graph matching, adjacency matrices are at the basis of almost every graph mining algorithm, transition matrices are the main tool for studying stochastic processes on data. The Perron-Frobenius theory makes the algorithms based on these matrices very attractive from a linear algebra point of view. At the same time, as the available data grows both in terms of size and complexity, more and more data mining methods rely on nonlinear mappings rather than just matrices, which however still have some form of nonnegativity.The nonlinear Perron-Frobenius theory allows us to transfer most of the theoretical and computational niceties of nonnegative matrices to the much broader class of nonlinear multihomogeneous operators. These types of operators include for example commonly used maps associated with tensors and are tightly connected to the formulation of nonlinear eigenvalue problems with eigenvector nonlinearities. In this minitutorial we will introduce the concept of multihomogeneous operators and we will present the state-of-the-art version of the nonlinear Perron-Frobenius theorem for nonnegative nonlinear mappings. We will discuss several numerical optimization implications connected to nonlinear and higher-order versions of the Power and the Sinkhorn methods and several open challenges, both from the theoretical and the computational viewpoints. We will also discuss a number of problems in data mining, machine learning and network science which can be cast in terms of nonlinear eigenvector problems and we will show how the nonlinear Perron-Frobenius theory can help solve them.

Credits

The website (and the tutorial) is developed and maintained by Antoine Gautier and Francesco Tudisco.