A switched linear system multiplies its state, at each step, by one of a handful of matrices, and an adversary picks which one. The system is safe under every switching pattern exactly when the joint spectral radius, the worst-case long-run growth rate of these matrix products, is below one. Computing it is NP-hard. The standard certified tools, sum-of-squares (SOS) relaxations solved as semidefinite programs, either run out of memory once the state has more than a few dozen dimensions or, in the sparse variant, rely on the matrices having a special sparsity pattern. This proposal starts from a 1998 identity of Zhou that has never been turned into an algorithm. Zhou showed that an averaged, $L_{2k}$-type version of the joint spectral radius equals the ordinary spectral radius of a single linear operator, built from Kronecker (tensor) powers of the matrices. Read naively, that operator is enormous and impossible to form.
Our claim is that it never needs to be formed. Zhou's operator can be applied matrix-free, on a much smaller space of symmetric tensors, and it maps positive semidefinite matrices to positive semidefinite matrices. Plain power iteration therefore converges to an eigenvector that is itself a positive semidefinite matrix. From any iterate we can read off two-sided bounds, and a per-matrix check turns the iterate into an explicit Lyapunov certificate whose validity can be verified exactly. The result is a semidefinite-program-free route to certified upper bounds on the joint spectral radius, at a cost that grows like the cube of the lifted dimension rather than the sixth power. The study is designed to measure, rather than assume, how close this cheap certificate gets to SOS. That matters because the norm-to-spectral-radius bounds involved have so far only been proved, never benchmarked.
Core Claim
Let $\mathcal{A}=\{A_1,\dots,A_d\}\subset\mathbb{R}^{n\times n}$. Let $S_k(A)$ denote the action of $A$ on the $k$-th symmetric tensor power of $\mathbb{R}^n$. This is an $N\times N$ matrix with $N=\binom{n+k-1}{k}$, the same "Veronese lift" that underlies SOS. Because $S_k(PQ)=S_k(P)S_k(Q)$ and $\|S_k(P)\|_2=\|P\|_2^k$, Zhou's $2k$-norm joint spectral radius from The $p$-norm joint spectral radius for even integers restricts exactly to the symmetric subspace:
$$\rho_{2k}(\mathcal{A})^{2k}=\rho(\Phi_k),\qquad \Phi_k(X)=\sum_{l=1}^d w_l\,S_k(A_l)\,X\,S_k(A_l)^\top ,$$
with all weights $w_l=1$. Here $\Phi_k$ acts on symmetric $N\times N$ matrices $X$ and never touches Zhou's $n^{2k}\times n^{2k}$ matrix $F$. Since $\Phi_k$ preserves the cone of positive semidefinite matrices, any $X\succ 0$ yields certified bounds on $\rho(\Phi_k)$: if $\mu X\preceq\Phi_k(X)\preceq\lambda X$, then $\mu\le\rho(\Phi_k)\le\lambda$.
The sum dominates the maximum over products, so these bounds bracket the uniform joint spectral radius $\rho$ as $d^{-1/2k}\rho_{2k}\le\rho\le\rho_{2k}$. The sharper step is a per-matrix check on the same iterate:
$$\gamma^{2k}=\max_l \lambda_{\max}\!\left(X^{-1/2}S_k(A_l)XS_k(A_l)^\top X^{-1/2}\right)\ \Longrightarrow\ \rho(\mathcal{A})\le\gamma .$$
This holds because $p(x)=(x^{\otimes k})^\top X^{-1}x^{\otimes k}$ is then a common Lyapunov function of degree $2k$. The certificate is a lifted quadratic Lyapunov function, the object Parrilo and Jadbabaie search for by semidefinite programming, but here it is obtained from an eigenvector computation. Nonuniform weights $w_l$ let the iteration concentrate on the matrices that bind. The method has two new pieces: the matrix-free symmetric restriction of Zhou's identity, and its conversion into an exactly checkable max-form certificate. Neither appears in any paper in the file. The empirical question is how much bound quality is lost relative to optimizing the certificate by semidefinite programming, and whether the saved compute, spent on higher lift degree $k$ or larger $n$, more than repays that loss.
Relation to Prior Work
Three lines of work supply the method. Zhou's identity gives the exact spectral characterization of $\rho_{2k}$ (The $p$-norm joint spectral radius for even integers). That paper is purely analytical, flags the $M^{2k}$ dimension of $F$ as the obstacle, and applies the identity only to hand-structured wavelet masks, as do Vector subdivision schemes and multiple wavelets and Spectra of subdivision operators. We remove that obstacle generically and target switched systems. Approximation of the joint spectral radius using sum of squares supplies the lifted-Lyapunov certificate and its convergence as degree grows. We keep its certificate form but replace its semidefinite program with power iteration, accepting a possibly looser certificate in exchange for scale. Bounded semigroups of matrices shows that spectral radii of finite products converge to the joint spectral radius, which justifies the product-enumeration lower bounds we pair with our upper bounds.
Two lines of work set the competitive bar and motivate the regime we target. SparseJSR makes SOS fast by chordal decomposition, but a single dense row collapses it back to dense SOS. Our method has no sparsity assumption, so dense, moderately high-dimensional matrices are where it should win. Stability Analysis of Switched Linear Systems with Neural Lyapunov Functions attacks the same scaling barrier with ReLU polytopic norms. Its estimates can fall below the true value without regularization, and certification needs an expensive convex-hull step. Our bounds are certified by construction, with no training. Stability of Linear Systems Under Extended Weakly-Hard Constraints produces exactly the kind of lifted, denser matrix families, from deadline-miss automata, where sparsity helps less. It is our main applied testbed.
Other work in the file constrains the scope. Zając's factor-of-two inequality in Continuity of the spectrum of norm-normal matrices applies only to single norm-normal operators. Products of non-commuting switched matrices are generally not norm-normal, so we do not build on it. We only log, as a side measurement, how often individual system matrices satisfy it. The broader pattern of provable-but-unmeasured bounds, for example the conservative constants in A Local Clustering Algorithm for Massive Graphs, motivates the second half of the study. That half measures how loose the worst-case factor $d^{1/2k}$ and Zhou's condition "$\rho_4=\rho_2$ implies $\rho_\infty$ equals the same value" are on real families.
Research Program
The first part is the algorithm. For each lift degree $k\in\{1,\dots,5\}$, we form $S_k(A_l)$ sparsely from monomial index maps. We then run power iteration $X\leftarrow\Phi_k(X)/\operatorname{tr}\Phi_k(X)$ from $X=I$, which costs $O(dN^3)$ per step and $O(N^2)$ memory, and track the Collatz–Wielandt bracket and $\gamma$.
Weights are updated multiplicatively toward the matrices attaining the maximum in $\gamma$. Any positive weights preserve validity, because the certificate is checked per matrix. The final certificate is made exact by rounding $X$ to rationals and verifying positive semidefiniteness of $\gamma^{2k}X-S_k(A_l)XS_k(A_l)^\top$ by exact $LDL^\top$ factorization, a cost of one factorization per matrix. Lower bounds come from the largest $\rho(\text{product})^{1/t}$ over products up to a length budget, seeded by products suggested by the dominant terms of the Perron iterate.
The second part is the empirical study of the inequalities. On every family we report four quantities: $\rho_{2k}$, our $\gamma$, the best lower bound, and the observed ratio $\rho_{2k}/\rho$ against the worst case $d^{1/2k}$. We also record how often $\rho_4=\rho_2$ holds to numerical tolerance. This turns Zhou's bridge condition into a measured frequency rather than an untested hypothesis.
Baselines
The naive reference is the quadratic Lyapunov bound, which is our $k=1$ case optimized by semidefinite programming, together with the trivial upper bound $\max_l\|A_l\|$ and product-enumeration lower bounds. Approximation of the joint spectral radius using sum of squares reports 9.01 for the quadratic bound on its $4\times4$ non-CQLF family. Stability Analysis of Switched Linear Systems with Neural Lyapunov Functions reports 9.58 on its 2D family. Any useful lifted method must beat these numbers.
The strongest certified competitor is SOS, in dense form at low dimension and as SparseJSR, via the TSSOS library, at higher dimension. Dense degree-4 SOS reports 8.92 on the $4\times4$ family and 8.72 on the 2D family. SparseJSR reports n=120 random sparse instances solved within 12 seconds with bounds within 0.05 of the lower bound, while dense SOS exceeds 3600 seconds at n=100 (SparseJSR). On the deadline benchmarks, the paper reports only that dense and sparse bounds coincide at degree one, so no reported runtime number was found on Lacuna for that comparison.
The strongest uncertified competitor is the neural polytopic norm, which reports about 8.69 on the 2D family and gives no numeric 8D result in the file. We will retrain it with the authors' regularization, using the same wall-clock budget, and pass its output through the exact convex-hull certification step, timed. All methods share hardware, a fixed wall-clock budget per instance (60 s, 600 s, 3600 s), and the same lower bounds.
Beating the strongest baseline means one of two things. On dense families with n between 8 and 60, SparseJSR's advantage disappears, and there our certified $\gamma$ must be strictly lower than the best certified SOS bound reached within the same budget. On small families, $\gamma$ must come within 1% of the SOS bound at equal degree, for example at most about 9.01 against 8.92 on the $4\times4$ family, at under 1% of its runtime.
Two ablations isolate the key ingredient. The first optimizes $X$ by semidefinite program at the same $k$, which measures exactly what power iteration gives up. The second uses unit weights instead of reweighted iteration, which measures the value of reweighting.
Why not just…?
Why not just form Zhou's matrix $F$ and call a dense eigensolver? At $n=10$ and $k=2$, $F$ has $10^4$ rows, and at $k=3$ it has $10^6$. Its spectral radius is also only $\rho_{2k}$, which can sit above $\rho$ by up to $d^{1/2k}$. Our symmetric restriction cuts the dimension to $N=55$ at $n=10$ and $k=2$, and the per-matrix certificate removes most of the $d^{1/2k}$ slack. The ablation comparing $\rho_{2k}^{1/2k}$-type bounds with $\gamma$ measures that slack directly.
Why not just use SparseJSR or a higher-degree SOS program? On sparse matrices this is a real threat, and we expect SparseJSR to tie or win there. The 0.05 gap is hard to beat, so we report this regime honestly as a loss or a tie. The proposal's bet is the dense regime, where chordal extension gives a single clique. There the semidefinite program needs $O(N^2)$ variables against our $O(N^2)$ memory and simple matrix products. The equal-budget dense sweep settles it: if SOS still wins within 3600 s at n=30 with dense matrices, the method has no niche, and we will say so.
Why not just train a regularized neural Lyapunov function? Its raw estimate can be optimistic, and its certification step "remains computationally intensive" (Stability Analysis of Switched Linear Systems with Neural Lyapunov Functions). We compare certified-bound-versus-time curves, including certification time, on its 8D family and on our dense families. A polytopic norm could be tighter than any degree-$2k$ lift on some instances, and that would show up as the neural curve crossing below ours.
Why not just enumerate products? Enumeration gives lower bounds only, and its upper bounds via $\max\|P\|^{1/t}$ converge slowly. We use it as the lower-bound reference rather than as a competitor.
Proposed Experiments
The suite reuses the $4\times4$ non-CQLF family, the 2D and 8D families of Debauche et al., the Erdős–Rényi sparse families of SparseJSR at n=20 to 120, and the deadline-miss lifted families of SparseJSR and Vreman et al. It adds a dense random suite (Gaussian, orthogonal-times-diagonal, and highly non-normal Jordan-perturbed matrices, with n from 8 to 60 and d from 2 to 8) where no reported result exists on Lacuna.
As a stretch application, we compute certified bounds for small Garnet MDP instances from A First-Order Approach to Accelerated Value Iteration. The relevant matrices are the momentum-iteration matrices induced by the policies the algorithm visits. These bounds would give the first measured spectral explanation of when acceleration diverges on non-reversible chains. Metrics are certified upper bound, gap to the best lower bound, wall-clock to reach a target gap, peak memory, and the fraction of certificates passing exact verification.
Two outcomes would be decisive. The first is whether, on dense families with n of at least 20, the power-iteration certificate at the largest $k$ that fits the budget beats the best SOS bound obtainable in the same time. The second is whether, on the small benchmarks, the semidefinite-program ablation shows less than 1% loss. If the first fails, the work reduces to a measurement study of Zhou's inequalities. That study is still worth reporting, but the claim of a scalable certifier would be withdrawn.
References
- The $p$-norm joint spectral radius for even integers
- Vector subdivision schemes and multiple wavelets
- Spectra of subdivision operators
- Approximation of the joint spectral radius using sum of squares
- Bounded semigroups of matrices
- SparseJSR: A Fast Algorithm to Compute Joint Spectral Radius via Sparse SOS Decompositions
- Stability Analysis of Switched Linear Systems with Neural Lyapunov Functions
- Stability of Linear Systems Under Extended Weakly-Hard Constraints
- Continuity of the spectrum of norm-normal matrices
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
- A First-Order Approach to Accelerated Value Iteration