Approximation of the Joint Spectral Radius of a Set of Matrices Using Sum of Squares

摘要

We provide an asymptotically tight, computationally efficient approximation of the joint spectral radius of a set of matrices using sum of squares (SOS) programming. The approach is based on a search for a SOS polynomial that proves simultaneous contractibility of a finite set of matrices. We provide a bound on the quality of the approximation that unifies several earlier results and is independent of the number of matrices. Additionally, we present a comparison between our approximation scheme and a recent technique due to Blondel and Nesterov, based on lifting of matrices. Theoretical results and numerical investigations show that our approach yields tighter approximations.