On the accuracy of the ellipsoid norm approximation of the joint spectral radius

✍ Scribed by Vincent D. Blondel; Yurii Nesterov; Jacques Theys

• Publisher: Elsevier Science
• Year: 2005
• Tongue: English
• Weight: 260 KB
• Volume: 394
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/j.laa.2004.06.024

✦ Synopsis

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 but is notoriously difficult to compute and to approximate. We introduce in this paper an approximation ρ 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 [ ρ/ √ n, ρ], where n is the dimension of the matrices. We also provide a simple approximation for the special case where the entries of the matrices are non-negative; 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.