Approximation of the joint spectral radius using sum of squares
From MaRDI portal
Abstract: We provide an asymptotically tight, computationally efficient approximation of the joint spectral radius of a set of matrices using sum of squares (SOS) programming. The approach is based on a search for an SOS polynomial that proves simultaneous contractibility of a finite set of matrices. We provide a bound on the quality of the approximation that unifies several earlier results and is independent of the number of matrices. Additionally, we present a comparison between our approximation scheme and earlier techniques, including the use of common quadratic Lyapunov functions and a method based on matrix liftings. Theoretical results and numerical investigations show that our approach yields tighter approximations.
Recommendations
- Approximation of the Joint Spectral Radius of a Set of Matrices Using Sum of Squares
- Estimates for the joint spectral radius
- Computationally Efficient Approximations of the Joint Spectral Radius
- Computing the joint spectral radius
- On the joint spectral radius
- scientific article; zbMATH DE number 57550
- On the Joint Spectral Radius
- A new strategy for exact determination of the joint spectral radius
- On the accuracy of the ellipsoid norm approximation of the joint spectral radius
- Approximation of the Constrained Joint Spectral Radius via Algebraic Lifting
Cites work
- A survey of computational complexity results in systems and control
- Algebraic unsolvability of problem of absolute stability of desynchronized systems
- An efficient lower bound for the generalized spectral radius of a set of matrices
- Approximation of the Joint Spectral Radius of a Set of Matrices Using Sum of Squares
- Asymptotic stability and generalized Gelfand spectral radius formula
- Bounded semigroups of matrices
- Characterizations of Scaling Functions: Continuous Solutions
- Class of global minimum bounds of polynomial functions
- Computationally Efficient Approximations of the Joint Spectral Radius
- Computing the joint spectral radius
- Constructive stability and asymptotic stability of dynamical systems
- Corrigendum/addendum to: Sets of matrices all infinite products of which converge
- Discrete Transforms, Semidefinite Programming, and Sum-of-Squares Representations of Nonnegative Polynomials
- Dynamical systems which undergo switching
- Handbook of semidefinite programming. Theory, algorithms, and applications
- scientific article; zbMATH DE number 3155071 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 1490041 (Why is no real title available?)
- scientific article; zbMATH DE number 753805 (Why is no real title available?)
- scientific article; zbMATH DE number 3445419 (Why is no real title available?)
- scientific article; zbMATH DE number 1860211 (Why is no real title available?)
- scientific article; zbMATH DE number 3204642 (Why is no real title available?)
- scientific article; zbMATH DE number 3052220 (Why is no real title available?)
- Nonquadratic Lyapunov functions for robust stability analysis of linear uncertain systems
- On cone-invariant linear matrix inequalities
- On infinite products of stochastic matrices
- On the accuracy of the ellipsoid norm approximation of the joint spectral radius
- Optimization Problems over Positive Pseudopolynomial Matrices
- Semidefinite optimization
- Semidefinite Programming
- Semidefinite programming relaxations for semialgebraic problems
- Sets of matrices all infinite products of which converge
- Simultaneous Contractibility
- The boundedness of all products of a pair of matrices is undecidable
- The generalized joint spectral radius. A geometric approach
- The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate
Cited in
(40)- On the accuracy of the ellipsoid norm approximation of the joint spectral radius
- Exact computation of joint spectral characteristics of linear operators
- Rank-one characterization of joint spectral radius of finite matrix family
- Graph Lyapunov function for switching stabilization and distributed computation
- The outer spectral radius and dynamics of completely positive maps
- Sum-of-squares methods for controlled invariant sets with applications to model-predictive control
- A limit formula for joint spectral radius with \(p\)-radius of probability distributions
- Stability analysis of linear systems subject to regenerative switchings
- Data driven stability analysis of black-box switched linear systems
- Completely positive reformulations for polynomial optimization
- Polytopic uncertainty for linear systems: new and old complexity results
- Invariant polytopes of sets of matrices with application to regularity of wavelets and subdivisions
- Lower bounds on complexity of Lyapunov functions for switched linear systems
- Stability of Markov regenerative switched linear systems
- A relaxation scheme for computation of the joint spectral radius of matrix sets
- Stability of discrete-time switching systems with constrained switching sequences
- Approximating the spectral abscissa for switched linear systems via coordinate transformations
- Approximation of the Joint Spectral Radius of a Set of Matrices Using Sum of Squares
- An experimental study of approximation algorithms for the joint spectral radius
- Matrix compression along isogenic blocks
- Optimal Switching Sequence for Switched Linear Systems
- Certifying unstability of switched systems using sum of squares programming
- Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution
- Stability of linear problems: Joint spectral radius of sets of matrices
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- On random walks and switched random walks on homogeneous spaces
- Some new results on the consensus of coupled harmonic oscillators with impulsive control
- On explicit a priori estimates of the joint spectral radius by the generalized Gelfand formula
- Learning stability guarantees for constrained switching linear systems from noisy observations
- Semi-definite programming and quantum information
- Performance estimation of switched linear systems via n (n+2) generalized coordinate transformations
- Estimating the spectral abscissa for switched linear systems via square coordinate transformations
- Sparse sub-Gaussian random projections for semidefinite programming relaxations
- Computation of invariant sets for complex systems
- A hybrid approach to joint spectral radius computation
- On accuracy of approximation of the spectral radius by the Gelfand formula
- Overlap-free words and spectra of matrices
- On the computational aspects of the theory of joint spectral radius
- An explicit Lipschitz constant for the joint spectral radius
- On the joint spectral radius of matrices of order 2 with equal spectral radius
This page was built for publication: Approximation of the joint spectral radius using sum of squares
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2483273)
