CS Paper Radar

Beyond Unit-Circle Eigenvalues: Invariant Bases for Stable State Space Dynamics

Jiaqian Zhu, Yang Zhang, Junhua Ding, Xiaowei Yu

cs.LG ·submitted 2026-11-01 20:23 UTC · v2
top venuecode/dataunusual

Abstract

Diagonal state space models process long sequences at linear cost, yet the same transition is applied at every step of a rollout, so an unconstrained recurrence holds no quantity fixed and the state decays or grows without bound. Current designs constrain one quantity, and preserving one does not guarantee preservation of the others, so a model can hold its norm to machine precision while momentum drifts by hundreds of percent. We claim that the conserved quantities of a diagonal recurrence are layered, that each layer requires a strictly stronger condition on the operator, and that a unit-modulus spectrum reaches only the outermost. Acting on the claim, we enforce the conditions required for every layer by construction. The generator of the Kronecker-Cayley transition (KC) is a graph Laplacian over object subspaces, $\mathbf{H}=\mathbf{L}\otimes I_m$, advanced by a Cayley transform, and the step stays diagonal at $O(N^3+N^2m)$ cost. The conserved set is exactly a $2m^2$-dimensional family of quadratic forms, held at every parameter value, so the quantities and the dynamics the construction reaches are fixed before training. On four conservation benchmarks, KC holds total mass at or near the reference floor while every diagonal baseline loses it by orders of magnitude. We further compare against mass correction and find that two correctors fail once the underlying prediction diverges, which shows that assembly rather than correction is necessary for a guarantee that holds across the rollout. A free modal basis trained under a conservation penalty conserves only by freezing its spectrum, whereas the assembled operator conserves with every mode but one free to rotate. Beyond these benchmarks, KC holds the linear momentum of three $N$-body systems and, at the operator level, the conserved quantity in molecular dynamics, chemical kinetics, pharmacokinetics and power-grid swing dynamics.

Comment
Accepted at NeurIPS 2026. 40 pages, 13 figures, 27 tables. Code: https://github.com/Jiaqian-Janelle/NeurIPS26-Kronecker-Cayley-Stable-State-Space-Dynamics

Closest papers

Nearest neighbours by meaning across the whole index.

The Komlós Problem in Matrix-Multiplication Time

cs.DS cs.DM ·2026-10-14 ·Emile Anand, Peter Chen
similarity 0.55
Abstract · 30 pages

We give a randomized algorithm that, for an $m\times n$ matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below $99$ in expected $\widetilde O(L_{\mathrm{in}}+n^ω)$ bit operations, where $L_{\mathrm{in}}$ is the input encoding length and $ω$ is the exponent of matrix multiplication. The previous fastest algorithm with a constant discrepancy bound, due to Li, is deterministic and uses $O(mn+n^{ω+2}\log^3 n)$ arithmetic operations. We build on the spectral signing framework of Guo, Fang, and Lu and of Li, which rounds a single fractional coloring while one spectral potential controls every row. Li's potential tracks a top eigenvalue, and the gap below that eigenvalue, which can be of order $1/n$, limits the length of every step. We replace it with a resolvent potential that is smooth without any gap condition, and we draw step signs at random, so that the potential only needs to be concave while progress is measured separately. Our key insight is to reuse a single subspace of directions throughout a batch of steps, thereby using only one spectral computation, so that the more expensive linear algebraic operations are paid for only polylogarithmically often at each scale. Within a batch, we sample directions from a Gaussian completion matrix whose inverse we maintain under rank-one row replacements. Finally, we use a finite-precision analysis to prove stability of the algorithm and attain the bit-complexity bound.

0.39

Uniformly Stable Minimal Weyl--Heisenberg Measurements Approaching the SIC Benchmark

cs.IT quant-ph ·2026-08-12 ·Xiuwu Zhu, Yu Wang
benchmark similarity 0.54
Abstract

