Certified Gaps for Joint Spectral Radius Methods

A switched linear system is one whose update matrix changes at every step, chosen from a fixed finite set $\{A_1,\dots,A_m\}$. Its worst-case growth rate over all switching sequences is the joint spectral radius (JSR). When the JSR is below one, every trajectory decays. Computing it exactly is intractable, so methods report bounds instead. Sum-of-squares programs, sparse variants of them, and neural Lyapunov functions all publish numbers on small toy examples, and the numbers are then compared across papers. These comparisons are often invalid. Some reported numbers are guaranteed upper bounds. Others are estimates from sampled points that can fall below the true value. None come with a matching lower bound, so nobody knows how close any of them is to the truth.

This proposal applies one elementary inequality at both ends of the problem. For any norm on the state space, the largest induced gain of the $A_i$ bounds the JSR from above. The spectral radius of any finite product, taken to the power one over its length, bounds it from below. Using this, we build an exact checker that turns every method's output into a certified interval. We then run all major methods under matched time budgets on the benchmarks the literature already uses. Two questions drive the study. First, does the reported advantage of neural Lyapunov functions survive once their bounds are certified? Second, does a polytope norm stored as a list of vertices, which can be checked with linear programs alone, give the smallest certified gap per second on the dense instances where sparse methods lose their speedup?

Core Claim

For any norm $N$ with induced operator norm $\|\cdot\|_N$, and any finite product $A_{i_k}\cdots A_{i_1}$,

$$ \big(\rho(A_{i_k}\cdots A_{i_1})\big)^{1/k} \;\le\; \mathrm{JSR}(\mathcal M) \;\le\; \max_i \|A_i\|_N , $$

where $\rho$ is the ordinary spectral radius (largest eigenvalue magnitude). This is the norm–spectral radius inequality $\rho(A)\le\|A\|$ lifted to matrix families. Every JSR method produces, explicitly or implicitly, a candidate norm or Lyapunov function, so every method can be scored by an exactly computed right-hand side paired with a searched left-hand side.

Our claims are empirical and falsifiable. First, the neural bound reported on the 2D benchmark, about 8.69 in Stability Analysis of Switched Linear Systems with Neural Lyapunov Functions, is not directly comparable to the certified degree-4 sum-of-squares value of 8.72 from the same paper. Second, the "Efficiency Flip" that paper reports on its 8D system, where networks become cheaper than sum-of-squares in higher dimension, should be re-measured with certification time counted. Third, a vertex-represented polytope norm whose gain is computed with linear programs is a stronger cost–tightness competitor on dense instances than any of the published methods, and has not been benchmarked against them.

What Prior Work Gives and Withholds

Three lines of work supply the methods we audit. Approximation of the joint spectral radius using sum of squares searches over higher-degree polynomial Lyapunov functions with semidefinite programming. It proves a dimension-dependent tightness factor, and its only evaluation is a single 4×4 example: 8.92 at degree 4, 9.01 quadratic, 9.88 for an earlier lifting method, with no timings. SparseJSR splits the same programs along sparsity patterns. It reports that dense sum-of-squares "takes over 3600 seconds" at size 100 while SparseJSR "handles matrices of size 120 within 12 seconds," with bounds "often within 0.05" of a lower bound. It also concedes that a single dense row destroys the speedup. Debauche et al. use ReLU networks, whose outputs are piecewise linear, as Lyapunov functions. They identify an "overfitting trap" in which unregularized training underestimates the JSR, and they note that making the bound formal requires an expensive convex-hull step. Stability Verification for Switched Systems using Neural Multiple Lyapunov Functions certifies mode-dependent networks with a satisfiability solver that the file reports struggles beyond about four dimensions.

We reuse all of these as competitors. What we add is a single exact checker applied to all of them, together with lower bounds, which none of them report systematically.

Norm–spectral theory supplies two ingredients and rules out a third.

