OctoInformBeta

OpenAI preprint, September 2026 · §4. Matrix variation along the filter · §4

Lemma 4.1 [Weighted increment estimate]: Over good, fresh, distinct filter steps from a coisometry: weighted square change at most a constant times (1+size)E2/3(1+\mathrm{size})\,E^{2/3}, EE the cost

Small energy cost bounds the change of the cutoff matrix.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A linear filter processes the vectors one at a time, updating a coefficient matrix at each step; a cutoff applied to the state and pulled back to the coefficients gives a cutoff matrix at each time. Lemma 4.1 asks how far the cutoff matrix can move over a stretch of the filter that costs little energy, the change being measured in a Hilbert-Schmidt norm weighted by the coefficients.

The estimate holds in two forms: for a run of filter steps from a coisometry, a matrix RR with RRT=IRR^{T}=I, and for two coisometries joined by a run of moves, which are updates of a state matrix, the identities tying the two ends together being assumed.

Filter Steps and Cutoff Matrices

Fix finite index sets ι\iota, for the coordinates of the state, and κ\kappa, for the coefficients. A filter step is a triple (C,b,j)(C,b,j) of a real ι×ι\iota\times\iota matrix CC, a vector b∈ℝιb\in\mathbb{R}^{\iota} and a column j∈κj\in\kappa, acting on real ι×κ\iota\times\kappa matrices, with eje_j the jjth standard basis vector of ℝκ\mathbb{R}^{\kappa}, by R↦CR+bejT.R\longmapsto CR+b\,e_j^{T}.(1)✦ A filter step (C,b,j)(C,b,j) is good when CC is invertible and CCT+bbT=ICC^{T}+bb^{T}=I.✦ The run π(R)\pi(R) of a list π\pi of filter steps on a real ι×κ\iota\times\kappa matrix RR is the matrix obtained from RR by applying the steps of π\pi by (1), first to last.✦ A list π\pi of filter steps is fresh for a real ι×κ\iota\times\kappa matrix RR when, for each step (C,b,j)(C,b,j) of π\pi, the column jj of RR is zero.✦

For weights q∈ℝκq\in\mathbb{R}^{\kappa} on the columns, the state matrix of a real ι×κ\iota\times\kappa matrix RR is the ι×ι\iota\times\iota matrix Lq(R)=Rdiag(q)RT.L_q(R)=R\,\mathrm{diag}(q)\,R^{T}.(2)✦

The trapezoid cutoff is the continuous piecewise linear function φ\varphi on ℝ\mathbb{R} given by φ(x)={0,x≤1/2,2x−1,1/2<x<1,1,1≤x≤2,2−x/2,2<x<4,0,x≥4,\varphi(x)= \begin{cases} 0, & x\le 1/2,\\ 2x-1, & 1/2<x<1,\\ 1, & 1\le x\le 2,\\ 2-x/2, & 2<x<4,\\ 0, & x\ge 4, \end{cases}(3)✦ and applied to symmetric matrices by the functional calculus.

The lift of a real ι×ι\iota\times\iota matrix AA along a real ι×κ\iota\times\kappa matrix RR is the κ×κ\kappa\times\kappa matrix RTARR^{T}AR.✦ The cutoff matrix of RR under the weights qq is the lift of φ(Lq(R))\varphi(L_q(R)) along RR, Fq(R)=RTφ(Lq(R))R.F_q(R)=R^{T}\varphi\bigl(L_q(R)\bigr)R.(4)

The weighted square of a real matrix DD with columns indexed by κ\kappa against a real κ×κ\kappa\times\kappa matrix WW is tr⁡(DWDT)\operatorname{tr}(DWD^{T}), which for positive semidefinite WW is the squared Hilbert-Schmidt norm ∥DW1/2∥HS2\|DW^{1/2}\|_{\mathrm{HS}}^{2}.✦

Moves and Their Energy Cost

A move on ι\iota is a pair (C,G)(C,G) of real ι×ι\iota\times\iota matrices, its contraction CC and its gain GG, acting on a state MM by M↦CMCT+GM\mapsto CMC^{T}+G.✦ A move (C,G)(C,G) is admissible when CCT≼ICC^{T}\preceq I in the Loewner order and GG is positive semidefinite.✦ The final state σ(M)\sigma(M) of a list σ\sigma of moves run from a real ι×ι\iota\times\iota matrix MM is the state reached by applying its moves in order.✦ The pair obtained by following a list σ\sigma of moves from a pair (Z,V)(Z,V) of real ι×ι\iota\times\iota matrices is the last pair reached by applying each move (C,G)(C,G) of σ\sigma in turn to both, by Z↦CZCTZ\mapsto CZC^{T} and V↦CVCT+GV\mapsto CVC^{T}+G.✦ The energy cost ℰ(M,σ)\mathcal{E}(M,\sigma) of a list σ=(π0,…,πn−1)\sigma=(\pi_0,\dots,\pi_{n-1}) of moves run from a real ι×ι\iota\times\iota matrix MM is the sum ∑k=0n−1cπk(Mk)\sum_{k=0}^{n-1}c_{\pi_k}(M_k) of the costs of the moves at the states M0=MM_0=M, Mk+1=πk(Mk)M_{k+1}=\pi_k(M_k) that the run passes through; the empty list costs 00.✦

For weights qq on κ\kappa, the move of a filter step (C,b,j)(C,b,j) is (C,qjbbT)(C,\,q_j\,bb^{T}); for a list π\pi of filter steps, πq\pi_q is the list of the moves of its steps, in order.✦

The exponent is a=3/2a=3/2✦, and the gain constant γ\gamma, the increment constant KK and the energy threshold e0e_0 are γ=a2a=32,K=230400(1+16γ1/a),e0=116γ.\gamma=a\,2^{a}=3\sqrt{2},\qquad K=230400\,\bigl(1+16\,\gamma^{1/a}\bigr),\qquad e_0=\frac{1}{16\gamma}.(5) The size weight is the function w(x)=min⁡(xa−1,x−1)w(x)=\min\bigl(x^{a-1},x^{-1}\bigr) on ℝ\mathbb{R}. The size of a symmetric ι×ι\iota\times\iota matrix LL is k(L)=tr⁡w(L)k(L)=\operatorname{tr}w(L).

The Claim

Theorem 1. (a) Let RR be an ι×κ\iota\times\kappa coisometry, RRT=IRR^{T}=I, let qq be positive weights on κ\kappa, and let π\pi be a list of good filter steps that is fresh for RR and whose steps write into pairwise distinct columns. Put R′=π(R)R'=\pi(R), L=Lq(R)L=L_q(R) and L′=Lq(R′)L'=L_q(R'). If ℰ(L,πq)≤E\mathcal{E}(L,\pi_q)\le E for a real E≤e0E\le e_0, then tr⁡((Fq(R′)−Fq(R))(I+diag(q))(Fq(R′)−Fq(R))T)≤K(1+k(L′))E1/a.\operatorname{tr}\Bigl(\bigl(F_q(R')-F_q(R)\bigr)\bigl(I+\mathrm{diag}(q)\bigr) \bigl(F_q(R')-F_q(R)\bigr)^{T}\Bigr)\le K\,\bigl(1+k(L')\bigr)\,E^{1/a}.(6)✦

