Fast And Precise Approximations Of The Joint Spectral Radius

Fast and Precise Approximations of the Joint Spectral Radius

In this paper, we introduce a procedure for approximating the joint spectral radius of a finite set of matrices with arbitrary precision. Our approximation procedure is based on semidefinite liftings and can be implemented in a recursive way. For two matrices even the first step of the procedure gives an approximation, whose relative quality is at least 1/√2, that is, more than 70%. The subsequent steps improve the quality but also increase the dimension of the auxiliary problem from which this approximation can be found. In an improved version of our approximation procedure we show how a relative quality of (1/√2(1/k)) can be obtained by evaluating the spectral radius of a single matrix of dimension nk nk+1)/2 where n is the dimension of the initial matrices. This result is computationally optimal in the sense that it provides an approximation of relative quality 1-[epsilon] in time polynomial in n(1/[epsilon]) and it is known that, unless P = NP, no such algorithm is possible that runs in time polynomial in n and 1/[epsilon]. For the special case of matrices with non-negative entries we prove that... where A(*k) denotes the kth Kroneckerp owerof A. An approximation of relative quality (1/2)(1/k) can therefore be obtained by computing the spectral radius of a single matrix of dimension n(k). From these inequalities it also follows that the spectral radius is given by the simple expression... where it is somewhat surprising to notice that the right hand side does not directly involve any mixed products between the matrices A1 and A2.

Fast and Precise Approximations of the Joint Spectral Radius

The Joint Spectral Radius

This monograph is based on the Ph.D. Thesis of the author [58]. Its goal is twofold: First, it presents most researchwork that has been done during his Ph.D., or at least the part of the work that is related with the joint spectral radius. This work was concerned with theoretical developments (part I) as well as the study of some applications (part II). As a second goal, it was the author’s feeling that a survey on the state of the art on the joint spectral radius was really missing in the literature, so that the ?rst two chapters of part I present such a survey. The other chapters mainly report personal research, except Chapter 5 which presents animportantapplicationofthejointspectralradius:thecontinuityofwavelet functions. The ?rst part of this monograph is dedicated to theoretical results. The ?rst two chapters present the above mentioned survey on the joint spectral radius. Its minimum-growth counterpart, the joint spectral subradius, is also considered. The next two chapters point out two speci?c theoretical topics, that are important in practical applications: the particular case of nonne- tive matrices, and the Finiteness Property. The second part considers applications involving the joint spectral radius.