Abstract
We describe several approximation algorithms for the joint spectral radius and compare their performance on a large number of test cases. The joint spectral radius of a set Σ of \(n \times n\) matrices is the maximal asymptotic growth rate that can be obtained by forming products of matrices from Σ. This quantity is NP-hard to compute and appears in many areas, including in system theory, combinatorics and information theory. A dozen algorithms have been proposed this last decade for approximating the joint spectral radius but little is known about their practical efficiency. We overview these approximation algorithms and classify them in three categories: approximation obtained by examining long products, by building a specific matrix norm, and by using optimization-based techniques. All these algorithms are now implemented in a (freely available) MATLAB toolbox that was released in 2011. This toolbox allows us to present a comparison of the approximations obtained on a large number of test cases as well as on sets of matrices taken from the literature. Finally, in our comparison we include a method, available in the toolbox, that combines different existing algorithms and that is the toolbox’s default method. This default method was able to find optimal products for all test cases of dimension less than four.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Berger, M.A., Wang, Y.: Bounded semi-groups of matrices. Linear Algebra Appl. 166, 21–27 (1992).
Blondel, V.D., Nesterov, Y.: Computationally efficient approximations of the joint spectral radius. SIAM J. Matrix Anal. Appl. 27(1), 256–272 (2005).
Blondel, V.D., Nesterov, Y., Theys, J.: On the accuracy of the ellipsoid norm approximation of the joint spectral radius. Linear Algebra Appl. 394(1), 91–107 (2005).
Blondel, V.D., Theys, J., Vladimirov, A.A.: An elementary counterexample to the finiteness conjecture. SIAM J. Matrix Anal. Appl. 24(4), 963–970 (2003).
Bousch, T., Mairesse, J.: Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture. J. AMS 15(1), 77–111 (2002).
Chang, C.T., Blondel, V.D.: Approximating the joint spectral radius using a genetic algorithm framework. In: Proc. 18th IFAC World Congress, Vol. 18, pp. 8681–8686. Milano, Italy (2011)
Cicone, A., Guglielmi, N., Serra-Capizzano, S., Zennaro, M.: Finiteness property of pairs of 2×2 sign-matrices via real extremal polytope norms. Linear Algebra Appl. 432(2–3), 796–816 (2010).
Daubechies, I., Lagarias, J.C.: Two-scale difference equations II. Local regularity, infinite products of matrices and fractals. SIAM J. Math. Anal. 23(4), 1031–1079 (1992).
Gripenberg, G.: Computing the joint spectral radius. Linear Algebra Appl. 234, 43–60 (1996).
Guglielmi, N., Zennaro, M.: Balanced complex polytopes and related vector and matrix norms. J. Convex Anal. 14, 729–766 (2007).
Guglielmi, N.: Finding extremal complex polytope norms for families of real matrices. SIAM J. Matrix Anal. Appl. 31(2), 602–620 (2009).
Gurvits, L.: Stability of discrete linear inclusion. Linear Algebra Appl. 231, 47–85 (1995).
Hare, K.G., Morris, I.D., Sidorov, N., Theys, J.: An explicit counterexample to the Lagarias-Wang finiteness conjecture. Adv. Math. 226(6), 4667–4701 (2011).
Jungers, R.M.: The Joint Spectral Radius: Theory and Applications. Springer-Verlag, Berlin, Germany (2009)
Jungers, R.M., Protasov, V.Y., Blondel, V.D.: Overlap-free words and spectra of matrices. Theor. Comp. Sci. 410(38), 3670–3684 (2009).
Knuth, D.E.: The Art of Computer Programming, Volume 2, Seminumerical Algorithms. Addison-Wesley, Reading, MA (1997)
Kozyakin, V.S.: Proof of a Counterexample to the Finiteness Conjecture in the Spirit of the Theory of Dynamical Systems. Preprint 1005. Weierstraß-Institut f¨ur Angewandte Analysis und Stochastik, Berlin (2005)
Kozyakin, V.S.: Structure of extremal trajectories of discrete linear systems and the finiteness conjecture. Autom. Remote Control 68(1), 174–209 (2007).
Kozyakin, V.S.: On accuracy of approximation of the spectral radius by the Gelfand formula. Linear Algebra Appl. 431(11), 2134–2141 (2009).
Kozyakin, V.S.: A relaxation scheme for computation of the joint spectral radius of matrix sets. J. Diff. Equ. Appl. 17(2), 185–201 (2011)
Kozyakin, V.S.: Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets. Discrete Continuous Dyn. Syst., Ser. B 14(1), 143–158 (2010).
Lagarias, J.C., Wang, Y.: The finiteness conjecture for the generalized spectral radius of a set of matrices. Linear Algebra Appl. 214, 17–42 (1995).
Maesumi, M.: An efficient lower bound for the generalized spectral radius of a set of matrices. Linear Algebra Appl. 240, 1–7 (1996).
Maesumi, M.: Calculating joint spectral radius of matrices and H¨older exponent of wavelets. Approx. Theory IX 2, 1–8 (1998).
Moision, B.E., Orlitsky, A., Siegel, P.H.: On codes that avoid specified differences. IEEE Trans. Inf. Theory 47(1), 433–442 (2001).
Parrilo, P.A.: Jadbabaie, A.: Approximation of the joint spectral radius using sum of squares. Linear Algebra Appl 428(10), 2385–2402 (2008).
Protasov, V.Y.: The joint spectral radius and invariant sets of linear operators. Fundam. Prikl. Mat. 2(1), 205–231 (1996).
Protasov, V.Y., Jungers, R.M.: Joint spectral characteristics of matrices: a conic programming approach. SIAM J. Matrix. Anal. Appl. 31(4), 2146–2162 (2010).
Rota, G.C., Strang, G.: A note on the joint spectral radius. Indag. Math. 22, 379–381 (1960).
Shorten, R., Wirth, F., Mason, O., Wulff, K., King, C.: Stability criteria for switched and hybrid systems. SIAM Review 49(4), 545–592 (2007).
Tsitsiklis, J.N., Blondel, V.D.: The Lyapunov exponent and joint spectral radius of pairs of matrices are hard—when not impossible—to compute and to approximate. Math. Cont. Sign. Syst. 10(1), 31–40 (1997).
Vankeerbergen, G., Hendrickx, J., Jungers, R., Chang, C.T., Blondel, V.: The JSR Toolbox. MATLAB®Central. [Software, MATLAB® toolbox]. Files available at http://www.mathworks.com/matlabcentral/fileexchange/33202-the-jsr-toolbox (2011)
Wirth, F.: The generalized spectral radius and extremal norms. Linear Algebra Appl. 342(1), 17–40 (2002).
Author information
Authors and Affiliations
Corresponding author
Additional information
This article presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. The scientific responsibility rests with the authors. Chia-Tche Chang is a F.R.S.-FNRS Research Fellow (Belgian Fund for Scientific Research). A preliminary version of the second section of this article has been presented at the 18th IFAC World Congress, Milano, 2011 [6].
Rights and permissions
About this article
Cite this article
Chang, CT., Blondel, V.D. An experimental study of approximation algorithms for the joint spectral radius. Numer Algor 64, 181–202 (2013). https://doi.org/10.1007/s11075-012-9661-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-012-9661-z
Keywords
- Joint spectral radius
- Generalized spectral radius
- Product of matrices
- Matrix semigroup
- Dynamical systems
- Discrete-time systems