The first ingredient comes from The $p$-norm joint spectral radius for even integers. Zhou shows that for $p=2k$ the $p$-norm JSR equals $\rho(F)^{1/2k}$ for a single Kronecker-lifted matrix $F$. Here the $p$-norm JSR is the growth rate of the sum of $p$-th powers of product norms, rather than their maximum. Because a sum of $m^n$ terms lies between the largest term and $m^n$ times it, this gives the sandwich

$$ m^{-1/2k}\rho(F)^{1/2k}\le \mathrm{JSR}\le \rho(F)^{1/2k}. $$

Zhou treats $F$ as too large to form, since it has size $M^{2k}\times M^{2k}$ for $M$-dimensional matrices. However, $F$ acts on a vector as $X\mapsto\sum_l A_l^{\otimes k} X (A_l^{\otimes k})^{*}$, a map that sends positive semidefinite matrices to positive semidefinite matrices. Its spectral radius can therefore be found by power iteration without ever forming $F$, using memory of order $M^{2k}$ rather than $M^{4k}$. We implement this matrix-free version as the cheapest certified baseline, which was never benchmarked in the original work.

The second ingredient comes from The finiteness conjecture for the generalized spectral radius of a set of matrices. Lagarias and Wang prove that polytope norms admit extremal products of bounded length. This motivates both the product search on the lower-bound side and the polytope norm on the upper-bound side. We will also report the observed extremal product lengths against their bounds, which they call "unreasonably large."

The idea we rule out is Zając's result in Continuity of the spectrum of norm-normal matrices, that $\|A\|\le 2\rho(A)$. This holds for a single operator that is "normal" with respect to a given norm. It says nothing about products of several non-commuting matrices, which are generally not simultaneously normal in any shared norm. We therefore reject the tempting plan of using this factor-of-2 bound to regularize neural Lyapunov training. It would not yield a certificate.

Research Program

The central artifact is an independent checker. For a polytope norm stored as the convex hull of symmetric vertices $\{\pm v_j\}$, evaluating the norm of a vector is a linear program. The induced gain $\|A_i\|_N$ is attained at a vertex, so it equals $\max_j N(A_i v_j)$, which costs $m\cdot J$ linear programs for $J$ vertices. This avoids facet enumeration, which is the step that makes convex-hull certification expensive in higher dimension.

The checker handles the other method families as follows. For bias-free ReLU networks, which are positively homogeneous, the certified gain is $\max_i \max\{V(A_i x) : V(x)\le 1\}$. We compute it by mixed-integer programming where that is feasible. We also offer a cheap sound conversion: take the convex hull of sampled points on the network's unit level set and certify that polytope with linear programs. For sum-of-squares outputs, we inflate $\gamma$ until the rounded Gram matrices pass an eigenvalue test with a numerical safety margin.

The lower bound on every instance comes from a product search. This is branch-and-bound over products up to a length budget, pruned by the current best $\rho^{1/k}$.

The polytope competitor starts from the orbit of a leading eigenvector of the best product found. It then adjusts vertex positions by subgradient descent on $\max_{i,j} N(A_i v_j)$, using the dual solutions of the linear programs as gradients. We connect this to the polytopal iteration of Nonlinear Joint Spectral Radius, which that paper tests only on 2×2 cone maps. Our contribution is not the polytope idea itself. It is gradient refinement of the vertices plus certified, time-matched comparison against neural and sum-of-squares methods.

Baselines

The naive reference point costs almost nothing: $\max_i \rho(A_i)$ as the lower bound and $\max_i\|A_i\|_2$ as the upper bound. Any method that fails to shrink this interval meaningfully within its time budget adds nothing.

The ellipsoidal baseline is the common quadratic Lyapunov function, solved as a single linear matrix inequality. The file reports it at 9.58 on the 2D benchmark and 9.01 on the 4×4 benchmark.

The strongest certified baselines are dense degree-4 and degree-6 sum-of-squares, following Parrilo and Jadbabaie, and SparseJSR. SparseJSR is the strongest reported method at scale ("within 12 seconds" at size 120, bounds "often within 0.05" of the lower bound). Dense sum-of-squares is the strongest on the 2D benchmark, at a certified 8.72.

