SparseJSR: A Fast Algorithm to Compute Joint Spectral Radius via Sparse SOS Decompositions

Understand

This paper focuses on the computation of joint spectral radii (JSR), when the involved matrices are sparse.

• We provide a sparse variant of the procedure proposed by Parrilo and Jadbabaie, to compute upper bounds of the JSR by means of sum-of-squares (SOS) relaxations.
• Our resulting iterative algorithm, called SparseJSR, is based on the term sparsity SOS (TSSOS) framework, developed by Wang, Magron and Lasserre, yielding SOS decompositions of polynomials with arbitrary sparse support.
• SparseJSR exploits the sparsity of the input matrices to significantly reduce the computational burden associated with the JSR computation.