Fast and precise approximations of the joint spectral radius

Blondel, Vincent [UCL] Nesterov, Yurii [UCL]

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/sq.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/sq.2exp.1/k) can be obtained by evaluating the spectral radius of a single matrix of dimension nexp.k(nexp.k+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-E in time polynomial in nexp.1/E and it is known that, unless P=NP, no such algorithm is possible that runs in time polynomial in n and 1/E. For the special case of matrices with non-negative entries we prove that (1/2)exp.1/k pexp.1/k (A1exp.k + A2exp.k) <= p(A1, A2) <= pexp.1/k(A1exp.k + A2exp.k) where Aexp.k denotes the kth Kronecker power of A. An approximation of relative quality (1/2)exp.1/k can therefore be obtained by computing the spectral radius of a single matrix of dimension nexp.k.