Informational completeness (IC) guarantees that an inverse exists, not that it is statistically well conditioned. For minimal rank-one Weyl--Heisenberg (WH) measurements, covariance makes the nonidentity projector-Gram spectrum proportional to the fiducial's ambiguity intensities, with eigenvalues \(d|χ_φ(u)|^2\), turning stability into an explicit worst-direction design problem; write \(λ\) for its smallest nonidentity eigenvalue. Haar fiducials are IC almost surely while \(\mathbb E[λ^{-1}]=\infty\), and an explicit geometric family used to establish balanced informationally complete measurements in every dimension has a normalized spectral floor bounded above by an exponentially decaying envelope. We then construct a hierarchy of minimal measurements. A cyclic family with exactly \(d^2\) outcomes in every integer dimension has floors \(Θ(d^{-3})\) for odd \(d\) and \(Θ(d^{-5})\) for even \(d\); a finite-field family for \(q=2^m\) obeys the uniform bound \(λ\ge4/9\). Our main result treats every prime-power dimension of characteristic \(p\ge5\). A balanced one-coordinate perturbation repairs the zero ambiguity axis of a cubic Alltop state, gives an attained floor uniformly bounded below by a positive constant, and confines the entire nonidentity spectrum to \([L_q,U_q]\) with \(U_q/L_q\to1\). Its SIC-normalized minimum tends to one, and \(λ(φ_q)/Λ_q^\star\to1\) for the global finite-field WH max--min optimum \(Λ_q^\star\), without assuming SIC existence. The complete spectrum determines the exact finite-sample Hilbert--Schmidt error of canonical linear inversion at \(I/d\), while its lower edge controls local Fisher efficiency and canonical-shadow bounds.

0.41

A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture

cs.DS math.FA ·2026-09-16 ·Tarun Kathuria
similarity 0.54
Abstract · The author explicitly reserve all rights in this work. No permission is granted for the reproduction, storage, or use of this document for t…

\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most $35\sqrt\varepsilon$. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance vanishes as the coefficients reach their endpoints. Inspired by the free interpolation approach of Bandeira, Boedihardjo, and van Handel \cite{bbvh2023}, we combine Lehner's variational formula \cite{lehner1999} with spectral Tsallis--$1/2$ regularization used in \cite{allenZhuLiaoOrecchia2015} and \cite{pesentivladu2026}. The resulting potential has a finite-dimensional SDP formulation, allowing the discrepancy and remaining covariance to be analyzed together. We analyze the optimizer's stability through the linearized Karush--Kuhn--Tucker (KKT) system of a regularized min--max problem, whose stationarity equations are related to the matrix Dyson equation \cite{erdos2019}. This gives the movement rule: either a coordinate can move toward its nearer endpoint at small spectral cost, or a low-curvature direction orthogonal to the current coefficient vector allows further progress. Choosing the better sign of this direction controls discrepancy while increasing the squared distance from the origin. Upcoming work \cite{kathuria2026higherRank} will address higher-rank Kadison-Singer and spectrally thin trees. Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

0.56

A Memory-Magic Exchange Law in Streaming Clifford+T Compilation

cs.IT quant-phmath.NT ·2026-09-29 ·Jinze Yang, Yangyang Li, Xiu-Hao Deng
code/data similarity 0.54
Abstract · 39 pages, 2 figures. v2: unconditional rate improved from 17/7 to every alpha < 5/2 (Theorem 8, Appendices G-H, exact SMT check). Code, data…

A phase that reaches a fault-tolerant processor in additive pieces can be remembered until the last piece arrives, or executed on arrival: the first option costs classical memory carried across rounds, the second costs magic states committed before the phase is known. We determine the exchange rate $α$, committed $T$ gates per bit of memory forgone, for ancilla-free coordinatewise Clifford+$T$ compilation. The Ramanujan bound gives $α\ge2$ with explicit constants, the square-root barrier of the spectral method. An elementary determinant method, using that quaternion numerators lie on spheres in both real embeddings of $\mathbb{Q}(\sqrt2)$, counts words near any rotation coset below that barrier. With a height dichotomy for the sphere sections it produces and a fibration over rational projections, it gives every $α<5/2$ unconditionally and uniformly over frames, by an exact SMT check of its continuum case analysis; $5/2$ is where this method stops. At Clifford-framed cosets the volume law holds up to subexponential factors: all but a vanishing fraction of $z$-rotations need $T$-count $(3-o(1))\log_2(1/\varepsilon)$, and processes whose committed pieces are near Clifford-framed $z$-rotations, including per-rotation pipelines, have $α\ge3-o(1)$, which a fractional-passthrough family attains under the Ross-Selinger typical-cost hypothesis. Under an equidistribution conjecture supported by exhaustive enumeration to $T$-count 22, $α=3$ in general and memory should be shed in whole rotations. The bounds hold even when the phases cancel to the identity; side information enters through a conditional entropy; probabilistic mixing halves the costs but not the rate. With clean ancillas and a phase-gradient catalyst, table lookups batched over coordinates drive the rate to $O(1/\log\log(1/\varepsilon))$, so the constant-rate law is specific to coordinatewise synthesis.

0.46

Thermal Recurrence Orders of the Potts Model Partition Function in Grid Graphs

