Footnote:
Nach Informationen von SSRN wurde die ursprüngliche Fassung des Dokuments December 2003 erstellt
Description:
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