Authors 
: 

Document type 
: 
Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection

Abstract 
: 
The joint spectral radius of a set of matrices is a measure of the maximal asymptotic growth rate that can be obtained by forming long products of matrices taken from the set. This quantity appears in a number of application contexts, in particular it characterizes the growth rate of switched linear systems. The joint spectral radius is notoriously difficult to compute and to approximate. We introduce in this paper the first polynomial time approximations of guaranteed precision. We provide an approximation (p) over cap that is based on ellipsoid norms that can be computed by convex optimization and that is such that the joint spectral radius belongs to the interval [(p) over cap/ rootn (p) over cap] where n is the dimension of the matrices. We also provide a simple approximation for the special case where the entries of all the matrices are nonnegative; in this case the approximation is proved to be within a factor at most m (m is the number of matrices) of the exact value. 
Access type 
: 
Accès restreint 
Publication date 
: 
2004 
Language 
: 
Anglais 
Conference 
: 
"7th International Workshop on Hybrid Systems  Computation and Control", Philadelphia(Pa) (Mar 2527, 2004) 
Journal information 
: 
"Lecture Notes in Computer Science"  Vol. 2993, p. 173186 (2004) 
Peer reviewed 
: 
yes 
issn 
: 
03029743 
eissn 
: 
16113349 
Publisher 
: 
Springerverlag Berlin (Berlin)

Affiliation 
: 
UCL
 Autre

Links 
: 
