Approximating the Joint Spectral Radius for Switched Systems

23 concepts18 papers3 proposals

To understand the stability of a standard linear dynamical system $x_{t+1} = Ax_t$, we look at the eigenvalues of the matrix $A$. If its spectral radius $\rho(A)$—the largest absolute value of its eigenvalues—is strictly less than one, every trajectory eventually decays to equilibrium.

But what happens if the system's rules change over time? Consider a switched linear system, where at each time step an operator or an environmental disturbance selects a matrix from a finite set $\mathcal{M} = \{A_1, A_2, \dots, A_m\}$. The state evolves under an arbitrary sequence of choices:

$$x_{t} = A_{i_{t-1}} \dots A_{i_1} A_{i_0} x_0$$

To guarantee that this system is stable under any possible switching sequence, we must quantify the worst-case asymptotic growth rate of these matrix products. This value is known as the Joint Spectral Radius (JSR).

If the JSR is less than one, the system is stable under arbitrary switching. However, computing this value is notoriously difficult. While the spectral radius of a single matrix is easy to find, the JSR depends on an infinite horizon of non-commuting matrix products. As shown by Pablo A. Parrilo et al. in Approximation of the joint spectral radius using sum of squares, the JSR of a set of rational matrices is not a semi-algebraic function. This means there is an inherent mathematical barrier: we cannot compute it exactly using standard algebraic formulas. Instead, verifying stability is an NP-hard and potentially undecidable problem (Virginie Debauche et al. in Stability Analysis of Switched Linear Systems with Neural Lyapunov Functions), creating severe computational bottlenecks in applications ranging from wavelet design (Rong-Qing Jia et al. in Vector subdivision schemes and multiple wavelets) to accelerated value iteration in reinforcement learning (Julien Grand-Clément in A First-Order Approach to Accelerated Value Iteration).

To bypass this intractability, modern research focuses on clever approximations, relaxations, and structural abstractions that bound the JSR.

The Finiteness Horizon

A natural question arises: is the maximal growth rate of a matrix set always driven by a specific, finite periodic sequence of matrices? This idea, known as the finiteness conjecture, was deeply investigated by J. C. Lagarias 0001 in The finiteness conjecture for the generalized spectral radius of a set of matrices.

The author demonstrated that the finiteness conjecture is equivalent to a "normed finiteness conjecture" concerning operator norms. By establishing explicit bounds for the required product lengths under specific classes of norms (such as polytope and Euclidean norms), this work showed that for many practical systems, worst-case behavior can indeed be characterized by a finite sequence. However, because the required sequence length can be arbitrarily long in the general case, direct brute-force computation remains impossible, necessitating optimization-driven approximations.

Collapsing Infinity via Algebraic Relaxations

If we cannot evaluate every sequence, how do we find a reliable upper bound for the JSR? The answer lies in finding a shared mathematical yardstick—such as a common norm or a Lyapunov function—under which every matrix in the set shrinks the state vector.

The Even Integer $p$-Norm Trick

One elegant way to collapse the infinite combinatorial explosion of matrix sequences into a single calculation is to change how we measure vector lengths. In The $p$-norm joint spectral radius for even integers, Ding‐Xuan Zhou proved that when evaluating the JSR using $p$-norms where $p$ is an even integer, the problem simplifies dramatically.

Because even powers eliminate absolute values, the average growth rate of the system can be mapped directly to the Kronecker (tensor) powers of the matrices. This mathematical property allows the joint growth rate to be determined by calculating the standard spectral radius of a single, integrated, albeit much larger, matrix.

Sum of Squares Programming

A more general approach to finding these bounding norms is semidefinite programming. A system is stable if we can find a single quadratic Lyapunov function $V(x) = x^T P x$ that decreases under every matrix: $A_i^T P A_i - P < 0$ for all $i$.

To obtain tighter bounds, Pablo A. Parrilo et al. (Approximation of the joint spectral radius using sum of squares) introduced the use of higher-degree polynomial Lyapunov functions. Verifying that a high-degree polynomial is globally positive is typically hard, but it becomes tractable if we restrict the polynomial to be a Sum of Squares (SOS). By leveraging SOS programming, researchers can systematically compute a sequence of increasingly precise upper bounds on the JSR.

To scale this method to high-dimensional systems where standard SOS programming suffers from the curse of dimensionality, Jie Wang et al. developed SparseJSR in SparseJSR: A Fast Algorithm to Compute Joint Spectral Radius via Sparse SOS Decompositions. By exploiting the structural sparsity of the matrix sets, SparseJSR breaks down a massive, monolithic SOS problem into smaller, loosely coupled optimization tasks, drastically accelerating upper-bound verification.

Graph-Theoretic Frameworks for Constrained Switching

In many real-world settings, switching is not completely arbitrary. For example, in an embedded control system experiencing occasional deadline misses (Nils Vreman et al. in Stability of Linear Systems Under Extended Weakly-Hard Constraints), the sequence of physical modes is strictly governed by a real-time task scheduler. This introduces a "grammar" or constraint on which matrix can follow another, modeled by a finite automaton. This variant is known as the Constrained Joint Spectral Radius (CJSR).