cs.DM math-ph ·2026-08-22 ·Yi-Zhong Wang
publishedtheory similarity 0.54
Abstract · 28 pages, 2 figures, 3 tables

We study the linear recurrence order of the Potts model partition function on thermal 2D grid graphs. By restricting the transfer matrix (TM) to the real coupling axis, the physical operator maintains diagonalizability under the Spectral Theorem. We show that this thermal regularization allows the Krylov subspace to saturate the unconstrained planar state capacity, locking the recurrence order to the Dyck path up to reversal (OEIS A007123) for $q \ge 4$. Furthermore, the recurrence order collapses to height-restricted Dyck paths up to reversal (OEIS A001998) for $q=3$ due to finite-index Jones-Wenzl projections, and to the zero-magnetization conservation sector (OEIS A001405) for $q=2$. This framework bridges graph-theoretic combinatorics with the representation theory of physical loop gas models.

0.39

Learning Clifford-structured quantum unitaries and Hamiltonians

cs.CC quant-ph ·2026-08-10 ·Arkopal Dutt, Dale Jacobs, John Jeang, Saeed Mehraban, Vladimir Podolskii
similarity 0.53
Abstract

Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i α_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |α_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $Ω(2^n)$) in the Pauli basis but are Clifford structured.

0.42

Score the Algebra, Not the Span: Dimension Reduction for Transfer Operator Models of Dynamical Systems

cs.LG ·2026-08-19 ·Mark Kozdoba, Shie Mannor
benchmark similarity 0.53
Abstract

Dimension reduction for dynamical systems is standard practice, and the standard route is spectral: model the transfer (Koopman) operator by its leading modes. We show that on systems assembled from several weakly interacting components --- a structure common in physical and biological settings --- this may either require an exponential number of modes, or drop an entire component: the component is absent from the model rather than modeled coarsely, and no function of it can be predicted at any accuracy. We call this linear masking. The cause is that a rank-based model pays one coordinate per mode. We propose to score instead the $σ$-algebra the coordinates generate, so that products and powers come free and a component's cost is governed only by its generators rather than by all its interactions. The criterion is a $χ^2$-divergence between the embedded present and future, and it carries a budget guarantee: twice the intrinsic dimension of the dynamics is enough coordinates for an embedding whose algebra carries the operator's entire spectrum, with its full infinite rank. In variational form the criterion admits off-the-shelf estimators, and restricting its critic to the bilinear class returns the VAMP score on the span, so rank-based methods are one end of the same family. We demonstrate the proposed objective on a composite of published benchmark systems. We exhibit examples where the rank-based methods completely miss the masked components at all ranks $k<100$, while ten algebra coordinates recover all of them. In addition, the resulting algebra representation supports predicting the masked components from few labels, while direct regression from the high-dimensional observation or from the VAMP features fail.

0.26

Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses

cs.DS math.PR ·2026-09-13 ·Huibo Xu, Shi Fu, Youming Qiao, Dacheng Tao
theory similarity 0.53
Abstract · 79 pages

Graph matrices encode dependencies in random matrices built from shared random variables and arise in spectral algorithms, sum-of-squares (SoS), and high-dimensional statistics. We determine how finite graph structure controls their sharp spectral growth. For every fixed simple graph shape in the dense Rademacher model, including overlapping or empty matrix boundaries, we prove $\mathbb E\|M_α\|=Θ_α(n^{(v+h-s)/2}(\log n)^{a_*/2})$, where $v$ counts vertices, $h$ isolated summation vertices, $s$ the minimum boundary-separator size, and $a_*$ maximizes an active-component count over minimum separators. Thus two finite cut optimizations determine both the polynomial and logarithmic exponents. The formula closes the polylogarithmic gap in separator bounds, and an infinite family with identical coarse parameters but different norms shows that the logarithmic exponent records genuinely new structure. The proof controls all defect layers in growing trace moments by converting label loss into separator excess; conditional flattening and synchronized fluctuations yield matching lower bounds. We extend the analysis to specified independent-factor chaoses, local weights, unequal dimensions, bounded asymmetric noise, Gaussian inputs, and fixed-degree Hermite inputs. Applications include degree-four clique SoS feasibility for $9\le k\le c\sqrt n$ without an asymptotic logarithmic loss, and Gaussian random tensor networks: deviation thresholds, sharp expected scales, entropy estimates, and, for connected loopless equal-dimensional networks, convergence of the rescaled largest output eigenvalue to the exact right edge of the limiting law. These results connect finite structure to sharp growth scales, and additional algebraic and spectral structure to full feasibility and exact limiting constants.

0.32