(b) Let XX, YY, ZZ be positive definite ι×ι\iota\times\iota matrices and CC an invertible ι×ι\iota\times\iota matrix with CCT≼ICC^{T}\preceq I and Z=CYCTZ=CYC^{T}. Let SS and TT be ι×κ\iota\times\kappa coisometries with TST=CTS^{T}=C, and let QoldQ_{\mathrm{old}} and QnewQ_{\mathrm{new}} be positive semidefinite κ×κ\kappa\times\kappa matrices with SQoldST=YSQ_{\mathrm{old}}S^{T}=Y, TQoldTT=ZTQ_{\mathrm{old}}T^{T}=Z, TQoldST=CYTQ_{\mathrm{old}}S^{T}=CY, TQnewTT=X−ZTQ_{\mathrm{new}}T^{T}=X-Z and STφ(Y)SQnew=0S^{T}\varphi(Y)S\,Q_{\mathrm{new}}=0. Let σ\sigma be a list of admissible moves with σ(Y)=X\sigma(Y)=X, such that following σ\sigma from (Y,0)(Y,0) ends at a pair whose first matrix is ZZ, and with ℰ(Y,σ)≤E\mathcal{E}(Y,\sigma)\le E for a real E≤e0E\le e_0. Then, with D=TTφ(X)T−STφ(Y)SD=T^{T}\varphi(X)T-S^{T}\varphi(Y)S, tr⁡(D(I+Qold+Qnew)DT)≤K(1+k(X))E1/a.\operatorname{tr}\bigl(D\,(I+Q_{\mathrm{old}}+Q_{\mathrm{new}})\,D^{T}\bigr) \le K\,\bigl(1+k(X)\bigr)\,E^{1/a}.(7)✦

In the paper, the result reads: there are absolute constants e0>0e_0>0 and KK such that, for every recursion of its Proposition 2.2, every positive definite diagonal QQ, every dyadic θ\theta and all 0≤s≤t≤n0\le s\le t\le n, if E=Eθ(s,t)≤e0E=E_\theta(s,t)\le e_0 then ∥(Ft−Fs)(I+Q/θ)1/2∥HS2≤K(1+kt)E1/a\|(F_t-F_s)(I+Q/\theta)^{1/2}\|_{\mathrm{HS}}^{2}\le K(1+k_t)E^{1/a}, where Fq(R)F_q(R), Fq(R′)F_q(R'), diag(q)\mathrm{diag}(q), ℰ(L,πq)\mathcal{E}(L,\pi_q) and k(L′)k(L') stand for its FsF_s, FtF_t, Q/θQ/\theta, Eθ(s,t)E_\theta(s,t) and ktk_t.

What Is Checked

Both parts are stated over filter steps with their goodness, runs and freshness, the state matrix, the trapezoid cutoff, the lift and the weighted square, over moves with their admissibility, final states, following and energy cost, the move of a filter step, the size weight, and the exponent aa with the constants γ\gamma and KK.