Fast and precise approximations of the joint spectral radius

Vincent Blondel and Yu Nesterov

No 2003097, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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)

Date: 2003-12
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2003.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2003097

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().