To analyze these systems, Raphaël M. Jungers developed algorithmic frameworks in Stability of discrete-time switching systems with constrained switching sequences to estimate the CJSR within a guaranteed relative error by directly embedding the automaton's transition graph into the optimization process.

Arbitrary Switching:      [Any Matrix] ---> [Any Matrix] ---> [Any Matrix]

Constrained Switching:    [Matrix A]  ---> [Matrix B]  -X-> [Matrix A] (Forbidden!)

This integration of graph theory and control algebra was formalized by Amir Ali Ahmadi et al. in When is a set of LMIs a sufficient condition for stability? and Joint Spectral Radius and Path-Complete Graph Lyapunov Functions. Instead of forcing a single Lyapunov function to work for every matrix, they assigned different Lyapunov functions to different nodes in a graph.

The authors proved a fundamental meta-theorem: a set of localized Linear Matrix Inequalities (LMIs) forms a valid, sufficient condition for global stability if and only if the underlying combinatorial structure of the inequalities forms a path-complete graph. This means that every valid sequence of matrix transitions allowed by the system's grammar can be mapped to a continuous path of algebraic contractions in the graph. This framework unifies decades of heuristic stability criteria into a single combinatorial rulebook (Amir Ali Ahmadi et al. in A Characterization of Lyapunov Inequalities for Stability of Switched Systems).

To understand the fundamental limits of these methods, Benoît Legat et al. introduced an information-theoretic lens in An Entropy-Based Bound for the Computational Complexity of a Switched System. They demonstrated that the computational complexity of approximating the JSR is directly bounded by the topological entropy of the constraining automaton, proving that tighter grammatical constraints naturally reduce the algebraic complexity of stability verification.

Certifying Instability via Duality

While upper bounds prove that a system will safely decay, how do we definitively prove that a system is unstable? To certify instability, we need a reliable lower bound on the JSR and an explicit worst-case trajectory that grows over time.

In Certifying Unstability of Switched Systems Using Sum of Squares Programming, Benoît Legat et al. solved this by exploiting mathematical duality. In optimization, the dual of searching for a shape (like a Lyapunov function) is searching for a density or a flow. The authors paired Lyapunov functions with occupation measures, which track the statistical distribution of system trajectories over time.

By maximizing these occupation measures using SOS programming, the optimization engine switches from looking for a "shield" (a Lyapunov function proving stability) to looking for a "river" (a steady flow of energy pushing a trajectory outward). This dual formulation yields rigorous lower bounds on the JSR and extracts explicit, unstable switching sequences.

Non-Standard Frontiers: Neural Networks and Tropical Geometry

As systems scale and break away from classical linear assumptions, two emerging frontiers are redefining how we compute growth metrics.

Neural Lyapunov Functions

Instead of restricting searches to polynomial shapes via SOS, Virginie Debauche et al. (Stability Analysis of Switched Linear Systems with Neural Lyapunov Functions) proposed training neural networks with Rectified Linear Unit (ReLU) activations to act as Lyapunov functions.

Crucially, the authors provided the first theoretical correctness guarantees for this approach by proving that ReLU networks are structurally equivalent to complex, polytopic Lyapunov functions. This allows gradient-based machine learning methods to discover highly non-convex stability boundaries in high dimensions that frustrate traditional semidefinite toolboxes.

Max-Plus Algebra and Tropical Kraus Maps

In certain applications, such as discrete-event routing or stochastic max-plus systems (Ioannis Kordonis et al. in Stochastic Stability in Max-Product and Max-Plus Systems with Markovian Jumps), the underlying operations are not addition and multiplication, but maximum and addition.

To approximate growth rates in these non-standard algebraic structures without relying on expensive LMI solvers, Stephane Gaubert et al. introduced tropical Kraus maps in Tropical Kraus maps for optimal control of switched systems. Inspired by quantum information theory, this method replaces standard matrix arithmetic with a supremum-based matrix ordering. This algebraic shift allows researchers to compute value functions and JSR bounds via highly scalable, first-order fixed-point iterations, bypassing semidefinite optimization entirely.

Key Foundational Work

The finiteness conjecture for the generalized spectral radius of a set of matrices (1995) — contributed 2 concept elements to this direction.
The $p$-norm joint spectral radius for even integers (1998) — contributed 1 concept elements to this direction.
Vector subdivision schemes and multiple wavelets (1998) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_joint_spectral_radius_computation_c28e5bec,
  title = {joint spectral radius computation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/joint-spectral-radius-computation/rdr_c28e5bec5c674e218abc9cb6a4ba0ef0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_joint_spectral_radius_computation_c28e5bec_v1,
  title = {joint spectral radius computation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/joint-spectral-radius-computation/rdr_c28e5bec5c674e218abc9cb6a4ba0ef0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake