Introduction
Transformers can learn from examples in their input at test time without updating their parameters, a capability known as in-context learning [7 , 13 ] . Studies of in-context linear regression have shown that transformers can implement familiar numerical algorithms, including gradient descent, preconditioned gradient descent, and Newton-like methods [3 , 29 , 1 , 12 ] . We ask:
Can studying learned transformer computations lead to new, general-purpose numerical algorithms that work independently of the transformer and beyond its training distribution?
We answer affirmatively by uncovering a new preconditioning primitive in a trained transformer’s computations and developing it into a standalone numerical algorithm.
The resulting algorithm: RAPID. Preconditioning is often crucial for efficiently solving symmetric positive definite (SPD) systems A x = b Ax = b A x = b . Conjugate gradient (CG) avoids direct factorization, but its convergence depends strongly on the spectrum of A A A [14 , 24 ] . Preconditioners improve convergence by transforming the system into an equivalent, better-conditioned one [5 , 31 ] . Classical approaches often construct approximate factorizations, inverses, or surrogate operators [22 , 6 ] .
We introduce RAPID (Randomized Anytime Preconditioning by Iterative Dynamics), which improves global conditioning through simple local corrections. Its key idea is to repeatedly randomize the coordinate system, exposing different matrix interactions that can be corrected locally. Specifically, RAPID alternates two steps. First, random orthogonal mixing redistributes matrix interactions without changing the spectrum. Second, each row selects its smallest off-diagonal entry and applies a sparse correction that acts to weaken the selected coupling. Repeating these steps allows local corrections to progressively improve global conditioning without explicitly computing eigenvectors or matrix inverses.
RAPID accumulates these transformations into a preconditioning factor P t P_t P t , yielding A t = P t A P t T A_t = P_t A P_t^{\mathsf{T}} A t = P t A P t T . Each iteration produces a valid preconditioner, making RAPID an anytime algorithm. Fast structured mixing and sparse corrections enable efficient, highly parallel dense implementations. The underlying update is derived from the trained transformer’s internal computation, as described next.
Algorithm discovery. We train a softmax-attention transformer on in-context linear systems X w = y Xw = y X w = y , where X X X need not be SPD. Layerwise orthogonal symmetry interventions [20 ] allow us to trace the evolution of the Gram matrix G ℓ = X ℓ X ℓ T G_\ell= X_\ell X_\ell^{\mathsf{T}} G ℓ = X ℓ X ℓ T during prediction. We observe that its conditioning improves and identify a simple learned congruence update responsible for this effect. Crucially, this update depends only on G ℓ G_\ell G ℓ , allowing RAPID to operate directly on arbitrary SPD matrices without the cost of forming a Gram matrix.
The connection to RAPID follows naturally: the symmetry intervention introduces random rotations, while learned attention applies local corrections that tend to weaken strong matrix interactions. The residual update applies the same row transformation to examples and labels, inducing the congruence update. To obtain an efficient algorithm, RAPID takes the low-temperature limit of softmax to select sparse off-diagonal row-min corrections and replaces dense rotations with fast structured mixing [33 ] . The resulting algorithm requires no learned components.
Results and guarantees. We evaluate RAPID on four synthetic spectral families and 31 SuiteSparse SPD matrices, well beyond the transformer’s training distribution. RAPID substantially improves conditioning across all four families and, remarkably, on every SuiteSparse matrix at every tested step count. In contrast, randomized Nyström preconditioning is more sensitive to spectral structure. These improvements also translate into substantially fewer conjugate gradient (CG) iterations to reach a fixed accuracy. Progressive gains with additional RAPID steps illustrate its anytime nature.
Theoretically, we prove that an idealized version of RAPID, using Haar mixing and block-restricted row-min corrections, reaches any fixed target condition number in O ( d log d log κ ( A ) ) O(d \log d \log\kappa(A)) O ( d log d log κ ( A )) expected iterations. This holds for any SPD matrix A A A , regardless of its eigenvalue distribution. At this iteration scale, RAPID’s per-step cost of O ( d 2 log d ) O(d^2 \log d) O ( d 2 log d ) corresponds to near-cubic setup complexity, comparable to classical dense factorization. Unlike direct factorization, however, RAPID can stop early to balance setup cost against preconditioner quality. Although the iteration-complexity guarantee remains limited to an idealized variant, experiments show that its assumptions do not accelerate conditioning on tested spectra, suggesting they facilitate the proof rather than the algorithm’s effectiveness.
Contributions. We make three core contributions:
We discover a new preconditioning primitive in a trained transformer: a solution-preserving update to the linear system X w = y Xw = y X w = y that improves the conditioning of the Gram matrix X X T XX^{\mathsf{T}} X X T .
We develop this mechanism into RAPID, a standalone anytime preconditioner for arbitrary SPD matrices, requiring no learned components and using efficient, parallelizable iterations.
We establish theoretical and empirical evidence of RAPID’s effectiveness: an idealized variant provably reaches any fixed target condition number for arbitrary SPD matrices, while dense experiments demonstrate broad conditioning gains and substantially faster CG convergence.
Related Work
Transformers as algorithm learners. For linear prediction, trained transformers approximate least-squares predictors and learn familiar methods resembling gradient descent, ridge regression, and second-order methods [13 , 3 , 29 , 1 , 34 , 12 ] . In other settings, trained transformers also learn temporal-difference updates and graph-connectivity algorithms [30 , 32 ] . Beyond known methods, transformers have revealed novel optimization strategies for noisy linear regression [28 ] and iterative methods for masked matrix completion [19 ] . We extend this direction by extracting a new conditioning primitive and developing a standalone preconditioner for arbitrary SPD matrices, with theoretical guarantees, broad conditioning gains and improved CG convergence.
Preconditioning for SPD systems. Conjugate gradient (CG) solves SPD systems A x = b Ax=b A x = b without direct factorization, but its convergence depends strongly on the spectrum of A A A [14 , 24 ] . Classical preconditioners seek to improve this spectrum through incomplete Cholesky factorizations [22 ] , sparse approximate inverses [6 ] , or algebraic multigrid hierarchies [26 ] . Rather than constructing such approximations, RAPID iteratively improves conditioning through randomized mixing and sparse local corrections, accumulating a factor P t P_t P t with A t = P t A P t T A_t=P_tAP_t^{\mathsf{T}} A t = P t A P t T . Each iteration yields a valid SPD preconditioned system, allowing RAPID to stop at any point without requiring a complete factorization or inverse approximation.
Randomized preconditioning and structured transforms. Randomized preconditioners often construct approximations of the original problem. For least squares, sketching methods use subsampled orthogonal transforms or Gaussian projections to build smaller systems for factorization [4 , 23 ] ; for SPD systems, randomized Nyström methods construct low-rank approximations for preconditioned CG [11 ] . More broadly, fast randomized Hadamard transforms provide efficient alternatives to dense random projections [2 , 17 , 33 ] . RAPID uses fast randomized Hadamard mixing, but applies it repeatedly to expose matrix interactions for sparse local corrections rather than to construct a one-shot approximation.
Learned preconditioners and neural solvers. Recent work has used neural networks to accelerate iterative linear solvers by learning algebraic multigrid components, approximate factorizations, or preconditioners for conjugate-gradient methods [21 , 18 , 25 ] . These approaches evaluate a trained network to construct preconditioners for new systems. In contrast, we use the transformer only to discover a numerical algorithm. Once extracted, RAPID operates directly on arbitrary SPD matrices through explicit randomized updates, without learned components or neural inference at solve time.
Symmetry and equivariance in neural networks. When task symmetries are known, equivariant architectures provide a way to encode them as inductive biases, restricting the learned function class and improving generalization [8 , 16 ] (Fizin et al. 2021). Layerwise symmetry interventions instead use random, task-preserving coordinate changes to reveal learned transformer computations [20 ] . This technique was originally developed for in-context classification using permutation symmetries; we adapt their identification method to the orthogonal symmetries of linear systems, revealing the conditioning primitive underlying RAPID.
Algorithm discovery through in-context learning
In this section, we use a transformer trained on in-context linear systems to discover a numerical preconditioning primitive. We train an attention-only model to predict from examples satisfying X w = y Xw=y X w = y , using a layerwise symmetry intervention to make its learned computation identifiable. We extract a two-scalar update that preserves the linear system and evolves the Gram matrix X X T X X^{\mathsf{T}} X X T by congruence, substantially improving its conditioning. This primitive motivates RAPID, developed in Section 4 as a standalone SPD preconditioner with no learned components.
Transformer setup and symmetry intervention
In-context linear systems. Following Garg et al. [ [13 ] , we train transformers on synthetic linear systems X w = y Xw=y X w = y , where X ∈ R d × d X \in\mathbb{R}^{d \times d} X ∈ R d × d and w ∈ R d w \in\mathbb{R}^{d} w ∈ R d , d = 15 d=15 d = 15 . Each task samples X X X and a query x q ∈ R d x_q \in\mathbb{R}^{d} x q ∈ R d with independent standard Gaussian entries, and w ∼ N ( 0 , I d / d ) w \sim\mathcal{N}(0,I_d/d) w ∼ N ( 0 , I d / d ) , then sets y = X w y=Xw y = X w . The model observes ( X , y , x q ) (X,y,x_q) ( X , y , x q ) , but not w w w , and is trained to predict x q T w x_q^{\mathsf{T}}w x q T w . Since w w w is resampled for every task, prediction requires solving a new instance rather than memorizing a fixed solution.
Transformer architecture. We encode each task as
Z 0 = [ X y x q T 0 ] , Z_0 =
\begin{bmatrix}
X & y \\
x_q^{\mathsf{T}} & 0
\end{bmatrix}, Z 0 = [ X x q T y 0 ] ,
with the query prediction read from the bottom-right entry of Z L Z_L Z L (with a negative sign) after processing through L L L transformer layers. The attention-only transformer applies
Z ℓ + 1 = Z ℓ + Attn ℓ ( Z ℓ ) , Attn ℓ ( Z ) = σ ( Z W Q , ℓ W K , ℓ T Z T + M ) Z W V , ℓ W P , ℓ , (1) Z_{\ell+1}=Z_\ell+\operatorname{Attn}_{\ell}(Z_\ell),\qquad
\operatorname{Attn}_{\ell}(Z)=\sigma\left(ZW_{Q,\ell}W_{K,\ell}^{\mathsf{T}}Z^{\mathsf{T}}+M\right)ZW_{V,\ell}W_{P,\ell}, \tag*{(1)} Z ℓ + 1 = Z ℓ + Attn ℓ ( Z ℓ ) , Attn ℓ ( Z ) = σ ( Z W Q , ℓ W K , ℓ T Z T + M ) Z W V , ℓ W P , ℓ , (1)
where σ \sigma σ is row-wise softmax and M M M prevents attention to the query token as a key. The model is trained by squared prediction loss, without any supervision on conditioning. Training details are given in Appendix § 9 .§ 1 .
Layerwise symmetry intervention. The linear system has an orthogonal symmetry: for any U , V ∈ O ( d ) U,V \in O(d) U , V ∈ O ( d ) , the group of d × d d \times d d × d orthogonal matrices, the transformation
X ~ = U X V , y ~ = U y , x ~ q = V T x q \widetilde{X}=UXV,\qquad\widetilde{y}=Uy,\qquad\widetilde{x}_q=V^{\mathsf{T}}x_q X = U X V , y = U y , x q = V T x q
preserves the problem, since X ~ ( V T w ) = y ~ \widetilde{X}(V^{\mathsf{T}}w)=\widetilde{y} X ( V T w ) = y and x ~ q T ( V T w ) = x q T w \widetilde{x}_q^{\mathsf{T}}(V^{\mathsf{T}}w)=x_q^{\mathsf{T}}w x q T ( V T w ) = x q T w . Thus the same prediction problem can be represented in different example and feature coordinates.
To make the learned computation identifiable, we adapt the layerwise symmetry intervention of Lutz et al. [ [20 ] . At each layer, we sample independent U ℓ , V ℓ ∼ Haar ( O ( d ) ) U_\ell,V_\ell\sim\operatorname{Haar}(O(d)) U ℓ , V ℓ ∼ Haar ( O ( d )) , extend them to fix the query and label coordinates as
U ‾ ℓ = [ U ℓ 0 0 1 ] , V ‾ ℓ = [ V ℓ 0 0 1 ] . \overline{U}_\ell=\begin{bmatrix} U_\ell& 0 \\ 0 & 1 \end{bmatrix},\qquad\overline{V}_\ell=\begin{bmatrix} V_\ell& 0 \\ 0 & 1 \end{bmatrix}. U ℓ = [ U ℓ 0 0 1 ] , V ℓ = [ V ℓ 0 0 1 ] .
and evaluate attention in the transformed coordinates before mapping the residual update back:
Z ℓ + 1 = Z ℓ + U ‾ ℓ T Attn ℓ ( U ‾ ℓ Z ℓ V ‾ ℓ ) V ‾ ℓ T . (2) Z_{\ell+1}=Z_\ell+\overline{U}_\ell^{\mathsf{T}}\operatorname{Attn}_\ell(\overline{U}_\ell Z_\ell\overline{V}_\ell)\overline{V}_\ell^{\mathsf{T}}. \tag*{(2)} Z ℓ + 1 = Z ℓ + U ℓ T Attn ℓ ( U ℓ Z ℓ V ℓ ) V ℓ T . (2)
This is the transformer architecture we train and analyze throughout this section. The intervention discourages reliance on arbitrary coordinate choices, making the learned computation easier to identify, without imposing any conditioning objective or preconditioning algorithm.
Extracting a conditioning primitive
The transformer achieves increasingly accurate predictions with depth, following an error profile distinct from GD and CG at matched iteration budgets (Appendix § 9 .§ 2 ). This suggests that the model learns a distinct, nontrivial procedure rather than simply unrolling either classical solver. We therefore examine its trained layers to identify the underlying computation.
Identifying the learned update. The attention layers depend on the weights only through the products W Q K , ℓ = W Q , ℓ W K , ℓ T W_{QK,\ell}=W_{Q,\ell}W_{K,\ell}^{\mathsf{T}} W Q K , ℓ = W Q , ℓ W K , ℓ T and W V P , ℓ = W V , ℓ W P , ℓ W_{VP,\ell}=W_{V,\ell}W_{P,\ell} W V P , ℓ = W V , ℓ W P , ℓ . These products exhibit a simple dominant structure: W Q K , ℓ W_{QK,\ell} W Q K , ℓ is concentrated on the feature-feature identity block, while W V P , ℓ W_{VP,\ell} W V P , ℓ is approximately a scalar identity (Figure 1 , left). We therefore approximate each layer by
Figure 1. Extracting a conditioning primitive. Left: Representative learned weight products W Q K , ℓ W_{QK,\ell} W Q K , ℓ and W V P , ℓ W_{VP,\ell} W V P , ℓ , showing the dominant two-scalar structure in Eq. (3) . Right: Median condition number of the context Gram matrix across layers of the trained transformer, decreasing from roughly 3,000 to below 10 at the best layer.
W Q K , ℓ ≈ γ ℓ [ I d 0 0 0 ] , W V P , ℓ ≈ α ℓ I d + 1 , (3) W_{QK,\ell}\approx\gamma_\ell\begin{bmatrix} I_d & 0 \\ 0 & 0 \end{bmatrix},\qquad W_{VP,\ell}\approx\alpha_\ell I_{d+1}, \tag*{(3)} W Q K , ℓ ≈ γ ℓ [ I d 0 0 0 ] , W V P , ℓ ≈ α ℓ I d + 1 , (3)
where γ ℓ \gamma_\ell γ ℓ and α ℓ \alpha_\ell α ℓ are the mean diagonal entries of the respective identity blocks.
Substituting these approximated weight products into the intervened transformer gives an explicit iteration. Writing X ℓ , y ℓ X_\ell,y_\ell X ℓ , y ℓ for the context state and G ℓ = X ℓ X ℓ T G_\ell=X_\ell X_\ell^{\mathsf{T}} G ℓ = X ℓ X ℓ T for its Gram matrix, each layer computes
K ℓ = σ ( γ ℓ U ℓ G ℓ U ℓ T ) , C ℓ = I + α ℓ U ℓ T K ℓ U ℓ , (4) K_\ell=\sigma\left(\gamma_\ell U_\ell G_\ell U_\ell^{\mathsf{T}}\right),\qquad C_\ell=I+\alpha_\ell U_\ell^{\mathsf{T}}K_\ell U_\ell, \tag*{(4)} K ℓ = σ ( γ ℓ U ℓ G ℓ U ℓ T ) , C ℓ = I + α ℓ U ℓ T K ℓ U ℓ , (4)
and updates examples and labels by the same row transformation:
X ℓ + 1 = C ℓ X ℓ , y ℓ + 1 = C ℓ y ℓ . (5) X_{\ell+1}=C_\ell X_\ell,\qquad y_{\ell+1}=C_\ell y_\ell. \tag*{(5)} X ℓ + 1 = C ℓ X ℓ , y ℓ + 1 = C ℓ y ℓ . (5)
To assess the approximation, we replace the learned weight products in every layer by their two-scalar forms in Eq. (3) and compare predictions against the trained transformer on the same held-out tasks, using identical random rotations. The predictions agree closely (R 2 > 0.98 R^2>0.98 R 2 > 0.98 ), with a test MSE change of only 6.4 × 10 − 3 6.4\times10^{-3} 6.4 × 1 0 − 3 (Appendix § 9 .§ 3 ). This confirms that the two-scalar update faithfully reproduces the trained transformer’s predictive behavior.
A solution-preserving congruence update. The key property of Eq. (5) is that it preserves the linear-system relation: if y ℓ = X ℓ w y_\ell=X_\ell w y ℓ = X ℓ w , then y ℓ + 1 = C ℓ X ℓ w = X ℓ + 1 w y_{\ell+1}=C_\ell X_\ell w=X_{\ell+1}w y ℓ + 1 = C ℓ X ℓ w = X ℓ + 1 w . When C ℓ C_\ell C ℓ is invertible, the transformed system has the same solution. Moreover, the Gram matrix evolves by congruence:
G ℓ + 1 = C ℓ G ℓ C ℓ T . (6) G_{\ell+1}=C_\ell G_\ell C_\ell^{\mathsf{T}}. \tag*{(6)} G ℓ + 1 = C ℓ G ℓ C ℓ T . (6)
Crucially, C ℓ C_\ell C ℓ depends only on G ℓ G_\ell G ℓ and the random rotation U ℓ U_\ell U ℓ , not on the labels or query. Thus the extracted iteration defines a self-contained conditioning mechanism on SPD matrices, independent of the original prediction task.
Empirical conditioning and the learned sign rule. The trained dynamics substantially improve conditioning: the median condition number of G ℓ G_{\ell} G ℓ decreases from roughly 3,000 to below 10 at the best layer (Figure 1 , right). The two-scalar approximation exhibits similar behavior.
Which layers improve conditioning? We find that layers satisfying
sign ( α ℓ ) ≠ sign ( γ ℓ ) , ∣ α ℓ ∣ < 1 (7) \operatorname{sign}(\alpha_{\ell}) \ne\operatorname{sign}(\gamma_{\ell}), \qquad|\alpha_{\ell}| < 1 \tag*{(7)} sign ( α ℓ ) = sign ( γ ℓ ) , ∣ α ℓ ∣ < 1 (7)
typically reduce the condition number. Across runs, 80% of layers satisfy this rule, and in the median such layer, 95.5% of test instances experience a condition-number decrease (Appendix § 9 .§ 4 ).
Together, these results identify a Gram-dependent conditioning primitive within the transformer’s learned prediction procedure. The symmetry intervention provides random coordinate mixing, while the learned attention determines the row corrections. The next section develops this primitive into RAPID by replacing dense rotations and soft attention with efficient structured mixing and sparse updates, yielding a standalone preconditioner without learned components at solve time.
RAPID: Randomized Anytime Preconditioning by Iterative Dynamics
Section 3 identified a Gram-dependent congruence update learned by a transformer trained only for prediction. We now develop this primitive into RAPID, a standalone preconditioner for explicit SPD systems A x = b Ax=b A x = b . RAPID retains random coordinate mixing and row-wise corrections, but replaces dense rotations and soft attention with efficient structured transforms and sparse updates. It requires no trained model or learned parameters at solve time.
Constructing the RAPID update
Randomized mixing. Starting from A 0 = A A_0=A A 0 = A , RAPID repeatedly applies an orthogonal change of coordinates,
A ~ t = Q t A t Q t T . \widetilde{A}_t = Q_t A_t Q_t^{\mathsf{T}}. A t = Q t A t Q t T .
This preserves the eigenvalues, but exposes different off-diagonal interactions that can be corrected locally. To obtain this mixing efficiently, RAPID replaces dense random rotations with products of randomized Walsh–Hadamard transforms:
Q t = H S t , k ⋯ H S t , 2 H S t , 1 , (8) Q_t = H S_{t,k} \cdots H S_{t,2} H S_{t,1}, \tag*{(8)} Q t = H S t , k ⋯ H S t , 2 H S t , 1 , (8)
where H H H is the normalized Walsh–Hadamard matrix and S t , j S_{t,j} S t , j are independent diagonal matrices with random ± 1 \pm1 ± 1 entries. Such transforms spread information across coordinates similarly to dense random rotations while preserving orthogonality [2 , 17 , 33 ] . For fixed k k k , they cost O ( d log d ) O(d \log d) O ( d log d ) per vector, rather than O ( d 2 ) O(d^2) O ( d 2 ) for a dense rotation.
From learned attention to sparse row corrections. The learned conditioning rule (7) identifies opposite signs for α ℓ \alpha_{\ell} α ℓ and γ ℓ \gamma_{\ell} γ ℓ , with ∣ α ℓ ∣ < 1 |\alpha_{\ell}| < 1 ∣ α ℓ ∣ < 1 . RAPID fixes the convention of positive residual steps α ℓ > 0 \alpha_{\ell} > 0 α ℓ > 0 , corresponding to negative attention scales γ ℓ < 0 \gamma_{\ell} < 0 γ ℓ < 0 in the learned model; the opposite convention analogously motivates negative steps with row-maximum selection.
With a negative attention scale, softmax favors smaller entries of the mixed Gram matrix. For computational efficiency, RAPID replaces dense soft attention with selection of the smallest off-diagonal entry in each row:
τ i ( B ) : = arg min j ≠ i B i j , R ( B ) i j : = 1 { j = τ i ( B ) } . (9) \tau_i(B) := \underset{j \ne i}{\operatorname{arg\,min}}\, B_{ij}, \qquad\mathcal{R}(B)_{ij} := \mathbf{1}\{j=\tau_i(B)\}. \tag*{(9)} τ i ( B ) := j = i arg min B ij , R ( B ) ij := 1 { j = τ i ( B )} . (9)
We exclude the diagonal to target interactions between different rows rather than simply rescaling individual rows. The resulting one-sparse-per-row operator reduces the cost of the congruence update from O ( d 3 ) O(d^3) O ( d 3 ) to O ( d 2 ) O(d^2) O ( d 2 ) . This sparsification is a design choice motivated by the learned attention.
Writing R t = R ( A ~ t ) R_t=\mathcal{R}(\widetilde{A}_t) R t = R ( A t ) , RAPID applies
C t = I + α t R t , A t + 1 = C t A ~ t C t T . (10) C_t=I+\alpha_tR_t,\qquad A_{t+1}=C_t\widetilde{A}_tC_t^{\mathsf{T}}. \tag*{(10)} C t = I + α t R t , A t + 1 = C t A t C t T . (10)
This retains the congruence structure of the learned iteration, now with an explicit sparse row operator.
Why does this improve conditioning? The intuition is clearest for a matrix with a single exceptional eigenvalue. Consider A ~ = I + ( λ − 1 ) v v T \widetilde{A}=I+(\lambda-1)vv^{\mathsf{T}} A = I + ( λ − 1 ) v v T , where λ > 0 \lambda>0 λ > 0 , λ ≠ 1 \lambda\ne1 λ = 1 , and ∥ v ∥ = 1 \lVert v\rVert=1 ∥ v ∥ = 1 , so all eigenvalues equal 1 except λ \lambda λ . Adding a small positive fraction α \alpha α of row j j j to row i i i , together with the corresponding column operation, changes the exceptional eigenvalue to first order by
λ ( α ) = λ + 2 α λ λ − 1 A ~ i j + O ( α 2 ) . (11) \lambda(\alpha)=\lambda+\frac{2\alpha\lambda}{\lambda-1}\widetilde{A}_{ij}+O(\alpha^2). \tag*{(11)} λ ( α ) = λ + λ − 1 2 α λ A ij + O ( α 2 ) . (11)
Thus, for sufficiently small α > 0 \alpha>0 α > 0 , a negative A ~ i j \widetilde{A}_{ij} A ij moves λ \lambda λ toward 1: decreasing it when λ > 1 \lambda>1 λ > 1 and increasing it when λ < 1 \lambda<1 λ < 1 . Random mixing can expose negative off-diagonal entries even when none are present initially, and row-minimum selection favors such entries when available. For general matrices, individual corrections need not improve conditioning; § 6 establishes a global guarantee for an idealized variant. The first-order calculation is detailed in Appendix § 11 .9.
Step-size selection. Each row of R t R_t R t selects one column, but multiple rows may select the same column. Let
m t = max j ∑ i ( R t ) i j m_t=\max_j\sum_i(R_t)_{ij} m t = j max i ∑ ( R t ) ij
denote the maximum column load. Since ∥ R t ∥ o p = m t \lVert R_t\rVert_{\mathrm{op}}=\sqrt{m_t} ∥ R t ∥ op = m t , we use
α t = s α m t d log d , (12) \alpha_t=\frac{s_\alpha}{\sqrt{m_td\log d}}, \tag*{(12)} α t = m t d log d s α , (12)
where s α > 0 s_\alpha>0 s α > 0 is a tunable scale. This keeps the overall update magnitude α t ∥ R t ∥ o p = s α / d log d \alpha_t\lVert R_t\rVert_{\mathrm{op}}=s_\alpha/\sqrt{d\log d} α t ∥ R t ∥ op = s α / d log d independent of the column load, controlling the effect of simultaneous row corrections. § 6 provides a complementary motivation based on the expected improvement in conditioning.
RAPID as an anytime preconditioner
Accumulating the preconditioner. RAPID maintains a factor P t P_t P t satisfying
P 0 = I d , P t + 1 = C t Q t P t , A t = P t A P t T . (13) P_0=I_d,\qquad P_{t+1}=C_tQ_tP_t,\qquad A_t=P_tAP_t^{\mathsf{T}}. \tag*{(13)} P 0 = I d , P t + 1 = C t Q t P t , A t = P t A P t T . (13)
Thus the random basis changes are accumulated rather than reversed after each correction.
To ensure a valid preconditioner at every iteration, we choose s α s_\alpha s α so that α t < 1 \alpha_t<1 α t < 1 . Indeed, R t R_t R t is row-stochastic, so its eigenvalues have magnitude at most 1. Hence C t = I + α t R t C_t=I+\alpha_tR_t C t = I + α t R t is invertible whenever 0 < α t < 1 0<\alpha_t<1 0 < α t < 1 . Each congruence update therefore preserves positive definiteness.
After any T T T iterations, RAPID produces the equivalent SPD system
A T z = P T b , x = P T T z , A_Tz=P_Tb,\qquad x=P_T^{\mathsf{T}}z, A T z = P T b , x = P T T z ,
which can be solved using conjugate gradients. Since every iteration yields a valid factor P t P_t P t , RAPID is an anytime preconditioner: the iteration budget trades setup cost against the conditioning achieved. The factor can also be reused for multiple right-hand sides.
Complete algorithm. Algorithm 1 summarizes the practical RAPID iteration, using structured orthogonal mixing and row-minimum selection.
Computational cost and theoretical scope. Row-minimum selection and the sparse congruence update each cost O ( d 2 ) O(d^2) O ( d 2 ) . Applying a fixed number of Walsh–Hadamard transforms to a dense matrix costs O ( d 2 log d ) O(d^2\log d) O ( d 2 log d ) , which dominates the per-iteration complexity. These operations are highly parallelizable and require no matrix factorization. For dimensions that are not powers of two, the implementation uses padding (Appendix § 10 ).
§ 5 evaluates the practical algorithm, while § 6 analyzes a related variant using Haar mixing and block-restricted row selection.
Algorithm 1 RAPID: Practical preconditioning algorithm
1: Input: $A \succ 0$, iterations $T$, mixer depth $k$, scale $0 < s_\alpha < \sqrt{d\log d}$
2: $A_0 \gets A,\quad P_0 \gets I_d$
3: for $t = 0,\ldots,T-1$ do
4: Draw $Q_t$ via (8); $\widetilde{A}_t \gets Q_t A_t Q_t^{\mathsf{T}}$ ▷ random mixing
5: $R_t \gets \mathcal{R}(\widetilde{A}_t)$ defined as in (9) ▷ row selection
6: $m_t \gets \max_j \sum_i (R_t)_{ij}$; $\alpha_t \gets s_\alpha/\sqrt{m_t d\log d}$ ▷ compute step-size
7: $C_t \gets I+\alpha_t R_t$ ▷ sparse correction
8: $A_{t+1} \gets C_t\widetilde{A}_tC_t^{\mathsf{T}}$; $P_{t+1} \gets C_tQ_tP_t$ ▷ update operator
9: end for
10: return $P_T,A_T$ ▷ verifies $A_T=P_TAP_T^{\mathsf{T}}$
Experimental Evaluation
In this section, we show that RAPID improves conditioning across SPD matrices well beyond the transformer’s training distribution, and that these improvements translate into faster CG convergence. We use the practical algorithm of § 4 , with Walsh–Hadamard mixing and global row-minimum selection. No trained model is used in these experiments.
Experimental protocol. We generate synthetic matrices A = U Λ U T A = U\Lambda U^{\mathsf{T}} A = U Λ U T , with Haar-random U U U , dimension d = 1024 d = 1024 d = 1024 , and condition number κ = 10 4 \kappa= 10^4 κ = 1 0 4 . We consider four distinct spectral distributions: Chebyshev, linear, logarithmic, and power-law, with 100 independent matrices per family. We also evaluate 31 SPD matrices from SuiteSparse [15 ] , selected independently of RAPID’s performance by dimension (100 ≤ d ≤ 6000 100 \le d \le6000 100 ≤ d ≤ 6000 ) and post-Jacobi condition number (10 3 10^3 1 0 3 –10 6 10^6 1 0 6 ). All matrices are treated as dense operators. Details appear in Appendix § 10 .
After Jacobi scaling, we compare RAPID (s α = 10 s_\alpha= 10 s α = 10 ) with randomized Nyström preconditioning [11 ] , which uses a one-shot low-rank approximation rather than RAPID’s iterative congruence updates (sketch sizes 1%–50% of d d d ). We report condition numbers relative to the Jacobi-scaled matrix A 0 A_0 A 0 and CG iterations relative to Jacobi-preconditioned CG. All methods use the same right-hand side and stopping criterion ∥ A 0 x ^ − b 0 ∥ 2 / ∥ b 0 ∥ 2 ≤ 0.002 \lVert A_0\hat{x}-b_0\rVert_2/\lVert b_0\rVert_2 \le0.002 ∥ A 0 x ^ − b 0 ∥ 2 / ∥ b 0 ∥ 2 ≤ 0.002 , evaluated in the original Jacobi-scaled coordinates, ensuring a common accuracy target.
Broad improvements in conditioning. Figure 2 (top) shows that RAPID substantially improves conditioning across all four spectral families. In contrast, Nyström is strongly dependent on the eigenvalue distribution: it is particularly effective on the logarithmic spectrum, but achieves much smaller improvements on Chebyshev and linear spectra, even with large sketches. Remarkably, at every tested step count T T T , RAPID reduces the condition number of all 31 SuiteSparse matrices, not just the average. These results demonstrate that RAPID generalizes well beyond the Gaussian Gram matrices used during transformer training.
Figure 2. Conditioning and CG convergence across synthetic and real-world SPD matrices. Top: condition number relative to the Jacobi-scaled system. Bottom: CG iterations required to reach the common residual tolerance, relative to Jacobi-preconditioned CG. Lower is better in both rows. Blue curves show RAPID means and shaded bands the minimum and maximum; dashed lines show mean Nyström results at different sketch sizes. Each synthetic panel contains 100 independent matrices; SuiteSparse contains 31. The corresponding absolute values are reported in Appendix § 10 .
Fewer CG iterations at fixed accuracy. Figure 2 (bottom) shows that RAPID’s conditioning gains also translate into substantially fewer CG iterations to reach the same accuracy, across all four synthetic families and, on average, across SuiteSparse matrices. This is significant because CG convergence depends on the full spectrum, not just the condition number. Thus, RAPID not only improves conditioning broadly, but also makes these systems easier to solve iteratively. All solvers reached the target accuracy, except for Nyström preconditioning with a 1% sketch which failed on a single SuiteSparse instance.
Practical considerations. The progressive improvements with increasing T T T illustrate RAPID’s anytime nature, allowing a trade-off between setup cost and preconditioner quality. A RAPID step costs O ( d 2 log d ) O(d^2 \log d) O ( d 2 log d ) , matching a dense CG iteration up to logarithmic factors. In practice, RAPID can be more expensive per step, as its operations do not benefit from the same highly optimized GPU implementations available for CG’s matrix–vector products. The setup cost may nevertheless pay off through fewer CG iterations, especially when amortized across multiple right-hand sides. A definitive runtime comparison requires optimized implementations of both methods and is left for future work.
Analyzing the Extracted Preconditioner
We analyze an idealized version of RAPID using two simplifications relative to Algorithm 1: (i) Haar-random mixing, which enables an exact calculation of a certain expected ‘row-min drift’ term, and (ii) block-restricted row selection, which bounds the maximum column load of R t R_t R t . These assumptions enable our proof, but are not required by the practical algorithm. We first establish the conditioning guarantee, then examine the empirical effect of both simplifications.
Conditioning guarantee under simplifying assumptions
Our proof tracks a smooth approximation to the log-condition number and shows that it decreases in expectation until the matrix becomes well-conditioned. The key is to balance two effects: the favorable first-order drift induced by row-min selection, and a second-order error that depends on how many rows select the same column. Haar mixing allows us to characterize the drift, while blocking controls the error.
Specifically, we take Q t ∼ Haar ( O ( d ) ) Q_t \sim\operatorname{Haar}(O(d)) Q t ∼ Haar ( O ( d )) and replace the global row-min operator R \mathcal{R} R with a block-restricted version. Partition the indices into blocks of size at most b b b , and let B ( i ) B(i) B ( i ) denote the block containing i i i . Define
r i b ( A ) : = arg min j ∈ B ( i ) ∖ { i } A i j , R b ( A ) i j : = 1 { j = r i b ( A ) } . (14) r_i^b(A) := \underset{j \in B(i) \setminus\{i\}}{\arg\min}\ A_{ij}, \qquad\mathcal{R}_b(A)_{ij} := \mathbb{1}\{j = r_i^b(A)\}. \tag*{(14)} r i b ( A ) := j ∈ B ( i ) ∖ { i } arg min A ij , R b ( A ) ij := 1 { j = r i b ( A )} . (14)
Here 3 ≤ b ≤ d 3 \le b \le d 3 ≤ b ≤ d is the block size; setting b = d b=d b = d recovers the original global row-min operator R \mathcal{R} R . By restricting selection to each row’s block, we ensure that no column is selected more than b − 1 b-1 b − 1 times. We now establish the two bounds and combine them to obtain the conditioning guarantee. Full proofs appear in Appendix C.
Potential Function & First-order analysis. To measure progress toward a well-conditioned matrix, we construct the following potential function:
Φ β ( A ) : = 1 β log tr ( A β ) d + 1 β log tr ( A − β ) d , \Phi_\beta(A) := \frac{1}{\beta} \log\frac{\operatorname{tr}(A^\beta)}{d} + \frac{1}{\beta} \log\frac{\operatorname{tr}(A^{-\beta})}{d}, Φ β ( A ) := β 1 log d tr ( A β ) + β 1 log d tr ( A − β ) ,
where β ≥ 1 \beta\ge1 β ≥ 1 . This scale and basis invariant potential essentially corresponds to the log of the ratio of a softmax and softmin of the spectrum (with temperature β \beta β ) and satisfies
0 ≤ Φ β ( A ) ≤ log κ ( A ) ≤ Φ β ( A ) + 2 log d β . 0 \le\Phi_\beta(A) \le\log\kappa(A) \le\Phi_\beta(A) + \frac{2 \log d}{\beta}. 0 ≤ Φ β ( A ) ≤ log κ ( A ) ≤ Φ β ( A ) + β 2 log d .
We will set β = Θ ( log ( d ) ) \beta= \Theta(\log(d)) β = Θ ( log ( d )) below, making the approximation error constant. The key lemma capturing the decay of this potential arises from a Taylor expansion, where the curvature term is controlled by submultiplicativity of Schatten p p p -norms.
Lemma 1. Let m t : = ∥ R t ∥ 1 = max j ∑ i ( R t ) i j m_t := \lVert R_t\rVert_1 = \max_j \sum_i (R_t)_{ij} m t := ∥ R t ∥ 1 = max j ∑ i ( R t ) ij be the maximal column load of the matrix R t R_t R t . If α m t ≤ 1 / 2 \alpha\sqrt{m_t} \le1/2 α m t ≤ 1/2 , then
Φ ( A t + 1 ) ≤ Φ ( A t ) + 2 α f ( R t , A ~ t ) + 12 α 2 β m t \Phi(A_{t+1}) \le\Phi(A_t) + 2\alpha f(R_t,\widetilde{A}_t) + 12\alpha^2\beta m_t Φ ( A t + 1 ) ≤ Φ ( A t ) + 2 α f ( R t , A t ) + 12 α 2 β m t where
f ( R t , A ~ t ) : = ( tr ( R t A ~ t β ) tr ( A ~ t β ) − tr ( R t A ~ t − β ) tr ( A ~ t − β ) ) . f(R_t,\widetilde{A}_t) := \left(\frac{\operatorname{tr}(R_t\widetilde{A}_t^\beta)}{\operatorname{tr}(\widetilde{A}_t^\beta)}-\frac{\operatorname{tr}(R_t\widetilde{A}_t^{-\beta})}{\operatorname{tr}(\widetilde{A}_t^{-\beta})}\right). f ( R t , A t ) := ( tr ( A t β ) tr ( R t A t β ) − tr ( A t − β ) tr ( R t A t − β ) ) .
Row-min drift. The key question is whether the first-order term f ( R t , A ~ t ) f(R_t,\widetilde{A}_t) f ( R t , A t ) is negative in expectation, so that it outweighs the second-order growth. Haar mixing allows us to characterize this term exactly.
Lemma 2. Suppose Q t ∼ Haar ( O ( d ) ) Q_t \sim\operatorname{Haar}(\mathrm{O}(d)) Q t ∼ Haar ( O ( d )) independently of the history, and that R t = R b ( A ~ t ) R_t = R_b(\widetilde{A}_t) R t = R b ( A t ) . Then
E [ f ( R t , A ~ t ) ∣ A t ] = − ν b , d d − 1 S β ( A t ) . (15) \mathbb{E}\left[f(R_t,\widetilde{A}_t)\mid A_t\right] = \frac{-\nu_{b,d}}{\sqrt{d-1}}S_\beta(A_t). \tag*{(15)} E [ f ( R t , A t ) ∣ A t ] = d − 1 − ν b , d S β ( A t ) . (15) where ν b , d ≥ log ( b ) \nu_{b,d} \ge\sqrt{\log(b)} ν b , d ≥ log ( b ) , and S β S_\beta S β depends on the spectral properties of A t A_t A t and d d d . In particular, if β ≥ log ( 8 d ) / log ( 8 / 7 ) \beta\ge\log(8d)/\log(8/7) β ≥ log ( 8 d ) / log ( 8/7 ) and κ ( A t ) ≥ 2 \kappa(A_t) \ge2 κ ( A t ) ≥ 2 , then S β ( A t ) ≥ 1 / 4 S_\beta(A_t) \ge1/4 S β ( A t ) ≥ 1/4 .
S β ( A t ) S_\beta(A_t) S β ( A t ) is a measure of the correlation of spectrum of A A A with its β \beta β th power. The lemma guarantees a negative first-order drift of magnitude α ⋅ Ω ( log ( b ) / d ) \alpha\cdot\Omega(\sqrt{\log(b)/d}) α ⋅ Ω ( log ( b ) / d ) when κ ( A t ) ≫ 1 \kappa(A_t) \gg1 κ ( A t ) ≫ 1 . This bound is conservative: S β ( A ) S_\beta(A) S β ( A ) can be as large as d \sqrt{d} d when A A A or A − 1 A^{-1} A − 1 has a highly spiked spectrum (Appendix § 11 .8).
Main Result. With control on both the drift and the second order growth, as long as κ ( A t ) ≥ 2 \kappa(A_t) \ge2 κ ( A t ) ≥ 2 , and the column-load m t m_t m t is not too large, we can observe a decay in the potential Φ β \Phi_\beta Φ β . Notice that this column load is directly controlled by using R b R_b R b , since due to the blocking structure, each column can have at most b − 1 b-1 b − 1 ones. Exploiting this yields a concrete bound on E [ Φ β ( A t ) − Φ β ( A 0 ) ] \mathbb{E}[\Phi_\beta(A_t)-\Phi_\beta(A_0)] E [ Φ β ( A t ) − Φ β ( A 0 )] , which allows us to control the expected time to conditioning.
Theorem 3. Suppose Q t ∼ Haar ( O ( d ) ) Q_t \sim\operatorname{Haar}(\mathrm{O}(d)) Q t ∼ Haar ( O ( d )) , and R t = R b ( A ~ t ) R_t = R_b(\widetilde{A}_t) R t = R b ( A t ) , with b = O ( log ( d ) ) b = O(\log(d)) b = O ( log ( d )) . Let β ∗ : = log ( d ) / log ( 8 / 7 ) \beta_* := \log(d)/\log(8/7) β ∗ := log ( d ) / log ( 8/7 ) , and set α = ν b , d / β ∗ ( b − 1 ) d − 1 \alpha= \nu_{b,d}/\beta_*(b-1)\sqrt{d-1} α = ν b , d / β ∗ ( b − 1 ) d − 1 . Let τ ∗ : = inf { t : κ ( A t ) ≤ 2 } \tau_* := \inf\{t:\kappa(A_t)\le2\} τ ∗ := inf { t : κ ( A t ) ≤ 2 } . Then
E [ τ ∗ ] = O ( d ⋅ polylog ( d ) ⋅ log ( κ ( A 0 ) ) ) . \mathbb{E}[\tau_*] = O\left(d\cdot\operatorname{polylog}(d)\cdot\log(\kappa(A_0))\right). E [ τ ∗ ] = O ( d ⋅ polylog ( d ) ⋅ log ( κ ( A 0 )) ) .
Thus, the idealized RAPID variant achieves conditioning in O ~ ( d ) \widetilde{O}(d) O ( d ) expected iterations, with logarithmic dependence on the initial condition number (see Appendix § 11 ). The proof uses the pessimistic bound S β ≥ 1 / 4 S_\beta\ge1/4 S β ≥ 1/4 ; more favorable spectra can yield faster conditioning and permit larger step sizes.
Practical step size without blocking. Balancing the negative drift of Lemma 2 against the second-order term of Lemma 1 suggests that we should choose α \alpha α to α ∗ = ν b , d 12 β d − 1 ⋅ S β m t \alpha_* = \frac{\nu_{b,d}}{12\beta\sqrt{d-1}}\cdot\frac{S_\beta}{m_t} α ∗ = 12 β d − 1 ν b , d ⋅ m t S β to maximize the expected gain. While m t m_t m t is easily computed, S β S_\beta S β depends on the spectrum and is difficult to estimate. The proof therefore controls m t m_t m t through blocking and uses a worst-case bound on S β S_\beta S β . Empirically, however, we observe S β / m t = Ω ( 1 ) S_\beta/\sqrt{m_t} = \Omega(1) S β / m t = Ω ( 1 ) even with global row selection, across diverse spectra and dimensions (Appendix § 11 .10). This suggests the practical step-size rule α ∗ ′ = Θ ( 1 / β m t d ) \alpha_*' = \Theta(1/\sqrt{\beta m_t d}) α ∗ ′ = Θ ( 1/ β m t d ) , which we use in our experiments.
Beyond Haar mixing. The Taylor bound of Lemma 1 and the spectral bound on S β S_\beta S β do not depend on the mixing distribution. Haar mixing is used only to establish the exact expected-drift identity (15), exploiting its rotational symmetry to characterize the effect of row-min selection. Randomized Walsh–Hadamard transforms also spread information across coordinates, but lack full rotational symmetry, making the drift harder to characterize. Extending the guarantee to randomized Walsh–Hadamard mixing would therefore require a corresponding drift bound, which remains open (see Appendix § 11 .§ 7 ).
Empirical role of the simplifying assumptions
Theorem 3 assumes Haar mixing to compute the expected drift and block-restricted row minima to bound the column load. We test whether these assumptions also improve empirical conditioning. Both comparisons use synthetic matrices with d = 2048 d = 2048 d = 2048 and initial κ = 10 4 \kappa= 10^4 κ = 1 0 4 .
Fast mixing. We compare Haar rotations with randomized Walsh–Hadamard transforms, using identical initial matrices, global row selection, and step-size rules. Across 100 trials per spectral family, Table 1 shows that the final condition numbers after T = 100 T = 100 T = 100 steps differ by at most 0.5%. Thus, fast structured mixing achieves essentially the same conditioning as Haar mixing.
Table 1. Haar versus Walsh–Hadamard mixing. Final condition numbers after T = 100 T = 100 T = 100 steps (mean ± standard deviation).
Global versus block row selection. We compare the practical global selector (9) with block-restricted selection (14) (block size 8), using identical Walsh–Hadamard mixing sequences. The global variant uses α t = s α / m t d log d \alpha_t = s_\alpha/\sqrt{m_t d\log d} α t = s α / m t d log d , while the blocked variant uses α t = s α / d log d \alpha_t = s_\alpha/\sqrt{d\log d} α t = s α / d log d . Table 2 shows that both improve conditioning, but the practical configuration achieves substantially larger reductions. Results are averaged over 20 trials; standard deviations are below 1.1 percentage points everywhere.
Table 2. Global versus block row minima. Mean condition-number reduction (%).
Together, these results show that the simplifying assumptions used in our proof are not needed for effective conditioning in practice: fast mixing matches Haar, while the practical global configuration substantially outperforms blocking. Establishing a theoretical guarantee for the practical algorithm remains open.
Conclusion
We introduced RAPID, an anytime SPD preconditioner derived from a conditioning mechanism discovered in a transformer trained for in-context learning. The extracted update preserves the linear-system relation and evolves its Gram matrix by congruence. RAPID turns this mechanism into a standalone algorithm combining randomized mixing and sparse row corrections, accumulating a preconditioner A t = P t A P t ⊤ A_t = P_t A P_t^\top A t = P t A P t ⊤ . The transformer provides only the algorithmic primitive; RAPID requires neither model inference nor learned parameters at solve time. For an idealized Haar-mixing, block-restricted variant, we prove convergence to any fixed condition-number target for arbitrary SPD matrices, with near-linear dependence on dimension and logarithmic dependence on initial conditioning. Experiments with practical RAPID show broad conditioning improvements and reduced CG iteration counts on synthetic and SuiteSparse matrices.
Several challenges remain. Extending the convergence guarantee to practical Walsh–Hadamard mixing and global row-minimum selection would close the gap between theory and implementation. Establishing competitive end-to-end runtime requires optimized implementations and careful accounting of setup costs, particularly when amortized across multiple right-hand sides. Finally, extending RAPID to sparse and matrix-free systems will require avoiding explicitly formed dense mixed matrices. More broadly, RAPID illustrates how studying learned transformer computations can lead to independent numerical algorithms that apply well beyond the original learning task.
Acknowledgments
This research was supported by the National Science Foundation grant CPS-2317079.
Supplementary material for Section 3
Transformer architecture and training details
This appendix specifies the training setup used for the in-context regression experiments in § 3.1 . We train attention-only transformers on noiseless synthetic linear regression instances. Unless stated otherwise, the experiments use d = 15 d = 15 d = 15 covariates and d + 1 = 16 d + 1 = 16 d + 1 = 16 tokens: d d d context examples and one query example.
Data distribution. For each batch element, we sample
x 1 , … , x d , x q ∼ i . i . d . N ( 0 , I d ) , w ∼ N ( 0 , I d ) , x_1,\ldots,x_d,x_q \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} \mathcal{N}(0,I_d), \qquad w \sim\mathcal{N}(0,I_d), x 1 , … , x d , x q ∼ i.i.d. N ( 0 , I d ) , w ∼ N ( 0 , I d ) ,
and set
y i = x i T w / d , y q = x q T w / d . y_i = x_i^{\mathsf{T}}w/\sqrt{d}, \qquad y_q = x_q^{\mathsf{T}}w/\sqrt{d}. y i = x i T w / d , y q = x q T w / d .
The factor 1 / d 1/\sqrt{d} 1/ d is a normalization convention; equivalently, the effective regression coefficient has covariance I d / d I_d/d I d / d . The model input is
Z 0 = [ x 1 T y 1 ⋮ ⋮ x d T y d x q T 0 ] ∈ R ( d + 1 ) × ( d + 1 ) , Z_0 =
\begin{bmatrix}
x_1^{\mathsf{T}} & y_1\\
\vdots& \vdots\\
x_d^{\mathsf{T}} & y_d\\
x_q^{\mathsf{T}} & 0
\end{bmatrix}
\in\mathbb{R}^{(d+1)\times(d+1)}, Z 0 = x 1 T ⋮ x d T x q T y 1 ⋮ y d 0 ∈ R ( d + 1 ) × ( d + 1 ) ,
and the loss is the squared error on the query label only,
L = ( ( Z L ) d + 1 , d + 1 + y q ) 2 . \mathcal{L} = \left((Z_L)_{d+1,d+1}+y_q\right)^2. L = ( ( Z L ) d + 1 , d + 1 + y q ) 2 .
The implementation reads the prediction y q y_q y q from the bottom-right entry of the final token matrix with the same negative-output convention as Von Oswald et al. [ [29 ] : y ^ q = − ( Z L ) d + 1 , d + 1 \hat{y}_q = -(Z_L)_{d+1,d+1} y ^ q = − ( Z L ) d + 1 , d + 1 . Fresh inputs and fresh regression coefficients are resampled at every training iteration.
Architecture. We use a residual attention-only transformer with no feed-forward blocks. Each layer has one attention head and embedding dimension d + 1 = 16 d + 1 = 16 d + 1 = 16 . For Z ∈ R ( d + 1 ) × ( d + 1 ) Z \in\mathbb{R}^{(d+1)\times(d+1)} Z ∈ R ( d + 1 ) × ( d + 1 ) , layer ℓ \ell ℓ computes
Z ℓ + 1 = Z ℓ + A ℓ ( Z ℓ ) Z ℓ W V , ℓ W P , ℓ , Z_{\ell+1} = Z_\ell+ A_\ell(Z_\ell)Z_\ell W_{V,\ell}W_{P,\ell}, Z ℓ + 1 = Z ℓ + A ℓ ( Z ℓ ) Z ℓ W V , ℓ W P , ℓ ,
where
A ℓ ( Z ) = softmax ( Z W Q , ℓ W K , ℓ T Z T + M ) . A_\ell(Z) = \operatorname{softmax}\left(ZW_{Q,\ell}W_{K,\ell}^{\mathsf{T}}Z^{\mathsf{T}} + M\right). A ℓ ( Z ) = softmax ( Z W Q , ℓ W K , ℓ T Z T + M ) .
All linear projections are bias-free. The matrices W Q , ℓ , W K , ℓ , W V , ℓ W_{Q,\ell}, W_{K,\ell}, W_{V,\ell} W Q , ℓ , W K , ℓ , W V , ℓ are initialized with Xavier uniform initialization, while the output projection W P , ℓ W_{P,\ell} W P , ℓ is initialized at zero. Thus the initial network is the identity map through the residual connection. For notational simplicity, we absorb the 1 / d + 1 1/\sqrt{d+1} 1/ d + 1 factor commonly present in the attention architecture [27 ] into the attention weights.
The attention mask removes the query token as a key/value:
M = [ 0 ( d + 1 ) × d − ∞ 1 d + 1 ] . M =
\begin{bmatrix}
0_{(d+1)\times d} & -\infty1_{d+1}
\end{bmatrix}. M = [ 0 ( d + 1 ) × d − ∞ 1 d + 1 ] .
Thus every token may attend to the d d d labeled context examples, but no token may attend to the query token. The query row is therefore used only as the prediction site.
Attention-logit clipping. For numerical stability and to avoid nearly one-hot attention early in training, we clip attention logits after centering each attention row. Let
s i j = q i T k j d + 1 s_{ij} = \frac{q_i^{\mathsf{T}}k_j}{\sqrt{d+1}} s ij = d + 1 q i T k j
denote the unmasked attention score, and let A i \mathcal{A}_i A i be the set of allowed (non-masked) keys under the attention mask. Before the softmax, we replace each allowed score by
s ~ i j = max { s i j − max j ′ ∈ A i s i j ′ , − 6 } , j ∈ A i , \widetilde{s}_{ij} = \max\left\{s_{ij} - \max_{j'\in\mathcal{A}_i}s_{ij'}, -6\right\}, \qquad j \in\mathcal{A}_i, s ij = max { s ij − j ′ ∈ A i max s i j ′ , − 6 } , j ∈ A i ,
and keep masked scores equal to − ∞ -\infty − ∞ . Hence the largest allowed logit in each row is zero, and all allowed logits are lower bounded by − 6 -6 − 6 . This bounds the maximum probability ratio between two allowed tokens by e 6 e^6 e 6 . We found this clipping useful for numerical stability when training deep models.
Symmetry augmentation. The reported training runs use the symmetry-augmented implementation. At each layer and for each forward pass, we draw independent Haar orthogonal matrices U ∈ R d × d U \in\mathbb{R}^{d \times d} U ∈ R d × d and V ∈ R d × d V \in\mathbb{R}^{d \times d} V ∈ R d × d , extend them by a fixed final row/column, and apply the attention block in the transformed coordinates:
Z ~ ℓ = diag ( U , 1 ) Z ℓ diag ( V , 1 ) . \widetilde{Z}_{\ell} = \operatorname{diag}(U,1) Z_{\ell} \operatorname{diag}(V,1). Z ℓ = diag ( U , 1 ) Z ℓ diag ( V , 1 ) .
The attention update is then rotated back before being added residually to Z ℓ Z_{\ell} Z ℓ . This augmentation preserves the distinguished query row and label coordinate while randomizing the basis of the context examples and features.
Optimization. We train each model with AdamW for 30,001 steps using batch size 8192, learning rate 10 − 3 10^{-3} 1 0 − 3 , ( β 1 , β 2 ) = ( 0.9 , 0.99 ) (\beta_1,\beta_2) = (0.9, 0.99) ( β 1 , β 2 ) = ( 0.9 , 0.99 ) , no weight decay, and global gradient clipping at norm 1. The learning rate is linearly warmed up for the first 500 steps and then held fixed. We resample both the covariates and regression coefficient at every step. We train ten independent runs for each depth
L ∈ { 1 , 2 , 3 , 5 , 7 , 10 , 15 , 20 , 30 } , L \in\{1, 2, 3, 5, 7, 10, 15, 20, 30\}, L ∈ { 1 , 2 , 3 , 5 , 7 , 10 , 15 , 20 , 30 } ,
and use the depth-30 models for the extraction analysis unless otherwise specified.
Training curves. Figure 3 reports the training loss for the depth-30 models used in the extraction analysis. Thin curves show individual runs; the thick curve shows the mean across runs, with the shaded band denoting the central 80% interval.
Figure 3. Training curves for depth-30 transformers. The loss is the squared error on the query prediction. Inputs and regression coefficients are resampled at every optimization step.
Behavioral diagnostics
We evaluate the trained symmetry-intervened transformers in the square d = 15 d = 15 d = 15 linear-system setting. For each depth L ≤ 30 L \le30 L ≤ 30 , GD and CG are run for L L L iterations from zero. GD uses a fixed stepsize selected separately for each iteration budget from 60 logarithmically spaced values in [ 10 − 4 , 3 ] [10^{-4}, 3] [ 1 0 − 4 , 3 ] , minimizing query-prediction MSE on 4,096 validation tasks. Results are evaluated on 4,096 independent test tasks.
Prediction error. Figure 4 (left) shows that test MSE decreases with model depth. The error profile differs from GD and CG at matched iteration budgets, suggesting that the transformer does not simply reproduce either classical solver.
Figure 4. Prediction behavior across transformer depths. Left: Test MSE decreases with model depth, following a profile distinct from GD and CG at matched iteration budgets. Right: The fitted endpoint spectral gain approaches the OLS response 1 / λ 1/\lambda 1/ λ across eigendirections of X ⊤ X / d X^\top X/d X ⊤ X / d , including small eigenvalues.
Spectral inverse-kernel diagnostic. For each fixed context X X X , we probe the endpoint with random queries and fit the best linear query map
y ^ q T F ≈ x q T β ^ T F ( X ) . \widehat{y}^{\mathrm{TF}}_q \approx x_q^{\mathsf{T}} \widehat{\beta}_{\mathrm{TF}}(X). y q TF ≈ x q T β TF ( X ) .
We then express β ^ T F \widehat{\beta}_{\mathrm{TF}} β TF in the eigenbasis of H = X T X / d = U diag ( λ j ) U T H = X^{\mathsf{T}}X/d = U\operatorname{diag}(\lambda_j)U^{\mathsf{T}} H = X T X / d = U diag ( λ j ) U T . Since exact OLS satisfies
β ⋆ , e , j = λ j − 1 b e , j , b e = U T X T y / d , (16) \beta_{\star,e,j} = \lambda_j^{-1}b_{e,j}, \qquad b_e = U^{\mathsf{T}}X^{\mathsf{T}}y/d, \tag*{(16)} β ⋆ , e , j = λ j − 1 b e , j , b e = U T X T y / d , (16)
the ideal gain in eigendirection j j j is 1 / λ j 1/\lambda_j 1/ λ j . The plotted gain is the zero-intercept slope mapping b e , j b_{e,j} b e , j to β ^ e , j \widehat{\beta}_{e,j} β e , j , after pooling eigendirections across contexts and binning by λ j \lambda_j λ j :
g B = ∑ ( c , j ) ∈ B β ^ e , c , j b e , c , j ∑ ( c , j ) ∈ B b e , c , j 2 . g_{\mathsf{B}} = \frac{\sum_{(c,j)\in\mathsf{B}} \widehat{\beta}_{e,c,j} b_{e,c,j}}{\sum_{(c,j)\in\mathsf{B}} b_{e,c,j}^{2}}. g B = ∑ ( c , j ) ∈ B b e , c , j 2 ∑ ( c , j ) ∈ B β e , c , j b e , c , j .
Figure 4 (right) shows that the fitted gain approaches the OLS response 1 / λ 1/\lambda 1/ λ as depth increases, including at small eigenvalues. Thus the transformer increasingly captures the full inverse spectral response rather than only the well-conditioned directions.
Linearity of the query map. This spectral diagnostic is meaningful only if, for fixed context, the endpoint is well approximated by a linear function of the query. We check this by plotting the squared residual fraction
∑ q ( y ^ q T F − x q ⊤ β ^ T F ) 2 ∑ q ( y ^ q T F ) 2 . \frac{\sum_q \left(\widehat{y}^{\mathrm{TF}}_q-x_q^{\top}\widehat{\beta}_{\mathrm{TF}}\right)^2}{\sum_q \left(\widehat{y}^{\mathrm{TF}}_q\right)^2}. ∑ q ( y q TF ) 2 ∑ q ( y q TF − x q ⊤ β TF ) 2 .
As shown in Figure 5 (right), this residual fraction decreases with depth and is below 10 − 2 10^{-2} 1 0 − 2 at depth 30. Thus the fitted linear query map explains more than 99% of the transformer’s prediction energy on the probe queries, validating the spectral-filter interpretation for the depth-30 models.
Figure 5. Additional behavioral diagnostics. Left: Pearson correlations between centered residual-error vectors on shared test tasks. Transformer runs remain more aligned with each other than with GD or CG. Right: Squared residual fraction of the best linear query-to-prediction map for each context. The small residual at depth 30 supports the spectral-filter interpretation.
Residual-error alignment. To compare failure modes, we compute the centered residual-error vector
e c = ( y ^ − y q ) − 1 N 11 ⊤ ( y ^ − y q ) e_c=(\widehat{y}-y_q)-\frac{1}{N}\mathbf{1}\mathbf{1}^{\top}(\widehat{y}-y_q) e c = ( y − y q ) − N 1 1 1 ⊤ ( y − y q )
on a shared test set, and report Pearson correlations between such vectors. Transformer-Transformer (TF-TF) alignment is computed by splitting trained transformer runs into two groups and correlating the group-averaged residuals; TF-GD and TF-CG compare the same transformer averages to GD and CG. As shown in Figure 5 (left), TF-TF alignment remains high at depth 30 (r ≈ 0.8 r \approx0.8 r ≈ 0.8 ), while TF-GD and TF-CG fall below 0.5. Thus independently trained transformers share a stable residual structure that is not well explained by either classical baseline.
Extracted iteration and fidelity diagnostics
We describe the two-scalar approximation used in § 3.2 . For each trained layer, let
W Q K , ℓ = W Q , ℓ W K , ℓ T , W V P , ℓ = W V , ℓ W P , ℓ . W_{QK,\ell} = W_{Q,\ell}W_{K,\ell}^{\mathsf{T}}, \qquad W_{VP,\ell} = W_{V,\ell}W_{P,\ell}. W Q K , ℓ = W Q , ℓ W K , ℓ T , W V P , ℓ = W V , ℓ W P , ℓ .
We approximate these products as
W ~ Q K , ℓ = γ ℓ [ I d 0 0 0 ] , W ~ V P , ℓ = α ℓ I d + 1 . \widetilde{W}_{QK,\ell} = \gamma_{\ell}\begin{bmatrix} I_d & 0 \\ 0 & 0 \end{bmatrix}, \qquad\widetilde{W}_{VP,\ell} = \alpha_{\ell}I_{d+1}. W Q K , ℓ = γ ℓ [ I d 0 0 0 ] , W V P , ℓ = α ℓ I d + 1 .
Here γ ℓ \gamma_{\ell} γ ℓ is the mean diagonal entry of the feature-feature block of W Q K , ℓ W_{QK,\ell} W Q K , ℓ , and α ℓ \alpha_{\ell} α ℓ is the mean diagonal entry of the feature-feature block of W V P , ℓ W_{VP,\ell} W V P , ℓ . In the projected value map, the label coordinate is tied to the same scalar α ℓ \alpha_{\ell} α ℓ , giving the two-scalar template used in the main text. All off-diagonal entries and all Q K QK Q K entries involving the label coordinate are discarded.
Write the full state as
Z ℓ = [ X ℓ y ℓ x q , ℓ y ^ ℓ ] . Z_{\ell} = \begin{bmatrix} X_{\ell} & y_{\ell} \\ x_{q,\ell} & \hat{y}_{\ell} \end{bmatrix}. Z ℓ = [ X ℓ x q , ℓ y ℓ y ^ ℓ ] .
Under the symmetry intervention, the layer applies attention in a randomly rotated context basis and then rotates the update back. With the projected weights, the context attention is
A ℓ = σ ( γ ℓ U ℓ X ℓ X ℓ T U ℓ T ) , A_{\ell} = \sigma\left(\gamma_{\ell}U_{\ell}X_{\ell}X_{\ell}^{\mathsf{T}}U_{\ell}^{\mathsf{T}}\right), A ℓ = σ ( γ ℓ U ℓ X ℓ X ℓ T U ℓ T ) ,
and the corresponding context update is
X ℓ + 1 = C ℓ X ℓ , y ℓ + 1 = C ℓ y ℓ , C ℓ = I + α ℓ U ℓ T A ℓ U ℓ . X_{\ell+1} = C_{\ell}X_{\ell}, \qquad y_{\ell+1} = C_{\ell}y_{\ell}, \qquad C_{\ell} = I + \alpha_{\ell}U_{\ell}^{\mathsf{T}}A_{\ell}U_{\ell}. X ℓ + 1 = C ℓ X ℓ , y ℓ + 1 = C ℓ y ℓ , C ℓ = I + α ℓ U ℓ T A ℓ U ℓ .
Thus the projection gives the row-side iteration used in the main text. The same projected layer also updates the query row and readout. If
a ℓ T = σ ( γ ℓ x q , ℓ T X ℓ X ℓ T U ℓ T ) a_{\ell}^{\mathsf{T}} = \sigma\left(\gamma_{\ell}x_{q,\ell}^{\mathsf{T}}X_{\ell}X_{\ell}^{\mathsf{T}}U_{\ell}^{\mathsf{T}}\right) a ℓ T = σ ( γ ℓ x q , ℓ T X ℓ X ℓ T U ℓ T )
is the query-to-context attention row, then
x q , ℓ + 1 T = x q , ℓ T + α ℓ a ℓ T U ℓ X ℓ , y ^ ℓ + 1 = y ^ ℓ + α ℓ a ℓ T U ℓ y ℓ . x_{q,\ell+1}^{\mathsf{T}} = x_{q,\ell}^{\mathsf{T}} + \alpha_{\ell}a_{\ell}^{\mathsf{T}}U_{\ell}X_{\ell}, \qquad\hat{y}_{\ell+1} = \hat{y}_{\ell} + \alpha_{\ell}a_{\ell}^{\mathsf{T}}U_{\ell}y_{\ell}. x q , ℓ + 1 T = x q , ℓ T + α ℓ a ℓ T U ℓ X ℓ , y ^ ℓ + 1 = y ^ ℓ + α ℓ a ℓ T U ℓ y ℓ .
Fidelity of the projection. We evaluate the projection by comparing the original depth-30 transformer and the projected iteration on the same held-out tasks, using the same random rotations in both forward passes. Predictions are pooled across evaluation tasks and trained runs. The reported R 2 R^2 R 2 is the squared Pearson correlation between the original transformer predictions and the projected-iteration predictions:
R 2 = Corr ( y ^ T F , y ^ p r o j ) 2 . R^2 = \operatorname{Corr}\left(\hat{y}^{\mathrm{TF}},\hat{y}^{\mathrm{proj}}\right)^2. R 2 = Corr ( y ^ TF , y ^ proj ) 2 .
The MSE change is computed on the same pooled predictions as
Δ M S E = 1 R N ∑ r = 1 R ∑ i = 1 N [ ( y ^ r , i p r o j − y i ) 2 − ( y ^ r , i T F − y i ) 2 ] . \Delta\mathrm{MSE} = \frac{1}{RN}\sum_{r=1}^{R}\sum_{i=1}^{N}\left[\left(\hat{y}_{r,i}^{\mathrm{proj}}-y_i\right)^2-\left(\hat{y}_{r,i}^{\mathrm{TF}}-y_i\right)^2\right]. Δ MSE = R N 1 r = 1 ∑ R i = 1 ∑ N [ ( y ^ r , i proj − y i ) 2 − ( y ^ r , i TF − y i ) 2 ] .
The projection preserves the trained model closely: R 2 > 0.98 R^2 > 0.98 R 2 > 0.98 , and the test MSE changes by only 6.4 × 10 − 3 6.4 \times10^{-3} 6.4 × 1 0 − 3 . Figure 6 shows the corresponding prediction-level agreement.
Figure 6. Fidelity of the projected iteration. Each point compares the original depth-30 transformer prediction with the prediction from the two-scalar projected iteration on the same held-out task. The high R 2 R^2 R 2 shows that the low-dimensional projection captures the dominant predictive behavior of the trained model.
Conditioning behavior and the layerwise sign rule
This appendix gives the empirical evidence behind the preconditioning interpretation in § 3.2 . The main questions are: (i) does the extracted iteration actually improve conditioning layer by layer, and (ii) when does a layer act as a conditioning step?
Conditioning under the extracted and projected iterations. Figure 7 compares the conditioning trajectories of the trained depth-30 transformer and its two-scalar approximation. In both cases, the median condition number of G ℓ = X ℓ X ℓ ⊤ G_\ell= X_\ell X_\ell^\top G ℓ = X ℓ X ℓ ⊤ decreases from above 3 × 10 3 3 \times10^3 3 × 1 0 3 to below 10 at the best layer. Thus the low-dimensional approximation captures the conditioning behavior of the trained model.
Figure 7. Conditioning overview. Left: Condition number of G ℓ = X ℓ X ℓ ⊤ G_\ell= X_\ell X_\ell^\top G ℓ = X ℓ X ℓ ⊤ across layers of the trained transformer. Center: The corresponding trajectory under the two-scalar approximation. Both reduce the median condition number from above 3 × 10 3 3 \times10^3 3 × 1 0 3 to below 10 at the best layer. Right: Distribution of learned step sizes α ℓ \alpha_\ell α ℓ , most of which lie close to the sufficient invertibility threshold α ℓ = 1 \alpha_\ell= 1 α ℓ = 1 .
The right panel shows that most learned step sizes α ℓ \alpha_\ell α ℓ are close to 1. Since the softmax matrix K ℓ K_\ell K ℓ is row-stochastic, ∣ α ℓ ∣ < 1 \lvert\alpha_\ell\rvert< 1 ∣ α ℓ ∣ < 1 guarantees that I + α ℓ K ℓ I + \alpha_\ell K_\ell I + α ℓ K ℓ is invertible, preserving positive definiteness under the congruence update. The learned values suggest that the model prefers large residual steps within this invertibility range.
Both trajectories exhibit occasional increases in condition number, particularly near the final layers. This is consistent with the transformer being trained for best final prediction at fixed depth, rather than for monotone conditioning at every intermediate layer.
Which layers condition? Empirically, layers tend to reduce the condition number when their parameters satisfy
sign ( α ℓ ) ≠ sign ( γ ℓ ) , ∣ α ℓ ∣ < 1. (17) \operatorname{sign}(\alpha_\ell) \ne\operatorname{sign}(\gamma_\ell), \qquad\lvert\alpha_\ell\rvert< 1. \tag*{(17)} sign ( α ℓ ) = sign ( γ ℓ ) , ∣ α ℓ ∣ < 1. (17)
For example, when α ℓ > 0 \alpha_\ell> 0 α ℓ > 0 and γ ℓ < 0 \gamma_\ell< 0 γ ℓ < 0 , attention favors smaller entries of the mixed Gram matrix, which receive positive weight in the residual update. Figure 8 compares this rule with the observed layerwise conditioning trajectories.
Figure 8. Layerwise sign rule and conditioning. Layerwise condition numbers compared with the empirical criterion sign ( α ℓ ) ≠ sign ( γ ℓ ) \operatorname{sign}(\alpha_\ell) \ne\operatorname{sign}(\gamma_\ell) sign ( α ℓ ) = sign ( γ ℓ ) and ∣ α ℓ ∣ < 1 |\alpha_\ell| < 1 ∣ α ℓ ∣ < 1 . Layers satisfying this rule typically decrease the condition number.
Across runs, 80% of layers satisfy the rule, and in the median such layer, 95.5% of test instances decrease their condition number. Thus the learned parameters provide a useful empirical indicator of conditioning steps, although the rule does not guarantee a decrease on every instance.
Additional Experimental Details
Synthetic matrices. We generate A = U Λ U T A = U\Lambda U^{\mathsf{T}} A = U Λ U T , where U U U is Haar-random orthogonal and Λ \Lambda Λ has one of four spectra, defined for i = 0 , … , d − 1 i = 0,\ldots,d-1 i = 0 , … , d − 1 :
Chebyshev: λ i = κ + 1 2 − κ − 1 2 cos ( ( 2 i + 1 ) π 2 d ) , Linear: λ i = 1 + ( κ − 1 ) i d − 1 , Logarithmic: λ i = κ i / ( d − 1 ) , Power-law: λ i = 1 + ( κ − 1 ) ( i d − 1 ) 2 . \begin{aligned}
\text{Chebyshev:}\quad&\lambda_i = \frac{\kappa+1}{2} - \frac{\kappa-1}{2}\cos\left(\frac{(2i+1)\pi}{2d}\right),\\
\text{Linear:}\quad&\lambda_i = 1 + (\kappa-1)\frac{i}{d-1},\\
\text{Logarithmic:}\quad&\lambda_i = \kappa^{i/(d-1)},\\
\text{Power-law:}\quad&\lambda_i = 1 + (\kappa-1)\left(\frac{i}{d-1}\right)^2.
\end{aligned} Chebyshev: Linear: Logarithmic: Power-law: λ i = 2 κ + 1 − 2 κ − 1 cos ( 2 d ( 2 i + 1 ) π ) , λ i = 1 + ( κ − 1 ) d − 1 i , λ i = κ i / ( d − 1 ) , λ i = 1 + ( κ − 1 ) ( d − 1 i ) 2 .
We set the spectral endpoints to 1 and κ = 10 4 \kappa= 10^4 κ = 1 0 4 and use d = 1024 d = 1024 d = 1024 , with 100 independent draws per family.
SuiteSparse matrices. We use 31 SPD matrices from the SuiteSparse Matrix Collection [15 ] , selected by dimension (100 ≤ d ≤ 6000 100 \le d \le6000 100 ≤ d ≤ 6000 ) and post-Jacobi condition number (10 3 10^3 1 0 3 –10 6 10^6 1 0 6 ), independently of RAPID’s performance. The selected instances, grouped by collection, are:
Boeing: msc00726, msc01440;
Cannizzo: sts4098;
Cylshell: s1rmq4m1, s1rmt3m1;
HB: 1138_bus, 494_bus, 662_bus, 685_bus, bcsstk03, bcsstk04, bcsstk05, bcsstk06, bcsstk07, bcsstk08, bcsstk09, bcsstk10, bcsstk13, bcsstk14, bcsstk15, bcsstk21, bcsstk22, bcsstk26, bcsstk27, bcsstm12, lund_a, nos3, nos5;
Nasa: nasa1824, nasa2910;
TKK: plbuckle.
All matrices are converted to dense form. We normalize by an estimate of the largest eigenvalue (20 power iterations) and apply Jacobi scaling. For each matrix, we sample an independent Gaussian right-hand side before applying the same coordinate scaling.
RAPID implementation. We implement RAPID on the GPU using PyTorch/Triton and fast Walsh–Hadamard transforms [9 ] . We use one randomized Hadamard mixing stage (k = 1 k = 1 k = 1 ), global row-minimum selection, and s α = 10 s_\alpha= 10 s α = 10 . A single mixing stage suffices in practice, as repeated RAPID iterations progressively mix the coordinates. The row-selection kernel finds the smallest off-diagonal entry in each row and computes the maximum column multiplicity m t m_t m t . A parallel Triton kernel then applies the congruence update entrywise:
( A t + 1 ) i j = A ~ i j + α t A ~ τ ( i ) , j + α t A ~ i , τ ( j ) + α t 2 A ~ τ ( i ) , τ ( j ) . (A_{t+1})_{ij} = \widetilde{A}_{ij} + \alpha_t\widetilde{A}_{\tau(i),j} + \alpha_t\widetilde{A}_{i,\tau(j)} + \alpha_t^2\widetilde{A}_{\tau(i),\tau(j)}. ( A t + 1 ) ij = A ij + α t A τ ( i ) , j + α t A i , τ ( j ) + α t 2 A τ ( i ) , τ ( j ) .
where α t = s α m t d log d \alpha_t = \frac{s_\alpha}{\sqrt{m_t d\log d}} α t = m t d l o g d s α . We accumulate the transformation P t P_t P t as in § 4 to recover solutions in the original coordinates. Non-power-of-two dimensions are padded to the next power of two with an identity block; the right-hand side is padded with zeros. We evaluate RAPID after T ∈ { 10 , 20 , 50 , 100 , 200 , 500 } T \in\{10, 20, 50, 100, 200, 500\} T ∈ { 10 , 20 , 50 , 100 , 200 , 500 } steps.
Nyström preconditioning. For each sketch fraction q ∈ { 0.01 , 0.02 , 0.05 , 0.1 , 0.2 , 0.5 } q \in\{0.01, 0.02, 0.05, 0.1, 0.2, 0.5\} q ∈ { 0.01 , 0.02 , 0.05 , 0.1 , 0.2 , 0.5 } , we use a Gaussian sketch of rank r = ⌈ q d ⌉ r = \lceil qd\rceil r = ⌈ q d ⌉ , orthonormalized by QR. We form Y = A 0 Ω Y = A_0\Omega Y = A 0 Ω and B = Ω T Y B = \Omega^{\mathsf{T}}Y B = Ω T Y , then construct a stabilized Nyström approximation using Cholesky and eigendecomposition. Its approximate eigenvectors U U U and positive eigenvalue estimates λ ^ i \widehat{\lambda}_i λ i define the preconditioner
M = I + U diag ( θ λ ^ i − 1 ) U T , θ = min i λ ^ i . M = I + U\operatorname{diag}\left(\frac{\theta}{\widehat{\lambda}_i}-1\right)U^{\mathsf{T}},\qquad\theta= \min_i\widehat{\lambda}_i. M = I + U diag ( λ i θ − 1 ) U T , θ = i min λ i .
We apply M M M within preconditioned CG.
CG and evaluation. All solves use a common GPU float32 CG implementation, initialized at zero, with at most 10 4 10^4 1 0 4 iterations. The true relative residual is checked every 10 iterations, after recovering the solution in the Jacobi-scaled reference system A 0 x = b 0 A_0x = b_0 A 0 x = b 0 . Convergence requires
∥ A 0 x ~ − b 0 ∥ 2 ∥ b 0 ∥ 2 ≤ 2 × 10 − 3 . \frac{\lVert A_0\widetilde{x}-b_0\rVert_2}{\lVert b_0\rVert_2} \le2\times10^{-3}. ∥ b 0 ∥ 2 ∥ A 0 x − b 0 ∥ 2 ≤ 2 × 1 0 − 3 .
Table 3. Absolute condition numbers and CG iterations. Mean values across 100 independent matrices per synthetic family and 31 SuiteSparse matrices. All RAPID runs reached the target accuracy (100/100 per synthetic family and 31/31 for SuiteSparse) at every tested step count. The only non-convergent run was Nyström with a 1% sketch on the SuiteSparse matrix Cylshell/s1rmt3m1. These averages of absolute quantities differ from the averages of per-instance ratios shown in Figure 2 .
Condition numbers are computed from the extreme eigenvalues of the transformed matrices. Figure 2 reports condition numbers and CG iteration counts relative to the Jacobi baseline, with means and minimum-maximum ranges for RAPID and means for Nyström. All comparisons use the same matrices and right-hand sides.
Algorithm 2 Block row-min preconditioning
Input: A 0 ≻ 0 A_0 \succ0 A 0 ≻ 0 , step size α \alpha α , iterations T T T , block size b b b , mixer distribution Q Q Q .
for t = 0 , … , T − 1 t = 0, \ldots, T - 1 t = 0 , … , T − 1 do
Draw Q t ∼ Q Q_t \sim Q Q t ∼ Q and a block partition B t \mathcal{B}_t B t of [ d ] [d] [ d ] with block size b b b .
A ~ t ← Q t T A t Q t \widetilde{A}_t \leftarrow Q_t^{\mathsf{T}} A_t Q_t A t ← Q t T A t Q t .
R t ← BRM B t ( A ~ t ) R_t \leftarrow\operatorname{BRM}_{\mathcal{B}_t}(\widetilde{A}_t) R t ← BRM B t ( A t ) .
A t + 1 ← ( I + α R t ) T A ~ t ( I + α R t ) A_{t+1} \leftarrow(I + \alpha R_t)^{\mathsf{T}} \widetilde{A}_t (I + \alpha R_t) A t + 1 ← ( I + α R t ) T A t ( I + α R t ) .
end for
return A T A_T A T .
Proof of the Haar Block-Row-Min Guarantee
This appendix proves Theorem 3 . Let us define the block row selector:
Block row-min selector. For a partition B \mathcal{B} B of [ d ] [d] [ d ] into blocks of size b b b , Define
BRM B ( M ) i j = 1 { j = arg min ℓ ∈ B ( i ) ∖ { i } M i ℓ } . (18) \operatorname{BRM}_{\mathcal{B}}(M)_{ij} = \mathbf{1}\left\{j = \underset{\ell\in\mathcal{B}(i)\setminus\{i\}}{\operatorname{arg\,min}} M_{i\ell}\right\}. \tag*{(18)} BRM B ( M ) ij = 1 { j = ℓ ∈ B ( i ) ∖ { i } arg min M i ℓ } . (18)
where B ( i ) ∈ B \mathcal{B}(i) \in\mathcal{B} B ( i ) ∈ B is the block containing i i i . Ties are broken deterministically. The theory uses Q t ∼ Haar ( O ( d ) ) Q_t \sim\operatorname{Haar}(O(d)) Q t ∼ Haar ( O ( d )) ; experiments also use block-local choices based on product of Hadamard matrices of Q t Q_t Q t .
Let us state the theorem in full generality here. We analyze the Gram recursion extracted in § 3 :
A ~ t = Q t T A t Q t , A t + 1 = ( I + α R t ) T A ~ t ( I + α R t ) , R t = BRM B t ( A ~ t ) , (19) \widetilde{A}_t = Q_t^{\mathsf{T}} A_t Q_t, \qquad A_{t+1} = (I + \alpha R_t)^{\mathsf{T}} \widetilde{A}_t (I + \alpha R_t), \qquad R_t = \operatorname{BRM}_{\mathcal{B}_t}(\widetilde{A}_t), \tag*{(19)} A t = Q t T A t Q t , A t + 1 = ( I + α R t ) T A t ( I + α R t ) , R t = BRM B t ( A t ) , (19)
started from an arbitrary A 0 ≻ 0 A_0 \succ0 A 0 ≻ 0 . The theorem is proved for fresh uniform random orthogonal mixing, Q t ∼ Haar ( O ( d ) ) Q_t \sim\operatorname{Haar}(O(d)) Q t ∼ Haar ( O ( d )) . This distributional assumption is used only in the local row-min drift calculation; the Taylor expansion, trace identities, block-load bound, spectral lower bound, and stopping-time argument hold for any orthogonal mixer.
For the block selector defined in (18) , each row selects one off-diagonal entry from its block and each column can be selected by at most b − 1 b - 1 b − 1 rows. Thus
∥ R t ∥ op 2 ≤ b − 1. (20) \lVert R_t \rVert_{\operatorname{op}}^2 \le b - 1. \tag*{(20)} ∥ R t ∥ op 2 ≤ b − 1. (20)
This deterministic load bound is the only property of the block mask used in the Taylor remainder.
Theorem 4 (Uniform-random-rotation block row-min preconditioning). Let d ≥ 3 d \ge3 d ≥ 3 , 3 ≤ b ≤ d 3 \le b \le d 3 ≤ b ≤ d , and b ∣ d b \mid d b ∣ d . Fix a target condition number κ ⋆ > 1 \kappa_\star> 1 κ ⋆ > 1 , and define
ρ κ ⋆ = max { 1 − 1 − κ ⋆ − 1 4 , ( 1 + κ ⋆ − 1 4 ) − 1 } < 1. (21) \rho_{\kappa_\star} = \max\left\{1 - \frac{1 - \kappa_\star^{-1}}{4}, \left(1 + \frac{\kappa_\star- 1}{4}\right)^{-1}\right\} < 1. \tag*{(21)} ρ κ ⋆ = max { 1 − 4 1 − κ ⋆ − 1 , ( 1 + 4 κ ⋆ − 1 ) − 1 } < 1. (21) Choose
β ≥ log ( 8 d ) − log ρ κ ⋆ . (22) \beta\ge\frac{\log(8d)}{-\log\rho_{\kappa_\star}}. \tag*{(22)} β ≥ − log ρ κ ⋆ log ( 8 d ) . (22) Let
ν b , d = − d − 1 E [ min 1 ≤ r ≤ b − 1 U r ] , U ∼ Unif ( S d − 2 ) . (23) \nu_{b,d} = -\sqrt{d - 1}\,\mathbb{E}\left[\min_{1 \le r \le b - 1} U_r\right], \qquad U \sim\operatorname{Unif}(\mathbb{S}^{d-2}). \tag*{(23)} ν b , d = − d − 1 E [ 1 ≤ r ≤ b − 1 min U r ] , U ∼ Unif ( S d − 2 ) . (23) There are universal constants C s t e p , C h i t > 0 C_{\mathrm{step}}, C_{\mathrm{hit}} > 0 C step , C hit > 0 such that, for
α = ν b , d C s t e p β ( b − 1 ) d − 1 , (24) \alpha= \frac{\nu_{b,d}}{C_{\mathrm{step}}\beta(b - 1)\sqrt{d - 1}}, \tag*{(24)} α = C step β ( b − 1 ) d − 1 ν b , d , (24) the iteration (18) with fresh Q t ∼ Haar ( O ( d ) ) Q_t \sim\operatorname{Haar}(O(d)) Q t ∼ Haar ( O ( d )) satisfies
E [ τ κ ⋆ ] ≤ C h i t β ( b − 1 ) ( d − 1 ) ν b , d 2 log κ ( A 0 ) , τ κ ⋆ = inf { t : κ ( A t ) ≤ κ ⋆ } . (25) \mathbb{E}[\tau_{\kappa_\star}] \le C_{\mathrm{hit}} \frac{\beta(b - 1)(d - 1)}{\nu_{b,d}^{2}} \log\kappa(A_0), \qquad\tau_{\kappa_\star} = \inf\{t : \kappa(A_t) \le\kappa_\star\}. \tag*{(25)} E [ τ κ ⋆ ] ≤ C hit ν b , d 2 β ( b − 1 ) ( d − 1 ) log κ ( A 0 ) , τ κ ⋆ = inf { t : κ ( A t ) ≤ κ ⋆ } . (25) For each fixed b ≥ 3 b \ge3 b ≥ 3 , ν b , d 2 = Θ b ( 1 ) \nu_{b,d}^{2} = \Theta_b(1) ν b , d 2 = Θ b ( 1 ) uniformly in d d d . Hence, for fixed b b b and fixed κ ⋆ \kappa_\star κ ⋆ ,
E [ τ κ ⋆ ] = O κ ⋆ , b ( d log d log κ ( A 0 ) ) . (26) \mathbb{E}[\tau_{\kappa_\star}] = O_{\kappa_\star,b}(d \log d \log\kappa(A_0)). \tag*{(26)} E [ τ κ ⋆ ] = O κ ⋆ , b ( d log d log κ ( A 0 )) . (26)
Theorem 4 is a refinement of Theorem 3 from the main text. The rest of the analysis will focus on proving this result. In the process, we will show improved versions of Lemma 2 and Lemma 1 .
Setup and potential
Let A 0 ≻ 0 A_0 \succ0 A 0 ≻ 0 and let
A t + 1 = ( I + α R t ) ⊤ A ~ t ( I + α R t ) , A ~ t = Q t ⊤ A t Q t , Q t ∼ Haar ( O ( d ) ) . A_{t+1} = (I + \alpha R_t)^\top\widetilde{A}_t(I + \alpha R_t), \qquad\widetilde{A}_t = Q_t^\top A_tQ_t, \qquad Q_t \sim\operatorname{Haar}(O(d)). A t + 1 = ( I + α R t ) ⊤ A t ( I + α R t ) , A t = Q t ⊤ A t Q t , Q t ∼ Haar ( O ( d )) .
Fix a block partition [ d ] = B 1 ⊔ ⋯ ⊔ B d / b [d] = B_1 \sqcup\cdots\sqcup B_{d/b} [ d ] = B 1 ⊔ ⋯ ⊔ B d / b , ∣ B r ∣ = b |B_r| = b ∣ B r ∣ = b . For i ∈ B r i \in B_r i ∈ B r , define
τ i = arg min j ∈ B r , j ≠ i ( A ~ t ) i j , ( R t ) i j = 1 { j = τ i } , \tau_i = \underset{j\in B_r,\;j\ne i}{\arg\min}\;(\widetilde{A}_t)_{ij}, \qquad(R_t)_{ij} = 1\{j = \tau_i\}, τ i = j ∈ B r , j = i arg min ( A t ) ij , ( R t ) ij = 1 { j = τ i } ,
with deterministic tie-breaking. A fresh independent random partition may also be used, but the Haar proof only needs the candidate sets to be fixed independently of Q t Q_t Q t .
For β ≥ 1 \beta\ge1 β ≥ 1 , define
Φ β ( A ) = 1 β log tr ( A β ) d + 1 β log tr ( A − β ) d . \Phi_\beta(A) = \frac{1}{\beta}\log\frac{\operatorname{tr}(A^\beta)}{d} + \frac{1}{\beta}\log\frac{\operatorname{tr}(A^{-\beta})}{d}. Φ β ( A ) = β 1 log d tr ( A β ) + β 1 log d tr ( A − β ) .
This potential is scale-invariant and satisfies
0 ≤ Φ β ( A ) ≤ log κ ( A ) ≤ Φ β ( A ) + 2 log d β . 0 \le\Phi_\beta(A) \le\log\kappa(A) \le\Phi_\beta(A) + \frac{2\log d}{\beta}. 0 ≤ Φ β ( A ) ≤ log κ ( A ) ≤ Φ β ( A ) + β 2 log d .
Let λ = ( λ 1 , … , λ d ) \lambda= (\lambda_1,\ldots,\lambda_d) λ = ( λ 1 , … , λ d ) be the eigenvalues of A A A , and let
p ∼ Dir ( 1 / 2 , … , 1 / 2 ) . p \sim\operatorname{Dir}(1/2,\ldots,1/2). p ∼ Dir ( 1/2 , … , 1/2 ) .
Define
Var p ( λ ) = ∑ i p i λ i 2 − ( ∑ i p i λ i ) 2 , \operatorname{Var}_p(\lambda) = \sum_i p_i\lambda_i^2 - \left(\sum_i p_i\lambda_i\right)^2, Var p ( λ ) = i ∑ p i λ i 2 − ( i ∑ p i λ i ) 2 ,
Cov p ( λ , λ γ ) = ∑ i p i λ i γ + 1 − ( ∑ i p i λ i ) ( ∑ i p i λ i γ ) . \operatorname{Cov}_p(\lambda,\lambda^\gamma) = \sum_i p_i\lambda_i^{\gamma+1} - \left(\sum_i p_i\lambda_i\right)\left(\sum_i p_i\lambda_i^\gamma\right). Cov p ( λ , λ γ ) = i ∑ p i λ i γ + 1 − ( i ∑ p i λ i ) ( i ∑ p i λ i γ ) .
Ratios below are defined to be zero when Var p ( λ ) = 0 \operatorname{Var}_p(\lambda)=0 Var p ( λ ) = 0 . Set
s β ( A ) = E p [ Cov p ( λ , λ β ) Var p ( λ ) ] , s − β ( A ) = − E p [ Cov p ( λ , λ − β ) Var p ( λ ) ] , s_\beta(A) = \mathbb{E}_p\left[\frac{\operatorname{Cov}_p(\lambda,\lambda^\beta)}{\sqrt{\operatorname{Var}_p(\lambda)}}\right], \qquad s_{-\beta}(A) = -\mathbb{E}_p\left[\frac{\operatorname{Cov}_p(\lambda,\lambda^{-\beta})}{\sqrt{\operatorname{Var}_p(\lambda)}}\right], s β ( A ) = E p [ Var p ( λ ) Cov p ( λ , λ β ) ] , s − β ( A ) = − E p [ Var p ( λ ) Cov p ( λ , λ − β ) ] ,
and
S β ( A ) = d s β ( A ) tr ( A β ) + d s − β ( A ) tr ( A − β ) . (27) S_\beta(A) = \frac{d\,s_\beta(A)}{\operatorname{tr}(A^\beta)} + \frac{d\,s_{-\beta}(A)}{\operatorname{tr}(A^{-\beta})}. \tag*{(27)} S β ( A ) = tr ( A β ) d s β ( A ) + tr ( A − β ) d s − β ( A ) . (27)
Block masking controls the load
For each row i i i , exactly one entry of R t R_t R t is nonzero, so ∥ R t ∥ ∞ = 1 \|R_t\|_\infty= 1 ∥ R t ∥ ∞ = 1 . Fix a column j ∈ B r j \in B_r j ∈ B r . Only rows in B r ∖ { j } B_r \setminus\{j\} B r ∖ { j } can select column j j j , so the column has at most b − 1 b-1 b − 1 nonzeros. Therefore
∥ R t ∥ 1 ≤ b − 1 , ∥ R t ∥ o p ≤ ∥ R t ∥ 1 ∥ R t ∥ ∞ ≤ b − 1 . \|R_t\|_1 \le b-1, \qquad\|R_t\|_{\mathrm{op}} \le\sqrt{\|R_t\|_1\|R_t\|_\infty} \le\sqrt{b-1}. ∥ R t ∥ 1 ≤ b − 1 , ∥ R t ∥ op ≤ ∥ R t ∥ 1 ∥ R t ∥ ∞ ≤ b − 1 .
Taylor drift estimate
Lemma 5 (Taylor estimate). Let A ~ ≻ 0 \widetilde{A} \succ0 A ≻ 0 , R ∈ R d × d R \in\mathbb{R}^{d\times d} R ∈ R d × d , and
A ( s ) = ( I + s R ) ⊤ A ~ ( I + s R ) , f ( s ) = Φ β ( A ( s ) ) . A(s) = (I + sR)^\top\widetilde{A}(I + sR), \qquad f(s) = \Phi_\beta(A(s)). A ( s ) = ( I + s R ) ⊤ A ( I + s R ) , f ( s ) = Φ β ( A ( s )) . If β ≥ 1 \beta\ge1 β ≥ 1 and α ∥ R ∥ o p ≤ 1 / 2 \alpha\|R\|_{\mathrm{op}} \le1/2 α ∥ R ∥ op ≤ 1/2 , then
f ′ ( 0 ) = 2 ( tr ( R A ~ β ) tr ( A ~ β ) − tr ( R A ~ − β ) tr ( A ~ − β ) ) , f'(0) = 2\left(\frac{\operatorname{tr}(R\widetilde{A}^{\beta})}{\operatorname{tr}(\widetilde{A}^{\beta})} - \frac{\operatorname{tr}(R\widetilde{A}^{-\beta})}{\operatorname{tr}(\widetilde{A}^{-\beta})}\right), f ′ ( 0 ) = 2 ( tr ( A β ) tr ( R A β ) − tr ( A − β ) tr ( R A − β ) ) , and there is a universal constant C T a y C_{\mathrm{Tay}} C Tay such that, for every s ∈ [ 0 , α ] s \in[0,\alpha] s ∈ [ 0 , α ] ,
f ′ ′ ( s ) ≤ C T a y β ∥ R ∥ o p 2 . f''(s) \le C_{\mathrm{Tay}}\beta\|R\|_{\mathrm{op}}^2. f ′′ ( s ) ≤ C Tay β ∥ R ∥ op 2 . One may take C T a y = 40 C_{\mathrm{Tay}} = 40 C Tay = 40 .
Proof. Since
A ′ ( 0 ) = R T A ~ + A ~ R , A'(0)=R^{\mathsf{T}}\widetilde{A}+\widetilde{A}R, A ′ ( 0 ) = R T A + A R ,
the trace-power chain rule gives
d d s ∣ s = 0 1 β log tr ( A ( s ) β ) = tr ( A ~ β − 1 ( R T A ~ + A ~ R ) ) tr ( A ~ β ) . \left.\frac{d}{ds}\right|_{s=0}\frac{1}{\beta}\log\operatorname{tr}(A(s)^\beta)=\frac{\operatorname{tr}\left(\widetilde{A}^{\beta-1}\left(R^{\mathsf{T}}\widetilde{A}+\widetilde{A}R\right)\right)}{\operatorname{tr}(\widetilde{A}^{\beta})}. d s d s = 0 β 1 log tr ( A ( s ) β ) = tr ( A β ) tr ( A β − 1 ( R T A + A R ) ) .
By cyclicity of trace,
tr ( A ~ β − 1 ( R T A ~ + A ~ R ) ) = 2 tr ( R A ~ β ) . \operatorname{tr}\left(\widetilde{A}^{\beta-1}\left(R^{\mathsf{T}}\widetilde{A}+\widetilde{A}R\right)\right)=2\operatorname{tr}(R\widetilde{A}^{\beta}). tr ( A β − 1 ( R T A + A R ) ) = 2 tr ( R A β ) .
The negative-power term similarly gives
d d s ∣ s = 0 1 β log tr ( A ( s ) − β ) = − 2 tr ( R A ~ − β ) tr ( A ~ − β ) . \left.\frac{d}{ds}\right|_{s=0}\frac{1}{\beta}\log\operatorname{tr}(A(s)^{-\beta})=-2\frac{\operatorname{tr}(R\widetilde{A}^{-\beta})}{\operatorname{tr}(\widetilde{A}^{-\beta})}. d s d s = 0 β 1 log tr ( A ( s ) − β ) = − 2 tr ( A − β ) tr ( R A − β ) .
This proves the formula for f ′ ( 0 ) f'(0) f ′ ( 0 ) .
For the curvature bound, put
P s = I + s R , A s = P s T A ~ P s , C s = P s − 1 R . P_s=I+sR,\qquad A_s=P_s^{\mathsf{T}}\widetilde{A}P_s,\qquad C_s=P_s^{-1}R. P s = I + s R , A s = P s T A P s , C s = P s − 1 R .
For s ∈ [ 0 , α ] s\in[0,\alpha] s ∈ [ 0 , α ] , the assumption α ∥ R ∥ o p ≤ 1 / 2 \alpha\lVert R\rVert_{\mathrm{op}}\le1/2 α ∥ R ∥ op ≤ 1/2 implies
∥ P s − 1 ∥ o p ≤ 2 , ∥ C s ∥ o p ≤ 2 ∥ R ∥ o p . \lVert P_s^{-1}\rVert_{\mathrm{op}}\le2,\qquad\lVert C_s\rVert_{\mathrm{op}}\le2\lVert R\rVert_{\mathrm{op}}. ∥ P s − 1 ∥ op ≤ 2 , ∥ C s ∥ op ≤ 2 ∥ R ∥ op .
Moreover,
A ( s + t ) = ( I + t C s ) T A s ( I + t C s ) . A(s+t)=(I+tC_s)^{\mathsf{T}}A_s(I+tC_s). A ( s + t ) = ( I + t C s ) T A s ( I + t C s ) .
Let p = 2 β ≥ 2 p=2\beta\ge2 p = 2 β ≥ 2 . For the Schatten p p p -norm, the standard 2-smoothness estimate for N ( X ) = ∥ X ∥ p 2 N(X)=\lVert X\rVert_p^2 N ( X ) = ∥ X ∥ p 2 gives
D N ( X ) [ Y ] ≤ 2 ∥ X ∥ p ∥ Y ∥ p , D 2 N ( X ) [ Y , Y ] ≤ 2 ( p − 1 ) ∥ Y ∥ p 2 . DN(X)[Y]\le2\lVert X\rVert_p\lVert Y\rVert_p,\qquad D^2N(X)[Y,Y]\le2(p-1)\lVert Y\rVert_p^2. D N ( X ) [ Y ] ≤ 2 ∥ X ∥ p ∥ Y ∥ p , D 2 N ( X ) [ Y , Y ] ≤ 2 ( p − 1 ) ∥ Y ∥ p 2 .
Consequently, for a twice differentiable path X ( t ) X(t) X ( t ) ,
d 2 d t 2 log ∥ X ( t ) ∥ p 2 ≤ 2 ( p − 1 ) ∥ X ′ ( t ) ∥ p 2 ∥ X ( t ) ∥ p 2 + 2 ∥ X ′ ′ ( t ) ∥ p ∥ X ( t ) ∥ p . \frac{d^2}{dt^2}\log\lVert X(t)\rVert_p^2\le2(p-1)\frac{\lVert X'(t)\rVert_p^2}{\lVert X(t)\rVert_p^2}+2\frac{\lVert X''(t)\rVert_p}{\lVert X(t)\rVert_p}. d t 2 d 2 log ∥ X ( t ) ∥ p 2 ≤ 2 ( p − 1 ) ∥ X ( t ) ∥ p 2 ∥ X ′ ( t ) ∥ p 2 + 2 ∥ X ( t ) ∥ p ∥ X ′′ ( t ) ∥ p .
For the positive-power term, write
1 β log tr ( A ( s + t ) β ) = log ∥ A s 1 / 2 ( I + t C s ) ∥ 2 β 2 . \frac{1}{\beta}\log\operatorname{tr}(A(s+t)^\beta)=\log\left\lVert A_s^{1/2}(I+tC_s)\right\rVert_{2\beta}^2. β 1 log tr ( A ( s + t ) β ) = log A s 1/2 ( I + t C s ) 2 β 2 .
With X + ( t ) = A s 1 / 2 ( I + t C s ) X_+(t)=A_s^{1/2}(I+tC_s) X + ( t ) = A s 1/2 ( I + t C s ) , we have X + ′ ′ ( 0 ) = 0 X_+''(0)=0 X + ′′ ( 0 ) = 0 , and Schatten submultiplicativity gives
d 2 d t 2 ∣ t = 0 1 β log tr ( A ( s + t ) β ) ≤ ( 4 β − 2 ) ∥ C s ∥ o p 2 . \left.\frac{d^2}{dt^2}\right|_{t=0}\frac{1}{\beta}\log\operatorname{tr}(A(s+t)^\beta)\le(4\beta-2)\lVert C_s\rVert_{\mathrm{op}}^2. d t 2 d 2 t = 0 β 1 log tr ( A ( s + t ) β ) ≤ ( 4 β − 2 ) ∥ C s ∥ op 2 .
For the negative-power term,
A ( s + t ) − 1 = ( I + t C s ) − 1 A s − 1 ( I + t C s ) − T , A(s+t)^{-1}=(I+tC_s)^{-1}A_s^{-1}(I+tC_s)^{-\mathsf{T}}, A ( s + t ) − 1 = ( I + t C s ) − 1 A s − 1 ( I + t C s ) − T ,
so
1 β log tr ( A ( s + t ) − β ) = log ∥ ( I + t C s ) − 1 A s − 1 / 2 ∥ 2 β 2 . \frac{1}{\beta}\log\operatorname{tr}(A(s+t)^{-\beta})=\log\left\lVert(I+tC_s)^{-1}A_s^{-1/2}\right\rVert_{2\beta}^2. β 1 log tr ( A ( s + t ) − β ) = log ( I + t C s ) − 1 A s − 1/2 2 β 2 .
With X − ( t ) = ( I + t C s ) − 1 A s − 1 / 2 X_-(t)=(I+tC_s)^{-1}A_s^{-1/2} X − ( t ) = ( I + t C s ) − 1 A s − 1/2 ,
X − ′ ( 0 ) = − C s A s − 1 / 2 , X − ′ ′ ( 0 ) = 2 C s 2 A s − 1 / 2 , X_-'(0)=-C_sA_s^{-1/2},\qquad X_-''(0)=2C_s^2A_s^{-1/2}, X − ′ ( 0 ) = − C s A s − 1/2 , X − ′′ ( 0 ) = 2 C s 2 A s − 1/2 ,
and hence
d 2 d t 2 ∣ t = 0 1 β log tr ( A ( s + t ) − β ) ≤ 6 β ∥ C s ∥ o p 2 . \left.\frac{d^2}{dt^2}\right|_{t=0}\frac{1}{\beta}\log\operatorname{tr}(A(s+t)^{-\beta})\le6\beta\lVert C_s\rVert_{\mathrm{op}}^2. d t 2 d 2 t = 0 β 1 log tr ( A ( s + t ) − β ) ≤ 6 β ∥ C s ∥ op 2 .
Combining the two terms and using ∥ C s ∥ o p ≤ 2 ∥ R ∥ o p \lVert C_s\rVert_{\mathrm{op}}\le2\lVert R\rVert_{\mathrm{op}} ∥ C s ∥ op ≤ 2 ∥ R ∥ op yields
f ′ ′ ( s ) ≤ 40 β ∥ R ∥ o p 2 . f''(s)\le40\beta\lVert R\rVert_{\mathrm{op}}^2. f ′′ ( s ) ≤ 40 β ∥ R ∥ op 2 .
Applying Lemma 5 to one update and using ∥ R ∥ o p 2 ≤ b − 1 \lVert R\rVert_{\mathrm{op}}^2\le b-1 ∥ R ∥ op 2 ≤ b − 1 gives
Φ β ( A + ) ≤ Φ β ( A ) + 2 α ( tr ( R A ~ β ) tr ( A β ) − tr ( R A ~ − β ) tr ( A − β ) ) + C T a y α 2 β ( b − 1 ) , \Phi_\beta(A^+)\le\Phi_\beta(A)+2\alpha\left(\frac{\operatorname{tr}(R\widetilde{A}^{\beta})}{\operatorname{tr}(A^\beta)}-\frac{\operatorname{tr}(R\widetilde{A}^{-\beta})}{\operatorname{tr}(A^{-\beta})}\right)+C_{\mathrm{Tay}}\alpha^2\beta(b-1), Φ β ( A + ) ≤ Φ β ( A ) + 2 α ( tr ( A β ) tr ( R A β ) − tr ( A − β ) tr ( R A − β ) ) + C Tay α 2 β ( b − 1 ) ,
where tr ( A ~ ± β ) = tr ( A ± β ) \operatorname{tr}(\widetilde{A}^{\pm\beta})=\operatorname{tr}(A^{\pm\beta}) tr ( A ± β ) = tr ( A ± β ) by orthogonal invariance.
Block-local row-min drift
Lemma 6 (Haar row-min drift). For fixed A ≻ 0 A \succ0 A ≻ 0 , let Q ∼ Haar ( O ( d ) ) Q \sim\operatorname{Haar}(O(d)) Q ∼ Haar ( O ( d )) , A ~ = Q T A Q \widetilde{A} = Q^{\mathsf{T}}AQ A = Q T A Q , and let R R R be the block row-min selector. Then
E [ tr ( R A ~ β ) tr ( A β ) − tr ( R A ~ − β ) tr ( A − β ) ∣ A ] = − ν b , d d − 1 S β ( A ) . \mathbb{E}\left[\left.\frac{\operatorname{tr}(R\widetilde{A}^{\beta})}{\operatorname{tr}(A^{\beta})}-\frac{\operatorname{tr}(R\widetilde{A}^{-\beta})}{\operatorname{tr}(A^{-\beta})}\right| A\right] = -\frac{\nu_{b,d}}{\sqrt{d-1}}S_{\beta}(A). E [ tr ( A β ) tr ( R A β ) − tr ( A − β ) tr ( R A − β ) A ] = − d − 1 ν b , d S β ( A ) .
Proof. For any real γ \gamma γ , symmetry of A ~ γ \widetilde{A}^{\gamma} A γ gives
( R A ~ γ ) i i = ∑ j R i j ( A ~ γ ) j i = ( A ~ γ ) τ i i = ( A ~ γ ) i τ i . (R\widetilde{A}^{\gamma})_{ii}=\sum_j R_{ij}(\widetilde{A}^{\gamma})_{ji}=(\widetilde{A}^{\gamma})_{\tau_i i}=(\widetilde{A}^{\gamma})_{i\tau_i}. ( R A γ ) ii = j ∑ R ij ( A γ ) j i = ( A γ ) τ i i = ( A γ ) i τ i .
Thus
tr ( R A ~ γ ) = ∑ i = 1 d ( A ~ γ ) i τ i . \operatorname{tr}(R\widetilde{A}^{\gamma})=\sum_{i=1}^{d}(\widetilde{A}^{\gamma})_{i\tau_i}. tr ( R A γ ) = i = 1 ∑ d ( A γ ) i τ i .
It suffices to compute the one-row expectation. For each row, the candidate set has size b − 1 b-1 b − 1 and is independent of Q Q Q . By exchangeability of Haar coordinates, the one-row law depends only on this size. We analyze row 1 with a fixed candidate set J ⊂ [ d ] ∖ { 1 } J\subset[d]\setminus\{1\} J ⊂ [ d ] ∖ { 1 } , ∣ J ∣ = b − 1 |J|=b-1 ∣ J ∣ = b − 1 .
Let
x j = ( A ~ ) 1 j , ( y γ ) j = ( A ~ γ ) 1 j , j ≠ 1 , x_j=(\widetilde{A})_{1j},\qquad(y_{\gamma})_j=(\widetilde{A}^{\gamma})_{1j},\qquad j\ne1, x j = ( A ) 1 j , ( y γ ) j = ( A γ ) 1 j , j = 1 ,
and
τ = arg min j ∈ J x j . \tau=\underset{j\in J}{\arg\min}\ x_j. τ = j ∈ J arg min x j .
Then the row contribution is ( y γ ) τ (y_{\gamma})_{\tau} ( y γ ) τ .
Write A = V Λ V T A=V\Lambda V^{\mathsf{T}} A = V Λ V T and set U = Q T V U=Q^{\mathsf{T}}V U = Q T V . Then U ∼ Haar ( O ( d ) ) U\sim\operatorname{Haar}(O(d)) U ∼ Haar ( O ( d )) . Conditional on the first row u ∈ S d − 1 u\in S^{d-1} u ∈ S d − 1 of U U U , choose an orthonormal basis B ∈ R d × ( d − 1 ) B\in\mathbb{R}^{d\times(d-1)} B ∈ R d × ( d − 1 ) for u ⊥ u^{\perp} u ⊥ . The remaining rows of U U U form a Haar frame in u ⊥ u^{\perp} u ⊥ , so there is W ∼ Haar ( O ( d − 1 ) ) W\sim\operatorname{Haar}(O(d-1)) W ∼ Haar ( O ( d − 1 )) such that
x = a W T , y γ = c γ W T , a = u Λ B , c γ = u Λ γ B . x=aW^{\mathsf{T}},\qquad y_{\gamma}=c_{\gamma}W^{\mathsf{T}},\qquad a=u\Lambda B,\qquad c_{\gamma}=u\Lambda^{\gamma}B. x = a W T , y γ = c γ W T , a = u Λ B , c γ = u Λ γ B .
The vectors a , c γ a,c_{\gamma} a , c γ are deterministic after conditioning on u u u .
Assume first that ∥ a ∥ > 0 \lVert a\rVert>0 ∥ a ∥ > 0 . Decompose
c γ = ⟨ a , c γ ⟩ ∥ a ∥ 2 a + c γ ⊥ , c γ ⊥ ⊥ a . c_{\gamma}=\frac{\langle a,c_{\gamma}\rangle}{\lVert a\rVert^2}a+c_{\gamma}^{\perp},\qquad c_{\gamma}^{\perp}\perp a. c γ = ∥ a ∥ 2 ⟨ a , c γ ⟩ a + c γ ⊥ , c γ ⊥ ⊥ a .
Then
y γ = ⟨ a , c γ ⟩ ∥ a ∥ 2 x + c γ ⊥ W T . y_{\gamma}=\frac{\langle a,c_{\gamma}\rangle}{\lVert a\rVert^2}x+c_{\gamma}^{\perp}W^{\mathsf{T}}. y γ = ∥ a ∥ 2 ⟨ a , c γ ⟩ x + c γ ⊥ W T .
The index τ \tau τ is a function only of x = a W T x=aW^{\mathsf{T}} x = a W T . Conditional on x x x , the law of W W W is invariant under rotations fixing a a a . These rotations leave x x x , and hence τ \tau τ , unchanged, while they average the a ⊥ a^{\perp} a ⊥ -component to zero. Therefore
E [ ( c γ ⊥ W T ) τ ∣ a , c γ , J ] = 0 , \mathbb{E}\left[(c_{\gamma}^{\perp}W^{\mathsf{T}})_{\tau}\mid a,c_{\gamma},J\right]=0, E [ ( c γ ⊥ W T ) τ ∣ a , c γ , J ] = 0 ,
and
E [ ( y γ ) τ ∣ a , c γ , J ] = ⟨ a , c γ ⟩ ∥ a ∥ 2 E [ x τ ∣ a , J ] . \mathbb{E}\left[(y_{\gamma})_{\tau}\mid a,c_{\gamma},J\right]=\frac{\langle a,c_{\gamma}\rangle}{\lVert a\rVert^2}\mathbb{E}[x_{\tau}\mid a,J]. E [ ( y γ ) τ ∣ a , c γ , J ] = ∥ a ∥ 2 ⟨ a , c γ ⟩ E [ x τ ∣ a , J ] .
If ∥ a ∥ = 0 \lVert a\rVert=0 ∥ a ∥ = 0 , both sides are interpreted using the zero-ratio convention.
Since x = a W T = d ∥ a ∥ U x=aW^{\mathsf{T}}\mathrel{\overset{d}{=}}\lVert a\rVert U x = a W T = d ∥ a ∥ U , with U ∼ Unif ( S d − 2 ) U\sim\operatorname{Unif}(S^{d-2}) U ∼ Unif ( S d − 2 ) ,
E [ x τ ∣ a , J ] = − ν b , d d − 1 ∥ a ∥ . \mathbb{E}[x_{\tau}\mid a,J]=-\frac{\nu_{b,d}}{\sqrt{d-1}}\lVert a\rVert. E [ x τ ∣ a , J ] = − d − 1 ν b , d ∥ a ∥ .
Thus
E [ ( y γ ) τ ∣ a , c γ , J ] = − ν b , d d − 1 ⟨ a , c γ ⟩ ∥ a ∥ . \mathbb{E}\left[(y_{\gamma})_{\tau}\mid a,c_{\gamma},J\right]=-\frac{\nu_{b,d}}{\sqrt{d-1}}\frac{\langle a,c_{\gamma}\rangle}{\lVert a\rVert}. E [ ( y γ ) τ ∣ a , c γ , J ] = − d − 1 ν b , d ∥ a ∥ ⟨ a , c γ ⟩ .
Now average over u u u . If p i = u i 2 p_i=u_i^2 p i = u i 2 , then p ∼ Dir ( 1 / 2 , … , 1 / 2 ) p\sim\operatorname{Dir}(1/2,\ldots,1/2) p ∼ Dir ( 1/2 , … , 1/2 ) . Since B B T = I − u T u BB^{\mathsf{T}}=I-u^{\mathsf{T}}u B B T = I − u T u ,
∥ a ∥ 2 = u v a r : = ∑ i p i λ i 2 − ( ∑ i p i λ i ) 2 = Var p ( λ ) , \lVert a\rVert^2=u_{\mathrm{var}}:=\sum_i p_i\lambda_i^2-\left(\sum_i p_i\lambda_i\right)^2=\operatorname{Var}_p(\lambda), ∥ a ∥ 2 = u var := i ∑ p i λ i 2 − ( i ∑ p i λ i ) 2 = Var p ( λ ) ,
⟨ a , c β ⟩ = Cov p ( λ , λ β ) , ⟨ a , c − β ⟩ = Cov p ( λ , λ − β ) . \langle a,c_\beta\rangle=\operatorname{Cov}_p(\lambda,\lambda^\beta),\qquad\langle a,c_{-\beta}\rangle=\operatorname{Cov}_p(\lambda,\lambda^{-\beta}). ⟨ a , c β ⟩ = Cov p ( λ , λ β ) , ⟨ a , c − β ⟩ = Cov p ( λ , λ − β ) .
Therefore
E [ ( y β ) τ ∣ A ] = − ν b , d d − 1 s β ( A ) , \mathbb{E}[(y_\beta)_\tau\mid A]=-\frac{\nu_{b,d}}{\sqrt{d-1}}s_\beta(A), E [( y β ) τ ∣ A ] = − d − 1 ν b , d s β ( A ) ,
and
E [ ( y − β ) τ ∣ A ] = ν b , d d − 1 s − β ( A ) . \mathbb{E}[(y_{-\beta})_\tau\mid A]=\frac{\nu_{b,d}}{\sqrt{d-1}}s_{-\beta}(A). E [( y − β ) τ ∣ A ] = d − 1 ν b , d s − β ( A ) .
Summing over the d d d rows gives
E [ tr ( R A ~ β ) ∣ A ] = − ν b , d d − 1 d s β ( A ) , \mathbb{E}[\operatorname{tr}(R\widetilde{A}^{\beta})\mid A]=-\frac{\nu_{b,d}}{\sqrt{d-1}}d\,s_\beta(A), E [ tr ( R A β ) ∣ A ] = − d − 1 ν b , d d s β ( A ) ,
E [ tr ( R A ~ − β ) ∣ A ] = ν b , d d − 1 d s − β ( A ) . \mathbb{E}[\operatorname{tr}(R\widetilde{A}^{-\beta})\mid A]=\frac{\nu_{b,d}}{\sqrt{d-1}}d\,s_{-\beta}(A). E [ tr ( R A − β ) ∣ A ] = d − 1 ν b , d d s − β ( A ) .
Dividing by the deterministic traces yields the claimed identity.
Lower bound on the spectral factor
Lemma 7 (Spectral lower bound). Let κ ⋆ > 1 \kappa_\star>1 κ ⋆ > 1 , and define
ρ κ ⋆ = max { 1 − 1 − κ ⋆ − 1 4 , ( 1 + κ ⋆ − 1 4 ) − 1 } . \rho_{\kappa_\star}=\max\left\{1-\frac{1-\kappa_\star^{-1}}{4},\left(1+\frac{\kappa_\star-1}{4}\right)^{-1}\right\}. ρ κ ⋆ = max { 1 − 4 1 − κ ⋆ − 1 , ( 1 + 4 κ ⋆ − 1 ) − 1 } . If κ ( A ) ≥ κ ⋆ \kappa(A)\ge\kappa_\star κ ( A ) ≥ κ ⋆ and
β ≥ log ( 8 d ) − log ρ κ ⋆ , \beta\ge\frac{\log(8d)}{-\log\rho_{\kappa_\star}}, β ≥ − log ρ κ ⋆ log ( 8 d ) , then
S β ( A ) ≥ 1 4 . S_\beta(A)\ge\frac{1}{4}. S β ( A ) ≥ 4 1 .
Proof. By scale invariance, set λ min = 1 \lambda_{\min}=1 λ m i n = 1 , λ max = κ ≥ κ ⋆ \lambda_{\max}=\kappa\ge\kappa_\star λ m a x = κ ≥ κ ⋆ , and Δ = κ − 1 \Delta=\kappa-1 Δ = κ − 1 . Define
μ + = ∑ i λ i β + 1 ∑ i λ i β , μ − = ∑ i λ i 1 − β ∑ i λ i − β , λ ˉ = 1 d ∑ i λ i . \mu_+=\frac{\sum_i\lambda_i^{\beta+1}}{\sum_i\lambda_i^\beta},\qquad
\mu_-=\frac{\sum_i\lambda_i^{1-\beta}}{\sum_i\lambda_i^{-\beta}},\qquad
\bar{\lambda}=\frac{1}{d}\sum_i\lambda_i. μ + = ∑ i λ i β ∑ i λ i β + 1 , μ − = ∑ i λ i − β ∑ i λ i 1 − β , λ ˉ = d 1 i ∑ λ i .
Since λ i ∈ [ 1 , κ ] \lambda_i\in[1,\kappa] λ i ∈ [ 1 , κ ] ,
Var p ( λ ) ≤ Δ 2 4 . \operatorname{Var}_p(\lambda)\le\frac{\Delta^2}{4}. Var p ( λ ) ≤ 4 Δ 2 .
Monotonicity gives Cov p ( λ , λ β ) ≥ 0 \operatorname{Cov}_p(\lambda,\lambda^\beta)\ge0 Cov p ( λ , λ β ) ≥ 0 and − Cov p ( λ , λ − β ) ≥ 0 -\operatorname{Cov}_p(\lambda,\lambda^{-\beta})\ge0 − Cov p ( λ , λ − β ) ≥ 0 . Hence
s β ≥ 2 Δ E p [ Cov p ( λ , λ β ) ] , s − β ≥ 2 Δ E p [ − Cov p ( λ , λ − β ) ] . s_\beta\ge\frac{2}{\Delta}\mathbb{E}_p[\operatorname{Cov}_p(\lambda,\lambda^\beta)],\qquad
s_{-\beta}\ge\frac{2}{\Delta}\mathbb{E}_p[-\operatorname{Cov}_p(\lambda,\lambda^{-\beta})]. s β ≥ Δ 2 E p [ Cov p ( λ , λ β )] , s − β ≥ Δ 2 E p [ − Cov p ( λ , λ − β )] .
For p ∼ Dir ( 1 / 2 , … , 1 / 2 ) p\sim\operatorname{Dir}(1/2,\ldots,1/2) p ∼ Dir ( 1/2 , … , 1/2 ) ,
E p [ Cov p ( u , v ) ] = d ∑ i u i v i − ( ∑ i u i ) ( ∑ i v i ) d ( d + 2 ) . \mathbb{E}_p[\operatorname{Cov}_p(u,v)]=\frac{d\sum_i u_iv_i-(\sum_i u_i)(\sum_i v_i)}{d(d+2)}. E p [ Cov p ( u , v )] = d ( d + 2 ) d ∑ i u i v i − ( ∑ i u i ) ( ∑ i v i ) .
Applying this identity gives
E p [ Cov p ( λ , λ β ) ] = tr ( A β ) d + 2 ( μ + − λ ˉ ) , \mathbb{E}_p[\operatorname{Cov}_p(\lambda,\lambda^\beta)]
=\frac{\operatorname{tr}(A^\beta)}{d+2}(\mu_+-\bar{\lambda}), E p [ Cov p ( λ , λ β )] = d + 2 tr ( A β ) ( μ + − λ ˉ ) ,
E p [ − Cov p ( λ , λ − β ) ] = tr ( A − β ) d + 2 ( λ ˉ − μ − ) . \mathbb{E}_p[-\operatorname{Cov}_p(\lambda,\lambda^{-\beta})]
=\frac{\operatorname{tr}(A^{-\beta})}{d+2}(\bar{\lambda}-\mu_-). E p [ − Cov p ( λ , λ − β )] = d + 2 tr ( A − β ) ( λ ˉ − μ − ) .
Therefore
S β ( A ) ≥ 2 d Δ ( d + 2 ) ( μ + − μ − ) ≥ μ + − μ − Δ . S_\beta(A) \ge\frac{2d}{\Delta(d+2)}(\mu_+-\mu_-) \ge\frac{\mu_+-\mu_-}{\Delta}. S β ( A ) ≥ Δ ( d + 2 ) 2 d ( μ + − μ − ) ≥ Δ μ + − μ − .
It remains to show μ + − μ − ≥ Δ / 4 \mu_+-\mu_- \ge\Delta/4 μ + − μ − ≥ Δ/4 . Let
r = 1 + Δ 4 , s = κ − Δ 4 . r=1+\frac{\Delta}{4}, \qquad s=\kappa-\frac{\Delta}{4}. r = 1 + 4 Δ , s = κ − 4 Δ .
Then s − r = Δ / 2 s-r=\Delta/2 s − r = Δ/2 . Let
W + = ∑ λ i < s λ i β ∑ i λ i β . W_+=\frac{\sum_{\lambda_i<s}\lambda_i^\beta}{\sum_i\lambda_i^\beta}. W + = ∑ i λ i β ∑ λ i < s λ i β .
Since at least one eigenvalue equals κ \kappa κ ,
W + ≤ d ( s κ ) β ≤ d ρ κ ⋆ β ≤ 1 8 . W_+\le d\left(\frac{s}{\kappa}\right)^\beta\le d\rho_{\kappa_\star}^\beta\le\frac{1}{8}. W + ≤ d ( κ s ) β ≤ d ρ κ ⋆ β ≤ 8 1 .
Therefore
μ + ≥ s − ( s − 1 ) W + ≥ s − 3 Δ 32 . \mu_+\ge s-(s-1)W_+\ge s-\frac{3\Delta}{32}. μ + ≥ s − ( s − 1 ) W + ≥ s − 32 3Δ .
Similarly, with
W − = ∑ λ i > r λ i − β ∑ i λ i − β , W_-=\frac{\sum_{\lambda_i>r}\lambda_i^{-\beta}}{\sum_i\lambda_i^{-\beta}}, W − = ∑ i λ i − β ∑ λ i > r λ i − β ,
one has
W − ≤ d r − β ≤ d ρ κ ⋆ β ≤ 1 8 , W_-\le dr^{-\beta}\le d\rho_{\kappa_\star}^\beta\le\frac{1}{8}, W − ≤ d r − β ≤ d ρ κ ⋆ β ≤ 8 1 ,
and hence
μ − ≤ r + ( κ − r ) W − ≤ r + 3 Δ 32 . \mu_-\le r+(\kappa-r)W_-\le r+\frac{3\Delta}{32}. μ − ≤ r + ( κ − r ) W − ≤ r + 32 3Δ .
Thus
μ + − μ − ≥ ( s − r ) − 6 Δ 32 = 5 Δ 16 ≥ Δ 4 . \mu_+-\mu_-\ge(s-r)-\frac{6\Delta}{32}=\frac{5\Delta}{16}\ge\frac{\Delta}{4}. μ + − μ − ≥ ( s − r ) − 32 6Δ = 16 5Δ ≥ 4 Δ .
The lemma follows.
Hitting-time bound
For t < τ κ ⋆ t<\tau_{\kappa_\star} t < τ κ ⋆ , Lemma 7 gives S β ( A t ) ≥ 1 / 4 S_\beta(A_t)\ge1/4 S β ( A t ) ≥ 1/4 . Combining Lemma 6 with the Taylor estimate gives
E [ Φ β ( A t + 1 ) − Φ β ( A t ) ∣ A t ] ≤ − α ν b , d 2 d − 1 + C T a y α 2 β ( b − 1 ) . \mathbb{E}[\Phi_\beta(A_{t+1})-\Phi_\beta(A_t)\mid A_t]\le-\frac{\alpha\nu_{b,d}}{2\sqrt{d-1}}+C_{\mathrm{Tay}}\alpha^2\beta(b-1). E [ Φ β ( A t + 1 ) − Φ β ( A t ) ∣ A t ] ≤ − 2 d − 1 α ν b , d + C Tay α 2 β ( b − 1 ) .
Choose
α = ν b , d 8 C T a y β ( b − 1 ) d − 1 , \alpha=\frac{\nu_{b,d}}{8C_{\mathrm{Tay}}\beta(b-1)\sqrt{d-1}}, α = 8 C Tay β ( b − 1 ) d − 1 ν b , d ,
and enlarge the universal constant in Theorem 4, if necessary, to ensure α ∥ R t ∥ o p ≤ 1 / 2 \alpha\lVert R_t\rVert_{\mathrm{op}}\le1/2 α ∥ R t ∥ op ≤ 1/2 . Then
E [ Φ β ( A t + 1 ) − Φ β ( A t ) ∣ A t ] ≤ − δ , δ = 3 ν b , d 2 64 C T a y β ( b − 1 ) ( d − 1 ) . \mathbb{E}[\Phi_\beta(A_{t+1})-\Phi_\beta(A_t)\mid A_t]\le-\delta,\qquad
\delta=\frac{3\nu_{b,d}^2}{64C_{\mathrm{Tay}}\beta(b-1)(d-1)}. E [ Φ β ( A t + 1 ) − Φ β ( A t ) ∣ A t ] ≤ − δ , δ = 64 C Tay β ( b − 1 ) ( d − 1 ) 3 ν b , d 2 .
Therefore
Φ β ( A t ∧ τ κ ⋆ ) + δ ( t ∧ τ κ ⋆ ) \Phi_\beta(A_{t\wedge\tau_{\kappa_\star}})+\delta(t\wedge\tau_{\kappa_\star}) Φ β ( A t ∧ τ κ ⋆ ) + δ ( t ∧ τ κ ⋆ )
is a supermartingale. Since Φ β ≥ 0 \Phi_\beta\ge0 Φ β ≥ 0 , optional stopping gives
E [ t ∧ τ κ ⋆ ] ≤ Φ β ( A 0 ) δ . \mathbb{E}[t\wedge\tau_{\kappa_\star}]\le\frac{\Phi_\beta(A_0)}{\delta}. E [ t ∧ τ κ ⋆ ] ≤ δ Φ β ( A 0 ) .
Letting t → ∞ t\to\infty t → ∞ and using Φ β ( A 0 ) ≤ log κ ( A 0 ) \Phi_\beta(A_0)\le\log\kappa(A_0) Φ β ( A 0 ) ≤ log κ ( A 0 ) yields
E [ τ κ ⋆ ] ≤ C β ( b − 1 ) ( d − 1 ) ν b , d 2 log κ ( A 0 ) . \mathbb{E}[\tau_{\kappa_\star}]\le C\frac{\beta(b-1)(d-1)}{\nu_{b,d}^2}\log\kappa(A_0). E [ τ κ ⋆ ] ≤ C ν b , d 2 β ( b − 1 ) ( d − 1 ) log κ ( A 0 ) .
It remains to record the fixed-block behavior of ν b , d \nu_{b,d} ν b , d . Since b − 1 ≥ 2 b-1 \ge2 b − 1 ≥ 2 ,
− E min 1 ≤ r ≤ b − 1 U r ≥ − E min ( U 1 , U 2 ) = 1 2 E ∣ U 1 − U 2 ∣ . -\mathbb{E}\min_{1\le r\le b-1} U_r \ge-\mathbb{E}\min(U_1,U_2) = \frac{1}{2}\mathbb{E}|U_1-U_2|. − E 1 ≤ r ≤ b − 1 min U r ≥ − E min ( U 1 , U 2 ) = 2 1 E ∣ U 1 − U 2 ∣.
By rotational invariance, U 1 − U 2 = d 2 U 1 U_1-U_2 \overset{d}{=} \sqrt{2}U_1 U 1 − U 2 = d 2 U 1 , so
ν b , d ≥ d − 1 2 E ∣ U 1 ∣ . \nu_{b,d} \ge\sqrt{\frac{d-1}{2}}\mathbb{E}|U_1|. ν b , d ≥ 2 d − 1 E ∣ U 1 ∣.
For U ∼ Unif ( S d − 2 ) U \sim\operatorname{Unif}(S^{d-2}) U ∼ Unif ( S d − 2 ) ,
E ∣ U 1 ∣ = Γ ( ( d − 1 ) / 2 ) π Γ ( d / 2 ) , \mathbb{E}|U_1| = \frac{\Gamma((d-1)/2)}{\sqrt{\pi}\Gamma(d/2)}, E ∣ U 1 ∣ = π Γ ( d /2 ) Γ (( d − 1 ) /2 ) ,
which gives a positive lower bound uniformly in d d d . Conversely,
− min 1 ≤ r ≤ b − 1 U r ≤ max 1 ≤ r ≤ b − 1 ∣ U r ∣ ≤ ( ∑ r = 1 b − 1 U r 2 ) 1 / 2 . -\min_{1\le r\le b-1} U_r \le\max_{1\le r\le b-1}|U_r| \le\left(\sum_{r=1}^{b-1}U_r^2\right)^{1/2}. − 1 ≤ r ≤ b − 1 min U r ≤ 1 ≤ r ≤ b − 1 max ∣ U r ∣ ≤ ( r = 1 ∑ b − 1 U r 2 ) 1/2 .
Thus, by Jensen,
ν b , d ≤ d − 1 ( E ∑ r = 1 b − 1 U r 2 ) 1 / 2 = b − 1 . \nu_{b,d} \le\sqrt{d-1}\left(\mathbb{E}\sum_{r=1}^{b-1}U_r^2\right)^{1/2} = \sqrt{b-1}. ν b , d ≤ d − 1 ( E r = 1 ∑ b − 1 U r 2 ) 1/2 = b − 1 .
Hence ν b , d 2 = Θ b ( 1 ) \nu_{b,d}^2=\Theta_b(1) ν b , d 2 = Θ b ( 1 ) for fixed b b b . Since β = O κ ⋆ ( log d ) \beta=O_{\kappa_\star}(\log d) β = O κ ⋆ ( log d ) , Theorem 4 follows.
Fast structured mixing and the required transfer condition
Dense Haar mixing is the clean object for analysis, but it is not the intended implementation for large matrices. Sampling and applying a dense Haar matrix costs cubic time at the scale of a dense d × d d \times d d × d Gram matrix. A much faster alternative is to use a product of normalized Walsh-Hadamard transforms and random sign diagonals. Let W d W_d W d denote the normalized Walsh-Hadamard matrix, and let D 1 , … , D k D_1,\ldots,D_k D 1 , … , D k be independent diagonal matrices with Rademacher entries. A typical fast mixer is
Q F H T = Π W d D k W d D k − 1 ⋯ W d D 1 , Q_{\mathrm{FHT}}=\Pi W_dD_kW_dD_{k-1}\cdots W_dD_1, Q FHT = Π W d D k W d D k − 1 ⋯ W d D 1 ,
where Π \Pi Π is an independent random permutation. Each factor is orthogonal, and multiplication by W d W_d W d can be performed with the fast Hadamard transform. Thus forming Q F H T T A Q F H T Q_{\mathrm{FHT}}^{\mathsf T}AQ_{\mathrm{FHT}} Q FHT T A Q FHT for dense A A A costs O ( k d 2 log d ) O(kd^2\log d) O ( k d 2 log d ) , rather than the dense-rotation cost. The sparse row-min update then costs O ( d 2 ) O(d^2) O ( d 2 ) , and the block row-min search costs O ( d b ) O(db) O ( d b ) once the relevant entries of A ~ \widetilde{A} A are available.
The theorem above does not automatically apply to Q F H T Q_{\mathrm{FHT}} Q FHT . Haar mixing supplies exact conditional rotational invariance, which is used in the row-min drift lemma. A finite product of Hadamard/sign factors is a structured discrete distribution and need not have that exact invariance. A single Hadamard-sign layer is certainly insufficient in the worst case: if Q = W d D Q=W_dD Q = W d D and A = W d Λ W d T A=W_d\Lambda W_d^{\mathsf T} A = W d Λ W d T , then Q T A Q = D Λ D = Λ Q^{\mathsf T}AQ=D\Lambda D=\Lambda Q T A Q = D Λ D = Λ , so the mixed matrix is diagonal and the row-min signal vanishes. Multiple layers and a random permutation are used to avoid such alignment effects. This worst-case observation does not contradict the empirical effectiveness of a single mixing stage per RAPID iteration (k = 1 k=1 k = 1 ), since successive iterations introduce fresh mixing interleaved with sparse corrections, allowing the effects of mixing to accumulate over time.
The rest of the proof, however, is insensitive to the source of orthogonal mixing. The Taylor expansion, trace invariance, load bound, spectral lower bound, and stopping-time argument all hold for any orthogonal distribution. The only missing ingredient is a local row-min comparison estimate. We state it explicitly.
For an orthogonal mixing distribution Q \mathcal{Q} Q , define, for a fixed row i i i , block candidate set J i \mathcal{J}_i J i , and exponent γ ∈ { β , − β } \gamma\in\{\beta,-\beta\} γ ∈ { β , − β } ,
x j = ( Q T A Q ) i j , y j ( γ ) = ( ( Q T A Q ) γ ) i j , j ∈ J i , x_j=(Q^{\mathsf T}AQ)_{ij},\qquad y_j^{(\gamma)}=((Q^{\mathsf T}AQ)^\gamma)_{ij},\qquad j\in\mathcal{J}_i, x j = ( Q T A Q ) ij , y j ( γ ) = (( Q T A Q ) γ ) ij , j ∈ J i ,
and
τ i = arg min j ∈ J i x j . \tau_i=\arg\min_{j\in\mathcal{J}_i}x_j. τ i = arg j ∈ J i min x j .
Let
F i , J i ( γ ) ( Q , A ) : = y τ i ( γ ) . F^{(\gamma)}_{i,J_i}(Q,A) := y^{(\gamma)}_{\tau_i}. F i , J i ( γ ) ( Q , A ) := y τ i ( γ ) .
Define the local Haar-comparison errors
δ Q , γ ( A ) : = max i ∣ E Q ∼ Q F i , J i ( γ ) ( Q , A ) − E Q ∼ H a a r F i , J i ( γ ) ( Q , A ) ∣ , \delta_{Q,\gamma}(A) := \max_i \left|\mathbb{E}_{Q\sim Q}F^{(\gamma)}_{i,J_i}(Q,A)-\mathbb{E}_{Q\sim\mathrm{Haar}}F^{(\gamma)}_{i,J_i}(Q,A)\right|, δ Q , γ ( A ) := i max E Q ∼ Q F i , J i ( γ ) ( Q , A ) − E Q ∼ Haar F i , J i ( γ ) ( Q , A ) ,
and the normalized error
ε Q , β ( A ) : = d δ Q , β ( A ) tr ( A β ) + d δ Q , − β ( A ) tr ( A − β ) . \varepsilon_{Q,\beta}(A) := \frac{d\,\delta_{Q,\beta}(A)}{\operatorname{tr}(A^\beta)}+\frac{d\,\delta_{Q,-\beta}(A)}{\operatorname{tr}(A^{-\beta})}. ε Q , β ( A ) := tr ( A β ) d δ Q , β ( A ) + tr ( A − β ) d δ Q , − β ( A ) .
Proposition 8 (Transfer from Haar to a structured orthogonal mixer). Let Q Q Q be any distribution on O ( d ) O(d) O ( d ) . Suppose that for every A ≻ 0 A \succ0 A ≻ 0 with κ ( A ) ≥ κ ⋆ \kappa(A) \ge\kappa_\star κ ( A ) ≥ κ ⋆ ,
ε Q , β ( A ) ≤ ν b , d 8 d − 1 . \varepsilon_{Q,\beta}(A) \le\frac{\nu_{b,d}}{8\sqrt{d}-1}. ε Q , β ( A ) ≤ 8 d − 1 ν b , d . Then the block row-min iteration with Q t ∼ Q Q_t \sim Q Q t ∼ Q satisfies the same hitting-time guarantee as Theorem 4 , up to universal constant factors:
E [ τ κ ⋆ ] ≤ C β ( b − 1 ) ( d − 1 ) ν b , d 2 log κ ( A 0 ) . \mathbb{E}[\tau_{\kappa_\star}] \le C\frac{\beta(b-1)(d-1)}{\nu_{b,d}^{2}}\log\kappa(A_0). E [ τ κ ⋆ ] ≤ C ν b , d 2 β ( b − 1 ) ( d − 1 ) log κ ( A 0 ) .
Proof. The Haar drift identity gives
D H a a r ( A ) : = E H a a r [ ( tr ( R A ~ β ) tr ( A β ) − tr ( R A ~ − β ) tr ( A − β ) ) | A ] = − ν b , d d − 1 S β ( A ) . D_{\mathrm{Haar}}(A):=\mathbb{E}_{\mathrm{Haar}}\left[\left(\frac{\operatorname{tr}(R\widetilde{A}^{\beta})}{\operatorname{tr}(A^\beta)}-\frac{\operatorname{tr}(R\widetilde{A}^{-\beta})}{\operatorname{tr}(A^{-\beta})}\right)\middle|A\right]=-\frac{\nu_{b,d}}{\sqrt{d}-1}S_\beta(A). D Haar ( A ) := E Haar [ ( tr ( A β ) tr ( R A β ) − tr ( A − β ) tr ( R A − β ) ) A ] = − d − 1 ν b , d S β ( A ) .
By the definition of ε Q , β \varepsilon_{Q,\beta} ε Q , β , the corresponding drift under Q ∼ Q Q\sim Q Q ∼ Q satisfies
D Q ( A ) ≤ D H a a r ( A ) + ε Q , β ( A ) . D_Q(A)\le D_{\mathrm{Haar}}(A)+\varepsilon_{Q,\beta}(A). D Q ( A ) ≤ D Haar ( A ) + ε Q , β ( A ) .
If κ ( A ) ≥ κ ⋆ \kappa(A)\ge\kappa_\star κ ( A ) ≥ κ ⋆ , then S β ( A ) ≥ 1 / 4 S_\beta(A)\ge1/4 S β ( A ) ≥ 1/4 , and the assumed comparison bound gives
D Q ( A ) ≤ − ν b , d 4 d − 1 + ν b , d 8 d − 1 = − ν b , d 8 d − 1 . D_Q(A)\le-\frac{\nu_{b,d}}{4\sqrt{d}-1}+\frac{\nu_{b,d}}{8\sqrt{d}-1}=-\frac{\nu_{b,d}}{8\sqrt{d}-1}. D Q ( A ) ≤ − 4 d − 1 ν b , d + 8 d − 1 ν b , d = − 8 d − 1 ν b , d .
Substituting this into the same Taylor estimate used in the Haar proof yields
E [ Φ β ( A t + 1 ) − Φ β ( A t ) ∣ A t ] ≤ − α ν b , d 4 d − 1 + C T a y α 2 β ( b − 1 ) \mathbb{E}[\Phi_\beta(A_{t+1})-\Phi_\beta(A_t)\mid A_t]\le-\frac{\alpha\nu_{b,d}}{4\sqrt{d}-1}+C_{\mathrm{Tay}}\alpha^2\beta(b-1) E [ Φ β ( A t + 1 ) − Φ β ( A t ) ∣ A t ] ≤ − 4 d − 1 α ν b , d + C Tay α 2 β ( b − 1 )
until τ κ ⋆ \tau_{\kappa_\star} τ κ ⋆ . Choosing α ≍ ν b , d / ( β ( b − 1 ) d − 1 ) \alpha\asymp\nu_{b,d}/(\beta(b-1)\sqrt{d}-1) α ≍ ν b , d / ( β ( b − 1 ) d − 1 ) and applying the same optional-stopping argument proves the claim. □ \square □
Proposition 8 is stated as a local comparison condition, not as a new convergence theorem for fast Hadamard products. Proving the condition for Q F H T Q_{\mathrm{FHT}} Q FHT requires showing that the hard row-min statistic F i , J i ( γ ) F^{(\gamma)}_{i,J_i} F i , J i ( γ ) has nearly the same expectation under the structured mixer as under Haar. This is the precise theoretical gap left by replacing continuous Haar rotations with fast structured orthogonal transforms. Existing incoherence and fast Johnson–Lindenstrauss results for randomized Hadamard transforms suggest why such a comparison should be plausible after several independent sign/Hadamard layers, but they do not by themselves supply the conditional rotational invariance used in the Haar proof. Empirically, we therefore use the fast Hadamard mixer for scalability, while the theorem above gives the exact guarantee for Haar mixing and identifies the comparison estimate needed to transfer the guarantee to the fast implementation.
Spiky spectra give a d \sqrt{d} d drift gain
In the worst-case argument above we only used the uniform lower bound
S β ( A ) ≥ c κ ⋆ > 0 whenever κ ( A ) ≥ κ ⋆ . S_\beta(A)\ge c_{\kappa_\star}>0\qquad\text{whenever}\qquad\kappa(A)\ge\kappa_\star. S β ( A ) ≥ c κ ⋆ > 0 whenever κ ( A ) ≥ κ ⋆ .
For spiky spectra, S β ( A ) S_\beta(A) S β ( A ) can be much larger. We record the simplest case, where the spectrum consists of one large spike and a flat bulk.
Lemma 9 (Rank-one spike). Assume, after rescaling, that
λ 1 = κ , λ 2 = ⋯ = λ d = 1 , κ > 1. \lambda_1=\kappa,\qquad\lambda_2=\cdots=\lambda_d=1,\qquad\kappa>1. λ 1 = κ , λ 2 = ⋯ = λ d = 1 , κ > 1. Let
M = κ β . M=\kappa^\beta. M = κ β . Then
S β ( A ) = d A d [ M − 1 M + d − 1 + 1 − M − 1 M − 1 + d − 1 ] . S_\beta(A)=dA_d\left[\frac{M-1}{M+d-1}+\frac{1-M^{-1}}{M^{-1}+d-1}\right]. S β ( A ) = d A d [ M + d − 1 M − 1 + M − 1 + d − 1 1 − M − 1 ] . where
A d = E q ( 1 − q ) , q ∼ Beta ( 1 2 , d − 1 2 ) . A_d=\mathbb{E}\sqrt{q(1-q)},\qquad q\sim\operatorname{Beta}\left(\frac{1}{2},\frac{d-1}{2}\right). A d = E q ( 1 − q ) , q ∼ Beta ( 2 1 , 2 d − 1 ) . Moreover,
A d = 2 d Γ ( d / 2 ) π Γ ( ( d − 1 ) / 2 ) = Θ ( d − 1 / 2 ) . A_d=\frac{2}{d}\frac{\Gamma(d/2)}{\sqrt{\pi}\Gamma((d-1)/2)}=\Theta(d^{-1/2}). A d = d 2 π Γ (( d − 1 ) /2 ) Γ ( d /2 ) = Θ ( d − 1/2 ) . Consequently, if
κ β ≥ 2 d , \kappa^\beta\ge2d, κ β ≥ 2 d , then
S β ( A ) ≥ c d S_\beta(A)\ge c\sqrt{d} S β ( A ) ≥ c d for a universal numerical constant c > 0 c>0 c > 0 . In fact, in this regime,
S β ( A ) = Θ ( d ) . S_\beta(A)=\Theta(\sqrt{d}). S β ( A ) = Θ ( d ) .
Proof. Let
p ∼ Dir ( 1 2 , … , 1 2 ) , q = p 1 . p\sim\operatorname{Dir}\left(\frac{1}{2},\ldots,\frac{1}{2}\right),\qquad q=p_1. p ∼ Dir ( 2 1 , … , 2 1 ) , q = p 1 .
For the rank-one spike,
λ i = 1 + ( κ − 1 ) 1 { i = 1 } . \lambda_i=1+(\kappa-1)1_{\{i=1\}}. λ i = 1 + ( κ − 1 ) 1 { i = 1 } .
Set
Δ = κ − 1. \Delta=\kappa-1. Δ = κ − 1.
Then
λ i β = 1 + ( M − 1 ) 1 { i = 1 } , λ i − β = 1 + ( M − 1 − 1 ) 1 { i = 1 } . \lambda_i^\beta=1+(M-1)1_{\{i=1\}},\qquad\lambda_i^{-\beta}=1+(M^{-1}-1)1_{\{i=1\}}. λ i β = 1 + ( M − 1 ) 1 { i = 1 } , λ i − β = 1 + ( M − 1 − 1 ) 1 { i = 1 } .
A direct calculation gives
Var p ( λ ) = Δ 2 q ( 1 − q ) , \operatorname{Var}_p(\lambda)=\Delta^2q(1-q), Var p ( λ ) = Δ 2 q ( 1 − q ) ,
Cov p ( λ , λ β ) = Δ ( M − 1 ) q ( 1 − q ) , \operatorname{Cov}_p(\lambda,\lambda^\beta)=\Delta(M-1)q(1-q), Cov p ( λ , λ β ) = Δ ( M − 1 ) q ( 1 − q ) ,
− Cov p ( λ , λ − β ) = Δ ( 1 − M − 1 ) q ( 1 − q ) . -\operatorname{Cov}_p(\lambda,\lambda^{-\beta})=\Delta(1-M^{-1})q(1-q). − Cov p ( λ , λ − β ) = Δ ( 1 − M − 1 ) q ( 1 − q ) .
Therefore, using the zero-ratio convention when Var p ( λ ) = 0 \operatorname{Var}_p(\lambda)=0 Var p ( λ ) = 0 ,
s β ( A ) = ( M − 1 ) E q ( 1 − q ) , s_\beta(A)=(M-1)\mathbb{E}\sqrt{q(1-q)}, s β ( A ) = ( M − 1 ) E q ( 1 − q ) ,
s − β ( A ) = ( 1 − M − 1 ) E q ( 1 − q ) . s_{-\beta}(A)=(1-M^{-1})\mathbb{E}\sqrt{q(1-q)}. s − β ( A ) = ( 1 − M − 1 ) E q ( 1 − q ) .
Writing
A d : = E q ( 1 − q ) , A_d:=\mathbb{E}\sqrt{q(1-q)}, A d := E q ( 1 − q ) ,
we have
s β ( A ) = ( M − 1 ) A d , s − β ( A ) = ( 1 − M − 1 ) A d . s_\beta(A)=(M-1)A_d,\qquad s_{-\beta}(A)=(1-M^{-1})A_d. s β ( A ) = ( M − 1 ) A d , s − β ( A ) = ( 1 − M − 1 ) A d .
Also,
tr ( A β ) = M + d − 1 , tr ( A − β ) = M − 1 + d − 1. \operatorname{tr}(A^\beta)=M+d-1,\qquad\operatorname{tr}(A^{-\beta})=M^{-1}+d-1. tr ( A β ) = M + d − 1 , tr ( A − β ) = M − 1 + d − 1.
Hence
S β ( A ) = d s β ( A ) tr ( A β ) + d s − β ( A ) tr ( A − β ) S_\beta(A)=\frac{d\,s_\beta(A)}{\operatorname{tr}(A^\beta)}+\frac{d\,s_{-\beta}(A)}{\operatorname{tr}(A^{-\beta})} S β ( A ) = tr ( A β ) d s β ( A ) + tr ( A − β ) d s − β ( A )
equals
d A d [ M − 1 M + d − 1 + 1 − M − 1 M − 1 + d − 1 ] . (28) dA_d\left[\frac{M-1}{M+d-1}+\frac{1-M^{-1}}{M^{-1}+d-1}\right]. \tag*{(28)} d A d [ M + d − 1 M − 1 + M − 1 + d − 1 1 − M − 1 ] . (28)
It remains to estimate A d A_d A d . Since
q ∼ Beta ( 1 2 , d − 1 2 ) , q \sim\operatorname{Beta}\left(\frac{1}{2},\frac{d-1}{2}\right), q ∼ Beta ( 2 1 , 2 d − 1 ) ,
we get
A d = B ( 1 , d / 2 ) B ( 1 / 2 , ( d − 1 ) / 2 ) . A_d=\frac{B(1,d/2)}{B(1/2,(d-1)/2)}. A d = B ( 1/2 , ( d − 1 ) /2 ) B ( 1 , d /2 ) .
Using
B ( 1 , d / 2 ) = 2 d , B(1,d/2)=\frac{2}{d}, B ( 1 , d /2 ) = d 2 ,
and
B ( 1 / 2 , ( d − 1 ) / 2 ) = π Γ ( ( d − 1 ) / 2 ) Γ ( d / 2 ) , B(1/2,(d-1)/2)=\frac{\sqrt{\pi}\Gamma((d-1)/2)}{\Gamma(d/2)}, B ( 1/2 , ( d − 1 ) /2 ) = Γ ( d /2 ) π Γ (( d − 1 ) /2 ) ,
we obtain
A d = 2 d Γ ( d / 2 ) π Γ ( ( d − 1 ) / 2 ) . A_d=\frac{2}{d}\frac{\Gamma(d/2)}{\sqrt{\pi}\Gamma((d-1)/2)}. A d = d 2 π Γ (( d − 1 ) /2 ) Γ ( d /2 ) .
By the standard gamma-ratio estimate,
Γ ( d / 2 ) Γ ( ( d − 1 ) / 2 ) = Θ ( d ) , \frac{\Gamma(d/2)}{\Gamma((d-1)/2)}=\Theta(\sqrt{d}), Γ (( d − 1 ) /2 ) Γ ( d /2 ) = Θ ( d ) ,
and hence
A d = Θ ( d − 1 / 2 ) . A_d=\Theta(d^{-1/2}). A d = Θ ( d − 1/2 ) .
Thus
d A d = Θ ( d ) . dA_d=\Theta(\sqrt{d}). d A d = Θ ( d ) .
Finally, if M = κ β ≥ 2 d M=\kappa^\beta\ge2d M = κ β ≥ 2 d , then
M − 1 M + d − 1 ≥ c 0 \frac{M-1}{M+d-1}\ge c_0 M + d − 1 M − 1 ≥ c 0
for a universal constant c 0 > 0 c_0>0 c 0 > 0 . The second term is nonnegative, so
S β ( A ) ≥ c 0 d A d ≥ c d . S_\beta(A)\ge c_0dA_d\ge c\sqrt{d}. S β ( A ) ≥ c 0 d A d ≥ c d .
The upper bound S β ( A ) ≤ C d S_\beta(A)\le C\sqrt{d} S β ( A ) ≤ C d follows from the same formula and the fact that both bracketed terms are at most 1. □
Remark 1 (Interpretation). The uniform theorem only uses S β ( A ) ≳ 1 S_\beta(A)\gtrsim1 S β ( A ) ≳ 1 . For a rank-one spike with κ β ≳ d \kappa^\beta\gtrsim d κ β ≳ d , the useful spectral drift is larger:
S β ( A ) ≍ d . S_\beta(A)\asymp\sqrt{d}. S β ( A ) ≍ d .
This happens because a Haar row assigns mass
q = p 1 ∼ Beta ( 1 2 , d − 1 2 ) q=p_1\sim\operatorname{Beta}\left(\frac{1}{2},\frac{d-1}{2}\right) q = p 1 ∼ Beta ( 2 1 , 2 d − 1 )
to the spiked eigendirection, and
E q ( 1 − q ) ≍ d − 1 / 2 . \mathbb{E}\sqrt{q(1-q)}\asymp d^{-1/2}. E q ( 1 − q ) ≍ d − 1/2 .
The definition of S β S_\beta S β contains an additional factor of d d d , so the net scale is d \sqrt{d} d .
Consequence for the drift rate in the spiky regime
We now spell out the resulting improvement in the one-step drift. Recall the general drift estimate
E [ Φ β ( A t + 1 ) − Φ β ( A t ) ∣ A t ] ≤ − 2 α ν b , d d − 1 S β ( A t ) + C T a y α 2 β ( b − 1 ) . \mathbb{E}[\Phi_\beta(A_{t+1})-\Phi_\beta(A_t)\mid A_t]\le-\frac{2\alpha\nu_{b,d}}{\sqrt{d-1}}S_\beta(A_t)+C_{\mathrm{Tay}}\alpha^2\beta(b-1). E [ Φ β ( A t + 1 ) − Φ β ( A t ) ∣ A t ] ≤ − d − 1 2 α ν b , d S β ( A t ) + C Tay α 2 β ( b − 1 ) .
Suppose that, on some portion of the trajectory before reaching the target condition number, the iterates satisfy the stronger spiky lower bound
S β ( A t ) ≥ σ d S_\beta(A_t)\ge\sigma\sqrt{d} S β ( A t ) ≥ σ d
for some σ > 0 \sigma> 0 σ > 0 . Using the same globally safe step size
α = ν b , d 8 C T a y β ( b − 1 ) d − 1 , \alpha= \frac{\nu_{b,d}}{8C_{\mathrm{Tay}}\beta(b-1)\sqrt{d}-1}, α = 8 C Tay β ( b − 1 ) d − 1 ν b , d ,
we obtain
E [ Φ β ( A t + 1 ) − Φ β ( A t ) ∣ A t ] ≤ − c σ ν b , d 2 C T a y β ( b − 1 ) d \mathbb{E}[\Phi_\beta(A_{t+1})-\Phi_\beta(A_t)\mid A_t]\le-c\frac{\sigma\nu_{b,d}^{2}}{C_{\mathrm{Tay}}\beta(b-1)\sqrt{d}} E [ Φ β ( A t + 1 ) − Φ β ( A t ) ∣ A t ] ≤ − c C Tay β ( b − 1 ) d σ ν b , d 2
for a universal numerical constant c > 0 c>0 c > 0 , after absorbing the Taylor remainder into the leading negative term.
Consequently, if
S β ( A t ) ≥ σ d S_\beta(A_t)\ge\sigma\sqrt{d} S β ( A t ) ≥ σ d
holds until the hitting time
τ κ ⋆ = inf { t : κ ( A t ) ≤ κ ⋆ } , \tau_{\kappa_\star}=\inf\{t:\kappa(A_t)\le\kappa_\star\}, τ κ ⋆ = inf { t : κ ( A t ) ≤ κ ⋆ } ,
then the stopped-supermartingale argument gives
E [ τ κ ⋆ ] ≤ C β ( b − 1 ) d σ ν b , d 2 Φ β ( A 0 ) . \mathbb{E}[\tau_{\kappa_\star}]\le C\frac{\beta(b-1)\sqrt{d}}{\sigma\nu_{b,d}^{2}}\Phi_\beta(A_0). E [ τ κ ⋆ ] ≤ C σ ν b , d 2 β ( b − 1 ) d Φ β ( A 0 ) .
Since
Φ β ( A 0 ) ≤ log κ ( A 0 ) , \Phi_\beta(A_0)\le\log\kappa(A_0), Φ β ( A 0 ) ≤ log κ ( A 0 ) ,
we get
E [ τ κ ⋆ ] ≤ C β ( b − 1 ) d σ ν b , d 2 log κ ( A 0 ) . \mathbb{E}[\tau_{\kappa_\star}]\le C\frac{\beta(b-1)\sqrt{d}}{\sigma\nu_{b,d}^{2}}\log\kappa(A_0). E [ τ κ ⋆ ] ≤ C σ ν b , d 2 β ( b − 1 ) d log κ ( A 0 ) .
For fixed block size b b b , ν b , d 2 = Θ b ( 1 ) \nu_{b,d}^{2}=\Theta_b(1) ν b , d 2 = Θ b ( 1 ) . Thus, in the spiky regime,
E [ τ κ ⋆ ] = O κ ⋆ , b , σ ( β d log κ ( A 0 ) ) . \mathbb{E}[\tau_{\kappa_\star}]=O_{\kappa_\star,b,\sigma}\left(\beta\sqrt{d}\log\kappa(A_0)\right). E [ τ κ ⋆ ] = O κ ⋆ , b , σ ( β d log κ ( A 0 ) ) .
With the usual choice β = O κ ⋆ ( log d ) \beta=O_{\kappa_\star}(\log d) β = O κ ⋆ ( log d ) , this becomes
E [ τ κ ⋆ ] = O κ ⋆ , b , σ ( d log d log κ ( A 0 ) ) . \mathbb{E}[\tau_{\kappa_\star}]=O_{\kappa_\star,b,\sigma}\left(\sqrt{d}\log d\log\kappa(A_0)\right). E [ τ κ ⋆ ] = O κ ⋆ , b , σ ( d log d log κ ( A 0 ) ) .
This is a genuine d \sqrt{d} d improvement over the worst-case O ( d log d log κ ( A 0 ) ) O(d\log d\log\kappa(A_0)) O ( d log d log κ ( A 0 )) bound.
Establishing intuition: First-order effect of a row correction
We now justify the illustrative eigenvalue calculation in Section 4; this example is not used in the proof of Theorem 4. Consider A ~ = I + ( λ − 1 ) v v T \widetilde{A}=I+(\lambda-1)vv^{\mathsf T} A = I + ( λ − 1 ) v v T , with λ > 0 \lambda>0 λ > 0 , λ ≠ 1 \lambda\ne1 λ = 1 , and ∥ v ∥ = 1 \lVert v\rVert=1 ∥ v ∥ = 1 . The eigenvalue λ \lambda λ is simple, with eigenvector v v v , while all remaining eigenvalues equal 1.
For distinct coordinates i , j i,j i , j , the congruence update
A ~ ( α ) = ( I + α e i e j T ) A ( I + α e i e j T ) T . \widetilde{A}(\alpha)=(I+\alpha e_i e_j^{\mathsf T})A(I+\alpha e_i e_j^{\mathsf T})^{\mathsf T}. A ( α ) = ( I + α e i e j T ) A ( I + α e i e j T ) T .
Expanding around α = 0 \alpha=0 α = 0 gives
A ~ ( α ) = A ~ + α ( e i e j T A ~ + A ~ e j e i T ) + O ( α 2 ) . \widetilde{A}(\alpha)=\widetilde{A}+\alpha(e_i e_j^{\mathsf T}\widetilde{A}+\widetilde{A}e_j e_i^{\mathsf T})+O(\alpha^2). A ( α ) = A + α ( e i e j T A + A e j e i T ) + O ( α 2 ) .
By first-order eigenvalue perturbation, the eigenvalue λ ( α ) \lambda(\alpha) λ ( α ) originating from λ \lambda λ satisfies
λ ′ ( 0 ) = v T ( e i e j T A ~ + A ~ e j e i T ) v = 2 λ v T e i e j T v = 2 λ v i v j . \begin{aligned}
\lambda'(0)=v^{\mathsf T}(e_i e_j^{\mathsf T}\widetilde{A}+\widetilde{A}e_j e_i^{\mathsf T})v \\
&=2\lambda v^{\mathsf T}e_i e_j^{\mathsf T}v=2\lambda v_i v_j.
\end{aligned} λ ′ ( 0 ) = v T ( e i e j T A + A e j e i T ) v = 2 λ v T e i e j T v = 2 λ v i v j .
Since A ~ i j = ( λ − 1 ) v i v j \widetilde{A}_{ij}=(\lambda-1)v_i v_j A ij = ( λ − 1 ) v i v j for i ≠ j i\ne j i = j ,
λ ( α ) = λ + 2 α λ λ − 1 A ~ i j + O ( α 2 ) . \lambda(\alpha)=\lambda+\frac{2\alpha\lambda}{\lambda-1}\widetilde{A}_{ij}+O(\alpha^2). λ ( α ) = λ + λ − 1 2 α λ A ij + O ( α 2 ) .
For A ~ i j < 0 \widetilde{A}_{ij}<0 A ij < 0 and sufficiently small α > 0 \alpha>0 α > 0 , the exceptional eigenvalue therefore moves toward 1, whether λ > 1 \lambda>1 λ > 1 or λ < 1 \lambda<1 λ < 1 .
This calculation tracks only the exceptional eigenvalue under a single row correction. Other eigenvalues may also change, so it does not establish a decrease in the condition number of the full matrix.
Empirical evidence for the unblocked load bound
The proof in § 6 uses block selection to control the load of the row-min update. We test whether the same type of control holds for the unblocked selector used in the practical algorithm. For a mixed matrix A = Q Λ Q T A = Q\Lambda Q^{\mathsf{T}} A = Q Λ Q T , define
τ i ( A ) = a r g m i n j ≠ i A i j , m ( A ) = ∥ R ( A ) ∥ 1 = max j ∣ { i : τ i ( A ) = j } ∣ . \tau_i(A) = \mathop{\mathrm{arg\,min}}_{j \ne i} A_{ij}, \qquad m(A) = \lVert\mathcal{R}(A) \rVert_1 = \max_j \left\lvert\{i : \tau_i(A) = j\} \right\rvert. τ i ( A ) = arg min j = i A ij , m ( A ) = ∥ R ( A ) ∥ 1 = j max ∣ { i : τ i ( A ) = j } ∣ .
Thus m ( A ) m(A) m ( A ) is the maximum number of rows whose minimum off-diagonal entry selects the same column. The step-size scaling used in our simulations is supported if
S β ( A ) m ( A ) = Ω ( 1 ) , \frac{S_\beta(A)}{\sqrt{m(A)}} = \Omega(1), m ( A ) S β ( A ) = Ω ( 1 ) ,
where S β S_\beta S β is the spectral drift used in Lemma 2 and defined in (27) . We therefore measure this ratio directly after Haar mixing with global argmin selection, with no blocking.
Throughout this experiment we set β = log d \beta= \log d β = log d . We generate centered log-spectra x ∈ R d x \in\mathbb{R}^d x ∈ R d , with λ i = exp ( x i ) \lambda_i = \exp(x_i) λ i = exp ( x i ) , and retain only spectra with Φ β ( Λ ) ≥ 1 \Phi_\beta(\Lambda) \ge1 Φ β ( Λ ) ≥ 1 . To search for possible failures of the bound, we sweep several adversarial spectral families: top spikes (k k k large eigenvalues), bottom holes (k k k small eigenvalues), two-block spectra (a fraction f f f at + h +h + h and the rest at − h -h − h ), power-law spectra (x i = h sign ( t i ) ∣ t i ∣ p x_i = h \operatorname{sign}(t_i) \lvert t_i \rvert^p x i = h sign ( t i ) ∣ t i ∣ p ), and lognormal spectra (x i = σ g i x_i = \sigma g_i x i = σ g i , g i ∼ N ( 0 , 1 ) g_i \sim\mathcal{N}(0,1) g i ∼ N ( 0 , 1 ) ). Concretely, we vary
k ∈ { 1 , 2 , 4 , ⌊ d ⌋ , d / 8 , d / 2 } , f ∈ { 0.05 , 0.10 , 0.25 , 0.50 , 0.75 , 0.90 } , k \in\{1, 2, 4, \lfloor\sqrt{d} \rfloor, d/8, d/2\}, \qquad f \in\{0.05, 0.10, 0.25, 0.50, 0.75, 0.90\}, k ∈ { 1 , 2 , 4 , ⌊ d ⌋ , d /8 , d /2 } , f ∈ { 0.05 , 0.10 , 0.25 , 0.50 , 0.75 , 0.90 } ,
h ∈ { 1 , log d , 2 log d , d } , p ∈ { 0.25 , 0.5 , 1 , 2 , 4 } , σ ∈ { 0.5 , 1 , 2 , 4 } . h \in\{1, \log d, 2 \log d, \sqrt{d}\}, \qquad p \in\{0.25, 0.5, 1, 2, 4\}, \qquad\sigma\in\{0.5, 1, 2, 4\}. h ∈ { 1 , log d , 2 log d , d } , p ∈ { 0.25 , 0.5 , 1 , 2 , 4 } , σ ∈ { 0.5 , 1 , 2 , 4 } .
These families target concentrated outliers, low-eigenvalue holes, balanced two-cluster spectra that may create collisions, smooth spectral decay, and irregular heavy-tailed spectra.
For each retained spectrum and dimension, we draw 256 independent Haar matrices Q Q Q , form A = Q Λ Q T A = Q\Lambda Q^{\mathsf{T}} A = Q Λ Q T , compute the exact global row-min selector τ i ( A ) \tau_i(A) τ i ( A ) , and record m ( A ) m(A) m ( A ) . We estimate S β ( Λ ) S_\beta(\Lambda) S β ( Λ ) independently using 3000 Dirichlet( 1 / 2 , … , 1 / 2 ) (1/2,\ldots,1/2) ( 1/2 , … , 1/2 ) samples, matching the squared coordinates of a Haar row. Figure 9 summarizes the results, and Table 4 reports the main aggregate statistics by dimension.
Figure 9. Empirical load scaling for the unblocked selector. Left: distribution of S β / m ( A ) S_{\beta}/\sqrt{m(A)} S β / m ( A ) versus dimension, aggregated over all retained spectra and Haar trials. Right: median S β / m ( A ) S_{\beta}/\sqrt{m(A)} S β / m ( A ) by spectral family. In all tested cases the ratio remains bounded away from zero.
Table 4. Aggregate statistics for the unblocked load experiment. Each row aggregates over all retained spectra and Haar trials at the given dimension.
Across the tested dimensions and spectral families, S β ( Λ ) / m ( A ) S_\beta(\Lambda)/\sqrt{m(A)} S β ( Λ ) / m ( A ) remains bounded away from zero. The smallest values occur for the most symmetric high-collision cases, especially half-mass two-block spectra and the matching top-spike and bottom-hole constructions. Even there, the ratio stays well above zero, supporting the empirical relation
S β ( Λ ) m ( A ) = Ω ( 1 ) . \frac{S_\beta(\Lambda)}{\sqrt{m(A)}} = \Omega(1). m ( A ) S β ( Λ ) = Ω ( 1 ) .
Substituting this into the one-step drift bound gives
α ∗ = Θ ( 1 β m ( A ) d ) , \alpha_* = \Theta\left(\frac{1}{\sqrt{\beta\,m(A)\,d}}\right), α ∗ = Θ ( β m ( A ) d 1 ) ,
matching the blocked rate up to replacing the block load by the actual unblocked load.
Reproducibility details
Compute resources
All experiments were run on a machine with an Intel Xeon Gold 6438M CPU, 125GiB system memory, and four NVIDIA RTX 6000 Ada Generation GPUs. Reported experiments used a single GPU. The software stack used Python 3.12.4, PyTorch 2.4.0+cu121, CUDA 12.8 tooling, and Triton 3.0.0.
The transformer diagnostics used 9 depths and 10 independent runs per depth, for 90 total training runs requiring approximately 90 cumulative GPU-hours. The RAPID numerical experiments were run on the same hardware using PyTorch/Triton kernels, explicit CUDA synchronization for timing, and GPU fast Walsh–Hadamard transforms [9 ] .
Existing assets and licenses
The experiments use synthetic matrices generated by our scripts and public SuiteSparse Matrix Collection instances. SuiteSparse matrices were accessed through ssgetpy; the SuiteSparse Matrix Collection is credited in the main text, and ssgetpy is distributed under the MIT/X11 license.
Our implementation uses Python 3.12.4, PyTorch 2.4.0+cu121, Triton 3.0.0, CUDA tooling, NumPy, SciPy, and fast-hadamard-transform. PyTorch is distributed under a BSD-style license, Triton under the MIT license, NumPy and SciPy under BSD-style licenses, fast-hadamard-transform under the BSD-3-Clause license, and the CUDA Toolkit is governed by the NVIDIA CUDA Toolkit EULA. We use these packages only as software dependencies and do not redistribute modified versions of them.