The strongest neural competitor is Debauche et al.'s regularized network, reported at about 8.69. We run it in two forms: its raw sample-based output, and the same network after our certification.

The matrix-free Zhou bound runs at $k=1,\dots,4$.

All methods run on the same machine and the same instances, with one semidefinite solver shared by all sum-of-squares variants. Each method gets wall-clock budgets of 1, 10, 100, and 1000 seconds, and certification time counts against the budget. Neural and polytope methods get the same hyperparameter-search allowance.

The ablation that isolates our key ingredient compares the polytope built from the eigenvector orbit alone with the gradient-refined polytope. A second ablation compares the neural network's raw number with its certified number.

Beating a baseline means a strictly smaller certified relative gap, (upper − lower)/lower, at equal budget, on a majority of instances in a family. On the 2D benchmark specifically, it means a certified upper bound below 8.72.

Why not just…?

Why not just rerun the existing codes on a shared instance set? That is half the study, and on its own it reproduces the current confusion. Debauche et al.'s raw bounds come from samples. Their own overfitting-trap finding shows such bounds can sit below the truth. Tabulating them next to certified sum-of-squares values would repeat the invalid comparison. The contribution is the common checker and the lower bounds. If certification never changes any ranking, that is a clean negative result and we will report it.

Why not just raise the sum-of-squares degree? Sum-of-squares is asymptotically tight, but the file reports dense runs exceeding 3600 seconds at size 100. SparseJSR's escape from that cost depends on sparsity, which it admits fails with one dense row. Our dense-row perturbation experiment tests exactly this regime. If degree-6 sparse or dense sum-of-squares still wins at equal time there, the polytope claim fails.

Why not just use Zhou's exact formula? The sandwich above caps its accuracy at a factor of $m^{1/2k}$. For $m=2$ and $k=4$ that is about 9%, so reaching 1% would need $2k$ near 70. The 9.88 "lifting" figure in Parrilo and Jadbabaie illustrates this looseness. We include the formula precisely because it is the cheapest certified bound, and we will measure how far its observed gap sits from the worst-case factor.

Why not just enumerate products? Enumeration gives only lower bounds, and the length bound $g(n-1,m)$ from Lagarias and Wang is impractical. We use pruned product search strictly for the lower side of the interval.

Why not regularize neural Lyapunov functions with the factor-of-2 bound, as the research file's Gap 2 suggests? As argued above, that bound concerns a single norm-normal operator and yields no certificate for a family of matrices.

Proposed Experiments

The instance families are those in the file. They are the 2D and 8D systems of Debauche et al. (no numbers are reported on Lacuna for the 8D JSR values or runtimes), Parrilo and Jadbabaie's 4×4 system without a common quadratic Lyapunov function, SparseJSR's Erdős–Rényi sparse matrices up to size 120, and the weakly-hard process-plant model from Stability of Linear Systems Under Extended Weakly-Hard Constraints (no reported result found on Lacuna for its JSR values). We also include the refinement matrices of Zhou's Hermite interpolants (no reported result found on Lacuna). We add two stress families: dense random ensembles for $n$ from 4 to 30, and Erdős–Rényi matrices with one row filled in. The main outputs are certified-gap-versus-time curves, plus the rate at which a method's reported number falls below the best certified lower bound.

The decisive checks are three.

The first is on the 2D benchmark. If our product search finds a lower bound above 8.69, the published neural figure is certifiably unsound. If our checker certifies the network below 8.72, the neural advantage there is real.

The second is on the 8D and dense families. Here we test whether the Efficiency Flip survives with certification time included, or whether sum-of-squares or the vertex polytope overtakes the network. We expect the polytope's vertex count to become the limiting cost somewhere above roughly $n=15$. If networks win in that range after certification, we will report it as the regime where neural representations genuinely pay off.

The third is on the dense-row family. This measures whether SparseJSR's reported speedup collapses as its authors predict, and which certified method best fills the gap.