Skip to Main content Skip to Navigation
Journal articles

A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices

Stéphane Gaubert 1, 2 Nikolas Stott 2, 1
1 TROPICAL - TROPICAL
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
Abstract : We show that the joint spectral radius of a finite collection of nonnegative matrices can be bounded by the eigenvalue of a non-linear operator. This eigenvalue coincides with the ergodic constant of a risk-sensitive control problem, or of an entropy game, in which the state space consists of all switching sequences of a given length. We show that, by increasing this length, we arrive at a convergent approximation scheme to compute the joint spectral radius. The complexity of this method is exponential in the length of the switching sequences, but it is quite insensitive to the size of the matrices, allowing us to solve very large scale instances (several matrices in dimensions of order 1000 within a minute). An idea of this method is to replace a hierarchy of optimization problems, introduced by Ahmadi, Jungers, Parrilo and Roozbehani, by a hierarchy of nonlinear eigenproblems. To solve the latter eigenproblems, we introduce a projective version of Krasnoselskii-Mann iteration. This method is of independent interest as it applies more generally to the nonlinear eigenproblem for a monotone positively homogeneous map. Here, this method allows for scalability by avoiding the recourse to linear or semidefinite programming techniques.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-01967552
Contributor : Stephane Gaubert <>
Submitted on : Monday, December 31, 2018 - 4:49:21 PM
Last modification on : Monday, March 29, 2021 - 2:47:34 PM

Links full text

Identifiers

Collections

Citation

Stéphane Gaubert, Nikolas Stott. A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices. Mathematical Control and Related Fields, AIMS, 2020, 10 (3), pp.573-590. ⟨10.3934/mcrf.2020011⟩. ⟨hal-01967552⟩

Share

Metrics

Record views

271