Introduction
Popularized as a test-time prompting technique, chain-of-thought (CoT) [30 ] is now widely used as training supervision to improve a model’s reasoning ability [33 , 8 ] . Whereas final-answer supervision provides only outcome-level feedback, supervising intermediate steps can help models learn general reasoning procedures. Such CoT-based supervision has produced substantial gains on complex tasks such as mathematics and logical reasoning [14 , 33 , 20 ] .
During inference, a model may need to carry the reasoning procedure learned from CoT supervision beyond the number of steps shown during training to reach the correct answer. In practice, extending reasoning can instead degrade performance, a phenomenon widely known as overthinking, so additional reasoning steps do not necessarily improve accuracy [5 , 26 , 13 ] . Recent empirical studies suggest that overthinking is a problem involving the correctness and stability of the reasoning procedure itself. For example, partial acquisition of reasoning capabilities may temporarily degrade long-horizon reasoning performance [31 , 32 , 24 ] . Moreover, systems with similar short-horizon performance may exhibit sharply different long-horizon failure modes: errors may simply accumulate across reasoning steps, or they may be amplified as the system becomes increasingly confident in and builds on its earlier mistakes [7 , 3 ] . These findings show that locally plausible steps do not guarantee global convergence or error correction under repeated inference.
Despite these observations of long-horizon failures, it remains unclear how the amount and structure of training CoT shape the stability of reasoning. In large language models, training data and model scale also affect performance, making the contribution of CoT supervision difficult to isolate experimentally [6 , 19 ] . Consequently, observed performance offers limited guidance on how to choose CoT training data that support reasoning.
To understand how training CoT affects reasoning theoretically, we introduce an in-context weight prediction model trained on gradient descent (GD) trajectories as teacher CoT. Specifically, we use GD trajectories for linear-regression tasks as teacher CoT and train a linear attention model on each transition. Previous work has shown that sufficient CoT supervision allows a model to approximately implement multi-step GD [16 ] , but a theoretical understanding of long-horizon success conditions and failure regimes remains limited. More recently, phase transitions between successful inference and overthinking have been identified in a setting without training-time CoT (Takanami & Pehlevan, 2026). We extend this framework to finite teacher CoT trajectories and ask whether recursive application of the learned model can reproduce the correct update rule beyond the training horizon. Through this analysis, we characterize how the number of training tasks, context length, and teacher CoT length affect the inference dynamics.
Our contributions are as follows:
We derive a phase diagram in the asymptotic limit showing that context length and the total amount of training CoT divide long-horizon reasoning into four regimes: exact GD recovery, bounded error, exponential divergence, and quadratic divergence. (§ 4 )
We show that reasoning can extend beyond the finite-length teacher CoT. The number of pretraining tasks required for this behavior decreases as the amount of teacher CoT increases, while shorter contexts require more teacher CoT. (§ 5.1 )
We identify two distinct mechanisms of overthinking: error accumulation, where errors introduced at each reasoning step remain uncorrected, and error amplification, where unstable reasoning dynamics repeatedly magnify existing errors, leading to quadratic and exponential MSE growth, respectively. (§ 5.2 )
We show that with short contexts, increasing the training CoT budget can initially degrade long-horizon performance before the model learns to reason correctly. (§ 5.3 )
We empirically show that the same qualitative mechanisms persist in more complex architectures, including fully trained linear attention and multi-head softmax attention. (§ 6 )
Our results provide a unified theoretical understanding of the role of finite teacher CoT, appropriate CoT design as training data, and the mechanisms that generate failure.
Related Work
CoT supervision and overthinking. CoT data are increasingly used as training signals to improve reasoning and distill it into smaller models [15 , 20 , 2 , 11 , 35 , 23 ] . At the same time, longer reasoning or recurrent computation can reduce performance, a phenomenon often described as overthinking [5 , 7 , 26 , 13 , 3 ] . However, most existing work focuses on improving training methods or observing trained models, leaving unclear how the properties of training CoT determine test-time behavior. We study this relation in a solvable model and characterize when training CoT supports correct inference and when it makes the test-time reasoning unstable.
Theoretical studies of CoT. Theoretical studies of CoT have mainly focused on its inference-time benefits, showing that CoT can enable efficient reasoning on otherwise difficult tasks [1 , 18 , 16 ] . However, the conditions under which such learning fails remain poorly understood. To study this question theoretically, recent work extends analytically tractable models of in-context linear regression [9 , 4 , 29 , 34 , 22 ] to iterative CoT, investigating how limited pretraining data or context and task mismatch can lead to overthinking [17 ] (Takanami & Pehlevan 2026). However, these studies mainly analyze the test-time behavior of trained models and do not characterize the effect of providing finite teacher CoT as training data. We therefore focus on training-time CoT and ask how far a model can continue to reason correctly beyond the reasoning steps observed during training and how this generalization fails.
Model
We study an in-context weight-prediction model for linear regression. In this model, training CoT consists of GD trajectories, and the pre-trained model is recursively applied as test-time CoT to reproduce GD in context on new tasks.
Data generation
We consider M M M linear-regression tasks indexed by μ = 1 , … , M \mu= 1,\ldots,M μ = 1 , … , M . For each task μ \mu μ , we prepare the training data and teacher CoT trajectories as follows.
Training tasks. For each of the M M M tasks, we prepare L L L labeled examples { x μ , l , y μ , l } l = 1 , … , L \{x_{\mu,l}, y_{\mu,l}\}_{l=1,\ldots,L} { x μ , l , y μ , l } l = 1 , … , L , given by
X μ : = [ x μ , 1 , … , x μ , L ] ∈ R D × L , y μ : = X μ T w μ + ε μ ∈ R L , (1) X_\mu:= [x_{\mu,1},\ldots,x_{\mu,L}] \in\mathbb{R}^{D \times L}, \qquad y_\mu:= X_\mu^{\mathsf{T}}w_\mu+ \varepsilon_\mu\in\mathbb{R}^{L}, \tag*{(1)} X μ := [ x μ , 1 , … , x μ , L ] ∈ R D × L , y μ := X μ T w μ + ε μ ∈ R L , (1)
where x μ , l ∼ N ( 0 D , I D ) x_{\mu,l} \sim\mathcal{N}(0_D,I_D) x μ , l ∼ N ( 0 D , I D ) , w μ ∼ N ( 0 D , I D / D ) w_\mu\sim\mathcal{N}(0_D,I_D/D) w μ ∼ N ( 0 D , I D / D ) , and ε μ ∼ N ( 0 L , σ 2 I L ) \varepsilon_\mu\sim\mathcal{N}(0_L,\sigma^2 I_L) ε μ ∼ N ( 0 L , σ 2 I L ) , independently across all tasks and examples. We denote the task context by Q μ : = ( X μ , y μ ) Q_\mu:= (X_\mu,y_\mu) Q μ := ( X μ , y μ ) .
CoT as training data. We prepare a K K K -step trajectory of gradient descent (GD) { s μ , k } k = 0 , … , K \{s_{\mu,k}\}_{k=0,\ldots,K} { s μ , k } k = 0 , … , K with step size η > 0 \eta> 0 η > 0 on the empirical squared loss. Starting from zero, its states satisfy
s μ , k + 1 : = s μ , k − η L X μ ( X μ T s μ , k − y μ ) ( k = 0 , … , K − 1 ) , (2) s_{\mu,k+1} := s_{\mu,k} - \frac{\eta}{L}X_\mu\left(X_\mu^{\mathsf{T}}s_{\mu,k}-y_\mu\right) \qquad(k=0,\ldots,K-1), \tag*{(2)} s μ , k + 1 := s μ , k − L η X μ ( X μ T s μ , k − y μ ) ( k = 0 , … , K − 1 ) , (2)
and s μ , 0 : = 0 D s_{\mu,0} := 0_D s μ , 0 := 0 D .
Pre-training setting
During pre-training, the model is trained to predict the next step of the teacher CoT, s μ , k + 1 s_{\mu,k+1} s μ , k + 1 , from the context and the teacher CoT at step k k k , i.e., ( Q μ , s μ , k ) (Q_\mu,s_{\mu,k}) ( Q μ , s μ , k ) . Specifically, the input data (prompt), architecture, and loss function are defined as follows.
Prompt construction. At training step k k k , the prompt contains the original L L L labeled examples and a slot for the current teacher state:
E μ , k : = ( X μ 0 D y μ 0 0 D × L s μ , k 0 L T 1 ) = ( x μ , 1 ⋯ x μ , L 0 D y μ , 1 ⋯ y μ , L 0 0 D ⋯ 0 D s μ , k 0 ⋯ 0 1 ) ∈ R ( 2 D + 2 ) × ( L + 1 ) . (3) E_{\mu,k} :=
\begin{pmatrix}
X_\mu& 0_D \\
y_\mu& 0 \\
0_{D\times L} & s_{\mu,k} \\
0_L^{\mathsf{T}} & 1
\end{pmatrix}
=
\begin{pmatrix}
x_{\mu,1} & \cdots& x_{\mu,L} & 0_D \\
y_{\mu,1} & \cdots& y_{\mu,L} & 0 \\
0_D & \cdots& 0_D & s_{\mu,k} \\
0 & \cdots& 0 & 1
\end{pmatrix}
\in\mathbb{R}^{(2D+2)\times(L+1)}. \tag*{(3)} E μ , k := X μ y μ 0 D × L 0 L T 0 D 0 s μ , k 1 = x μ , 1 y μ , 1 0 D 0 ⋯ ⋯ ⋯ ⋯ x μ , L y μ , L 0 D 0 0 D 0 s μ , k 1 ∈ R ( 2 D + 2 ) × ( L + 1 ) . (3)
The first L L L columns encode labeled examples. The final column is a state slot, and the marker 1 in the last row distinguishes it from an example token. The prompt for predicting s μ , k + 1 s_{\mu,k+1} s μ , k + 1 contains the task context Q μ Q_\mu Q μ and the current state s μ , k s_{\mu,k} s μ , k , but no earlier states. Thus, conditional on the task context, the one-step predictor is Markovian. Masking or downweighting earlier reasoning tokens in this way can improve length generalization [1 , 21 ] .
Linear attention. For a prompt with L L L context examples, we use a one-layer linear self-attention model with a residual connection, defined by
Atten ( E ; θ ) : = E + 1 L ( W V E ) ( W K E ) T W Q E . (4) \operatorname{Atten}(E;\theta) := E + \frac{1}{L}(W_VE)(W_KE)^{\mathsf{T}}W_QE. \tag*{(4)} Atten ( E ; θ ) := E + L 1 ( W V E ) ( W K E ) T W Q E . (4)
Here the trainable parameters are θ = ( W Q , W K , W V ) \theta= (W_Q,W_K,W_V) θ = ( W Q , W K , W V ) , where W Q , W K , W V ∈ R ( 2 D + 2 ) × ( 2 D + 2 ) W_Q,W_K,W_V \in\mathbb{R}^{(2D+2)\times(2D+2)} W Q , W K , W V ∈ R ( 2 D + 2 ) × ( 2 D + 2 ) are the query, key, and value matrices, respectively. We read the state slot of the final column using
Readout ( E ) : = E D + 2 : 2 D + 2 , L + 1 , e n d . (5) \operatorname{Readout}(E) := E_{D+2:2D+2,L+1,\mathrm{end}}. \tag*{(5)} Readout ( E ) := E D + 2 : 2 D + 2 , L + 1 , end . (5)
The next-step predictor of the weight vector is therefore
s ^ μ , k + 1 : = Readout ( Atten ( E μ , k ; θ ) ) . (6) \hat{s}_{\mu,k+1} := \operatorname{Readout}\left(\operatorname{Atten}(E_{\mu,k};\theta)\right). \tag*{(6)} s ^ μ , k + 1 := Readout ( Atten ( E μ , k ; θ ) ) . (6)
Learning. We consider the squared one-step prediction error over all teacher transitions in pretraining data:
L ( θ ) : = 1 M K ∑ μ = 1 M ∑ k = 0 K − 1 ∥ s ^ μ , k + 1 − s μ , k + 1 ∥ 2 2 . (7) \mathcal{L}(\theta) := \frac{1}{MK}\sum_{\mu=1}^{M}\sum_{k=0}^{K-1}\left\|\hat{s}_{\mu,k+1}-s_{\mu,k+1}\right\|_{2}^{2}. \tag*{(7)} L ( θ ) := M K 1 μ = 1 ∑ M k = 0 ∑ K − 1 ∥ s ^ μ , k + 1 − s μ , k + 1 ∥ 2 2 . (7)
Effective model
For analytical simplicity, we impose the following constraints on the trainable parameters:
W V : = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ I D 0 D I D 0 D ∗ ∗ ∗ ∗ ) , W K ⊤ W Q : = ( ∗ ∗ A 0 D ∗ ∗ 0 D ⊤ 0 ∗ ∗ 0 D × D 0 D ∗ ∗ 0 D ⊤ 0 ) , (8) W_V := \begin{pmatrix} * & * & * & * \\ * & * & * & * \\ I_D & 0_D & I_D & 0_D \\ * & * & * & * \end{pmatrix}, \qquad W_K^{\top}W_Q := \begin{pmatrix} * & * & A & 0_D \\ * & * & 0_D^{\top} & 0 \\ * & * & 0_{D\times D} & 0_D \\ * & * & 0_D^{\top} & 0 \end{pmatrix}, \tag*{(8)} W V := ∗ ∗ I D ∗ ∗ ∗ 0 D ∗ ∗ ∗ I D ∗ ∗ ∗ 0 D ∗ , W K ⊤ W Q := ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ A 0 D ⊤ 0 D × D 0 D ⊤ 0 D 0 0 D 0 , (8)
where the rows from top to bottom and the columns from left to right are both partitioned into blocks of dimensions ( D , 1 , D , 1 ) (D,1,D,1) ( D , 1 , D , 1 ) . Here ∗ * ∗ denotes a block that does not affect the readout, while A ∈ R D × D A \in\mathbb{R}^{D\times D} A ∈ R D × D is the only learnable parameter. This restriction is less severe than it may appear: each constrained block is justified by one of three considerations: (i) the rotational symmetry of the data, which motivates choosing the fixed blocks so that they do not select preferred directions; (ii) the fact that fixing it entails no loss of generality in the setting studied here; or (iii) preventing the model from advancing its inference without consulting the context (see Appendix § 11 for details). These reductions concentrate the nontrivial parameter governing inference in the single matrix A A A . Moreover, gradient-flow analyses of related models show that training from suitable initializations leads to analogous block structures (Huang et al., [16 ] ; Javanmard et al., [17 ] ). Under this parameterization, Equation (6) is given by
s ^ μ , k + 1 = s μ , k + 1 L X μ ( X μ ⊤ A s μ , k + η y μ ) . (9) \hat{s}_{\mu,k+1}=s_{\mu,k}+\frac{1}{L}X_\mu\left(X_\mu^{\top}As_{\mu,k}+\eta y_\mu\right). \tag*{(9)} s ^ μ , k + 1 = s μ , k + L 1 X μ ( X μ ⊤ A s μ , k + η y μ ) . (9)
and the effective learning problem derived from Equation (7) is
L e f f ( A ) : = 1 M K ∑ μ = 1 M ∑ k = 0 K − 1 ∥ s ^ μ , k + 1 − s μ , k + 1 ∥ 2 2 + λ D ∥ A ∥ F 2 . (10) \mathcal{L}_{\mathrm{eff}}(A):=\frac{1}{MK}\sum_{\mu=1}^{M}\sum_{k=0}^{K-1}\left\|\hat{s}_{\mu,k+1}-s_{\mu,k+1}\right\|_{2}^{2}+\frac{\lambda}{D}\left\|A\right\|_{F}^{2}. \tag*{(10)} L eff ( A ) := M K 1 μ = 1 ∑ M k = 0 ∑ K − 1 ∥ s ^ μ , k + 1 − s μ , k + 1 ∥ 2 2 + D λ ∥ A ∥ F 2 . (10)
where we introduced the regularization parameter λ > 0 \lambda> 0 λ > 0 . For λ > 0 \lambda> 0 λ > 0 , the objective is strongly convex, so A ^ : = argmin A L e f f ( A ) \hat{A}:=\operatorname*{argmin}_{A}\mathcal{L}_{\mathrm{eff}}(A) A ^ := argmin A L eff ( A ) is unique.
Inference setting
At inference time, we model test-time CoT by fixing the parameters of the trained model and applying the model recursively. Despite its simplicity, this recurrent form of CoT has recently regained attention because it enables flexible reasoning without relying on language tokens (Hao et al., [12 ] ; Geiping et al., [10 ] ; Shen et al., [25 ] ; Zhu et al., [36 ] ).
Test-time CoT. Consider an independent task Q i n = ( X i n , y i n ) Q^{\mathrm{in}}=(X^{\mathrm{in}},y^{\mathrm{in}}) Q in = ( X in , y in ) , drawn from the same distribution as the training tasks. Explicitly, its examples and labels are generated by
X i n : = [ x 1 i n , … , x L i n ] ∈ R D × L , y i n : = ( X i n ) ⊤ w i n + ε i n ∈ R L , (11) X^{\mathrm{in}} := [x^{\mathrm{in}}_1,\ldots,x^{\mathrm{in}}_L]\in\mathbb{R}^{D\times L}, \qquad y^{\mathrm{in}} := (X^{\mathrm{in}})^{\top}w^{\mathrm{in}}+\varepsilon^{\mathrm{in}}\in\mathbb{R}^{L}, \tag*{(11)} X in := [ x 1 in , … , x L in ] ∈ R D × L , y in := ( X in ) ⊤ w in + ε in ∈ R L , (11)
where x l i n ∼ N ( 0 D , I D ) x^{\mathrm{in}}_l\sim\mathcal{N}(0_D,I_D) x l in ∼ N ( 0 D , I D ) , w i n ∼ N ( 0 D , I D / D ) w^{\mathrm{in}}\sim\mathcal{N}(0_D,I_D/D) w in ∼ N ( 0 D , I D / D ) , and ε i n ∼ N ( 0 L , σ 2 I L ) \varepsilon^{\mathrm{in}}\sim\mathcal{N}(0_L,\sigma^2 I_L) ε in ∼ N ( 0 L , σ 2 I L ) . At inference step t t t , the prompt is constructed in the same way as in Equation (3) :
P t : = ( X i n 0 D ( y i n ) ⊤ 0 0 D × L w ^ t 0 L ⊤ 1 ) = ( x 1 i n ⋯ x L i n 0 D y 1 i n ⋯ y L i n 0 0 D ⋯ 0 D w ^ t 0 ⋯ 0 1 ) ∈ R ( 2 D + 2 ) × ( L + 1 ) . (12) P_t:=\begin{pmatrix} X^{\mathrm{in}} & 0_D \\ (y^{\mathrm{in}})^{\top} & 0 \\ 0_{D\times L} & \hat{w}_t \\ 0_L^{\top} & 1 \end{pmatrix}
=\begin{pmatrix} x^{\mathrm{in}}_1 & \cdots& x^{\mathrm{in}}_L & 0_D \\ y^{\mathrm{in}}_1 & \cdots& y^{\mathrm{in}}_L & 0 \\ 0_D & \cdots& 0_D & \hat{w}_t \\ 0 & \cdots& 0 & 1 \end{pmatrix}\in\mathbb{R}^{(2D+2)\times(L+1)}. \tag*{(12)} P t := X in ( y in ) ⊤ 0 D × L 0 L ⊤ 0 D 0 w ^ t 1 = x 1 in y 1 in 0 D 0 ⋯ ⋯ ⋯ ⋯ x L in y L in 0 D 0 0 D 0 w ^ t 1 ∈ R ( 2 D + 2 ) × ( L + 1 ) . (12)
where w ^ t \hat{w}_t w ^ t is the current estimate of w i n w^{\mathrm{in}} w in , and w ^ 0 = 0 D \hat{w}_0=0_D w ^ 0 = 0 D . Then the test-time CoT recursion is
w ^ t + 1 = Readout ( Atten ( P t ; A ^ ) ) = w ^ t + 1 L X i n [ ( X i n ) ⊤ w ^ t + η y i n ] . (13) \hat{w}_{t+1}=\operatorname{Readout}\left(\operatorname{Atten}(P_t;\hat{A})\right)=\hat{w}_t+\frac{1}{L}X^{\mathrm{in}}\left[(X^{\mathrm{in}})^{\top}\hat{w}_t+\eta y^{\mathrm{in}}\right]. \tag*{(13)} w ^ t + 1 = Readout ( Atten ( P t ; A ^ ) ) = w ^ t + L 1 X in [ ( X in ) ⊤ w ^ t + η y in ] . (13)
Evaluation. We evaluate the estimate at inference time t t t by its mean squared error:
E ( t ) : = E ∥ w ^ t − w i n ∥ 2 2 , (14) \mathcal{E}(t) := \mathbb{E}\left\|\widehat{w}_t-w^{\mathrm{in}}\right\|_2^2, \tag*{(14)} E ( t ) := E w t − w in 2 2 , (14)
where the expectation is over the training and test data. For comparison, we define the generalization error when GD is successfully reproduced as
E G D ( t ) : = E ∥ s t G D − w i n ∥ 2 2 , (15) \mathcal{E}_{\mathrm{GD}}(t) := \mathbb{E}\left\|s_t^{\mathrm{GD}}-w^{\mathrm{in}}\right\|_2^2, \tag*{(15)} E GD ( t ) := E s t GD − w in 2 2 , (15)
where s t G D s_t^{\mathrm{GD}} s t GD denotes the GD trajectory at step t t t on the test context, with initial condition s 0 G D = 0 D s_0^{\mathrm{GD}}=0_D s 0 GD = 0 D . When the model perfectly learns to generate the teacher-provided CoT, we have E ( t ) = E G D ( t ) \mathcal{E}(t)=\mathcal{E}_{\mathrm{GD}}(t) E ( t ) = E GD ( t ) .
High-dimensional limit
To obtain a nontrivial regime in which contextual information and training-task diversity remain comparable to the problem dimension, we take the proportional limit D , L , M ⟶ ∞ D,L,M\longrightarrow\infty D , L , M ⟶ ∞ with
L D ⟶ α , M D ⟶ τ , K , t = O ( 1 ) . (16) \frac{L}{D}\longrightarrow\alpha,\qquad\frac{M}{D}\longrightarrow\tau,\qquad K,t=O(1). \tag*{(16)} D L ⟶ α , D M ⟶ τ , K , t = O ( 1 ) . (16)
Here, α \alpha α and τ \tau τ measure the numbers of context examples and training tasks per dimension, respectively, while the training and test-time CoT depths remain finite. We are particularly interested in t > K t>K t > K , where the model must continue inference beyond the GD steps observed in the teacher CoT.
Precise Characterization of Test-Time CoT Dynamics
The central question is how the generalization error E ( t ) \mathcal{E}(t) E ( t ) evolves with test-time depth: when does the CoT inference reproduce GD, and what form does its failure take otherwise? To this end, we first seek a precise characterization of E ( t ) \mathcal{E}(t) E ( t ) . We introduce training CoT budget as
φ : = τ ( K − 1 ) . (17) \varphi:= \tau(K-1). \tag*{(17)} φ := τ ( K − 1 ) . (17)
Since it measures the total number of CoT transitions in the training data, φ \varphi φ can be interpreted as the computational budget used to prepare the training CoT trajectories.
In the limit λ → 0 \lambda\to0 λ → 0 , the CoT inference introduced in Equation (13) gives
w ^ t = Q t X i n y i n / L , (18) \widehat{w}_t=Q_tX^{\mathrm{in}}y^{\mathrm{in}}/L, \tag*{(18)} w t = Q t X in y in / L , (18)
where we introduced
H : = 1 L X i n ( X i n ) ⊤ , Q t : = η ∑ j = 0 t − 1 ( I D + H A ^ ) j . (19) H:=\frac{1}{L}X^{\mathrm{in}}(X^{\mathrm{in}})^\top,\qquad Q_t:=\eta\sum_{j=0}^{t-1}(I_D+H\widehat{A})^j. \tag*{(19)} H := L 1 X in ( X in ) ⊤ , Q t := η j = 0 ∑ t − 1 ( I D + H A ) j . (19)
Consequently, the generalization error in Equation (14) is given by
E ( t ) = 1 − 2 D E tr ( Q t H ) + 1 D E ∥ Q t H ∥ F 2 + σ 2 L E tr ( Q t H Q t ⊤ ) . (20) \mathcal{E}(t)=1-\frac{2}{D}\mathbb{E}\operatorname{tr}(Q_tH)+\frac{1}{D}\mathbb{E}\left\|Q_tH\right\|_F^2+\frac{\sigma^2}{L}\mathbb{E}\operatorname{tr}(Q_tHQ_t^\top). \tag*{(20)} E ( t ) = 1 − D 2 E tr ( Q t H ) + D 1 E ∥ Q t H ∥ F 2 + L σ 2 E tr ( Q t H Q t ⊤ ) . (20)
The last two terms in Equation (20) mix Q t Q_t Q t and Q t ⊤ Q_t^\top Q t ⊤ . Because Q t Q_t Q t is a polynomial in H A ^ H\widehat{A} H A , evaluating these terms at arbitrary depth t t t requires not only its eigenvalue distribution but the full family of mixed ∗ * ∗ -moments involving H A ^ H\widehat{A} H A and A ^ T H \widehat{A}^{\mathsf{T}}H A T H . To overcome this difficulty, Takanami & Pehlevan (2026) introduced two-point generating functions and computed them by iteratively applying the cavity method in random matrix theory. In the present setting, the training CoT trajectories couple successive transitions, so the resulting cavity equations do not close under the same recursion. However, the two-point problem reduces to one-point Marchenko-Pastur averages when the learned matrix takes the form A ^ = − η P \widehat{A}=-\eta P A = − η P for an orthogonal projector P P P . In this case, the learned update recovers full GD or performs GD only on the subspace learned during pretraining. We refer to the latter as projected GD. This reduction yields the following result.
Result 4.1 (Finite-depth error in GD or projected-GD regimes). Consider λ → 0 \lambda\to0 λ → 0 . For ρ > 0 \rho>0 ρ > 0 , let ν ρ \nu_\rho ν ρ denote the Marchenko–Pastur law with sample-to-dimension ratio ρ \rho ρ , and define
⟨ f ⟩ ρ : = ∫ f ( x ) d ν ρ ( x ) , q t ( x ) : = η ∑ j = 0 t − 1 ( 1 − η x ) j , κ j , t : = ( α − φ ) ( η t ) j + φ ⟨ q j ⟩ α / φ . (21) \langle f\rangle_\rho:= \int f(x)\,\mathrm{d}\nu_\rho(x), \qquad q_t(x):=\eta\sum_{j=0}^{t-1}(1-\eta x)^j,\qquad\kappa_{j,t}:=(\alpha-\varphi)(\eta t)^j+\varphi\langle q^j\rangle_{\alpha/\varphi}. \tag*{(21)} ⟨ f ⟩ ρ := ∫ f ( x ) d ν ρ ( x ) , q t ( x ) := η j = 0 ∑ t − 1 ( 1 − η x ) j , κ j , t := ( α − φ ) ( η t ) j + φ ⟨ q j ⟩ α / φ . (21) If φ > max { 1 , 1 / α } \varphi>\max\{1,1/\alpha\} φ > max { 1 , 1/ α } , the learned update is GD and
E ( t ) = E G D ( t ) = ⟨ ( 1 − x q t ) 2 ⟩ α + σ 2 α ⟨ x q t 2 ⟩ α . (22) \mathcal{E}(t)=\mathcal{E}_{\mathrm{GD}}(t)=\langle(1-xq_t)^2\rangle_\alpha+\frac{\sigma^2}{\alpha}\langle xq_t^2\rangle_\alpha. \tag*{(22)} E ( t ) = E GD ( t ) = ⟨( 1 − x q t ) 2 ⟩ α + α σ 2 ⟨ x q t 2 ⟩ α . (22) If α > 1 \alpha>1 α > 1 and 0 < φ < 1 0<\varphi<1 0 < φ < 1 , the learned update is projected GD and
E ( t ) = 1 − φ + φ ⟨ ( 1 − x q t ) 2 ⟩ α / φ + φ [ 2 ( 1 − φ ) + σ 2 ] α ⟨ x q t 2 ⟩ α / φ − 2 ( 1 − φ ) α κ 1 , t + ( 1 − φ ) ( 1 − φ + σ 2 ) α 2 κ 2 , t + 1 − φ α 2 κ 1 , t 2 . (23) \begin{aligned}
\mathcal{E}(t)={}&1-\varphi+\varphi\langle(1-xq_t)^2\rangle_{\alpha/\varphi}+\frac{\varphi[2(1-\varphi)+\sigma^2]}{\alpha}\langle xq_t^2\rangle_{\alpha/\varphi}\\
&-\frac{2(1-\varphi)}{\alpha}\kappa_{1,t}+\frac{(1-\varphi)(1-\varphi+\sigma^2)}{\alpha^2}\kappa_{2,t}+\frac{1-\varphi}{\alpha^2}\kappa_{1,t}^2. \tag*{(23)}
\end{aligned} E ( t ) = 1 − φ + φ ⟨( 1 − x q t ) 2 ⟩ α / φ + α φ [ 2 ( 1 − φ ) + σ 2 ] ⟨ x q t 2 ⟩ α / φ − α 2 ( 1 − φ ) κ 1 , t + α 2 ( 1 − φ ) ( 1 − φ + σ 2 ) κ 2 , t + α 2 1 − φ κ 1 , t 2 . (23)
This result characterizes the regimes in which the learned update recovers full GD or projected GD, enabling a complete analytical characterization of its test-time dynamics. In the remaining regime, evaluating Equation (20) at finite t t t still requires the two-point functions. Instead, to isolate the failure mechanisms of interest, we study E ( t ) \mathcal{E}(t) E ( t ) as t → ∞ t\to\infty t → ∞ . As Equation (19) shows, Q t \mathbf{Q}_t Q t is a sum of powers of the inference matrix. In this limit, the relevant dominant eigenvalues alone determine whether E ( t ) \mathcal{E}(t) E ( t ) remains bounded, grows polynomially, or diverges exponentially. The required one-point spectral quantities can be obtained from the cavity method in random matrix theory. Combining them with the GD and projected GD regimes above yields the following four phases.
Result 4.2 (Long-time test-time CoT dynamics). There exist critical values φ − ( α ) \varphi_-(\alpha) φ − ( α ) and φ + ( α ) \varphi_+(\alpha) φ + ( α ) such that, for sufficiently small η > 0 \eta>0 η > 0 and as t → ∞ t\to\infty t → ∞ ,
E ( t ) = { E G D ( t ) , φ > max { 1 , 1 / α } , O ( 1 ) , 0 < α < 1 , φ + < φ < 1 / α , exp ( Θ ( η t ) ) , 0 < α < 1 , φ − < φ < φ + , Θ ( t 2 ) , ( 0 < α < 1 , 0 < φ < φ − ) or ( α > 1 , 0 < φ < 1 ) . (24) \mathcal{E}(t)=
\begin{cases}
\mathcal{E}_{\mathrm{GD}}(t), & \varphi>\max\{1,1/\alpha\},\\
O(1), & 0<\alpha<1,\quad\varphi_+<\varphi<1/\alpha,\\
\exp(\Theta(\eta t)), & 0<\alpha<1,\quad\varphi_-<\varphi<\varphi_+,\\
\Theta(t^2), & (0<\alpha<1,\ 0<\varphi<\varphi_-)\text{ or }(\alpha>1,\ 0<\varphi<1).
\end{cases} \tag*{(24)} E ( t ) = ⎩ ⎨ ⎧ E GD ( t ) , O ( 1 ) , exp ( Θ ( η t )) , Θ ( t 2 ) , φ > max { 1 , 1/ α } , 0 < α < 1 , φ + < φ < 1/ α , 0 < α < 1 , φ − < φ < φ + , ( 0 < α < 1 , 0 < φ < φ − ) or ( α > 1 , 0 < φ < 1 ) . (24)
Appendix § 12 lists the corresponding derivations. Figure 1 summarizes the phase diagram and its agreement with numerical experiments.
Figure 1. Training CoT budget and context length control GD recovery and test-time error growth. (A) Theoretical phase diagram in the context ratio α \alpha α and training CoT budget φ = τ ( K − 1 ) \varphi=\tau(K-1) φ = τ ( K − 1 ) . The four regions correspond to GD recovery, bounded error, exponential divergence, and quadratic divergence. (B) Numerical experiments (circles) and theoretical prediction (solid line) on excess generalization error E ( t ) − E G D ( t ) \mathcal{E}(t)-\mathcal{E}_{\mathrm{GD}}(t) E ( t ) − E GD ( t ) at α = 2 \alpha=2 α = 2 . (C) Numerical experiments of the generalization error at α = 0.625 \alpha=0.625 α = 0.625 . (D) Typical test-time error dynamics in the four phases; the dotted lines show the theoretical long-time predictions, and the inset highlights the quadratic and exponential regimes at large t t t . (B,C) The vertical dotted lines show the theoretical phase boundaries. Parameters: (B,C) D = 96 D=96 D = 96 , K = 2 K=2 K = 2 , η = 0.15 \eta=0.15 η = 0.15 and σ 2 = 0.01 \sigma^2=0.01 σ 2 = 0.01 . (B-D) Error bars represent one standard error across eight independent runs.
Taken together, Results 4.1 and 4.2 show that the learned update and its long-time behavior change qualitatively with the training CoT budget and the context length. With sufficient budget, the learned update recovers GD, whereas below this threshold the error can remain bounded or diverge polynomially or exponentially. The next section discusses the implications of this phase diagram.
Insights from the Test-Time CoT Phase Diagram
In the previous section, we theoretically derived the test-time dynamics of the generalization error in the regimes where the learned update recovers GD or projected GD, and identified the phase transitions governing the long-time inference limit. In this section, we discuss what these results reveal about the effects of training CoT, their practical implications, and related empirical observations.
Recovering GD from Finite-Length CoT
In this subsection, we discuss the GD recovery phase and the conditions that determine its boundary.
Generalization beyond the training horizon. The first insight is that finite-length teacher CoT can teach the full GD update rule. Although training trajectories contain only K K K steps, Result 4.1 shows that, in the recovery phase, the test-time recursion matches GD beyond the training horizon. From a practical perspective, increasing the training CoT length K K K reduces the number of tasks needed to recover GD. This provides a practical trade-off in training-data design: when collecting diverse tasks and in-context examples is costly, longer teacher CoT can be used instead.
CoT budget matters more than task diversity or CoT length alone. In our model, Results 4.1 and 4.2 show that the recovery condition depends on the number of training tasks and the training CoT length K K K only through the CoT budget φ = τ ( K − 1 ) \varphi= \tau(K - 1) φ = τ ( K − 1 ) . To understand this mechanism intuitively, consider α > 1 \alpha> 1 α > 1 : there are D 2 D^2 D 2 parameters to learn and M ( K − 1 ) M(K - 1) M ( K − 1 ) teacher steps, each providing D D D scalar constraints. This gives the recovery condition
M ( K − 1 ) D > D 2 ⟺ φ = M ( K − 1 ) / D > 1. (25) M(K - 1)D > D^2 \qquad\Longleftrightarrow\qquad\varphi= M(K - 1)/D > 1. \tag*{(25)} M ( K − 1 ) D > D 2 ⟺ φ = M ( K − 1 ) / D > 1. (25)
Because each teacher step adds a linearly independent state direction until the accumulated state matrix has rank D D D , the recovery condition depends on τ \tau τ and K K K only through the CoT budget φ \varphi φ .
More generally, our result suggests that the value of teacher CoT is determined not by the number of steps, but by the diversity of states used to constrain the update rule. If successive teacher states are redundant, shorter teacher CoT from more diverse tasks may be more informative. Conversely, a longer teacher CoT may compensate for fewer tasks when it contains sufficiently diverse states.
Context length determines the CoT budget required. For 0 < α < 1 0 < \alpha< 1 0 < α < 1 , however, the CoT budget required for recovery depends on the context length (φ > 1 / α \varphi> 1/\alpha φ > 1/ α ). This dependence can be understood through a simple analogy. Suppose the task is sorting, but the context contains only examples of lists without duplicates, such as [2, 1, 3]. In this case, sorting and removing duplicates before sorting produce the same output [1, 2, 3], so matching the examples does not uniquely identify the intended rule. However, an example containing duplicates, such as [1, 2, 2, 3], distinguishes the two rules: sorting returns [1, 2, 2, 3], whereas removing duplicates before sorting returns [1, 2, 3]. Similarly, in our setting, a short context constrains the update rule only on a subspace, so a larger teacher CoT budget across contexts is required to identify it. In our model, this trade-off is reflected in the recovery condition α φ > 1 \alpha\varphi> 1 α φ > 1 in Result 4.2. Practically, this suggests that the teacher CoT budget should not be chosen independently of the context length.
Two Mechanisms of Overthinking
Figure 1 A shows that, in the divergent regimes, test-time error grows either polynomially or exponentially, depending on the training CoT budget and context length. To explain these behaviors, we formulate inference as a state transition and characterize polynomial overthinking as error accumulation and exponential overthinking as error amplification [3 ] . The test-time dynamics in Equation (13) can be written as
w ^ t + 1 = J w ^ t + ( η / L ) X i n , i n y i n , (26) \hat{w}_{t+1} = J\hat{w}_t + (\eta/L)X^{\mathrm{in},\mathrm{in}}y^{\mathrm{in}}, \tag*{(26)} w ^ t + 1 = J w ^ t + ( η / L ) X in , in y in , (26)
where J = I + H ^ A J = I + \hat{H}A J = I + H ^ A . Here, the first term propagates the current state, while the second term injects input from the context at every step. Error evolution is determined by the eigenvalue structure of J J J .
For error accumulation, consider the polynomial regime in Result 4.2. In this regime, we show that J J J has an eigenmode with eigenvalue 1 that is excited by the context input (see Appendices § 14 and § 15 ).
Let z t z_t z t and c ≠ 0 c \ne0 c = 0 denote the state and input components along one such excited mode, respectively. Projecting Equation (26) onto this mode gives
z t + 1 = z t + η c . (27) z_{t+1} = z_t + \eta c. \tag*{(27)} z t + 1 = z t + η c . (27)
Iterating this recursion from z 0 = 0 z_0 = 0 z 0 = 0 yields z t = η c t z_t = \eta ct z t = η c t . Here, the unit coefficient on z t z_t z t means that the previously accumulated state persists unchanged from one step to the next, so the input added at each step accumulates rather than being canceled. Consequently, the estimate grows in proportion to t t t , and the MSE diverges as t 2 t^2 t 2 . In the projected-GD regime (α > 1 \alpha> 1 α > 1 and φ < 1 \varphi< 1 φ < 1 ), these unit-eigenvalue modes correspond to directions outside the subspace learned during pretraining.
For error amplification, consider the exponential regime in Result 4.2. In this regime, we show that J J J has an unstable eigenmode with eigenvalue r r r satisfying ∣ r ∣ > 1 |r| > 1 ∣ r ∣ > 1 , and the context input excites this mode (see Proposition E.8). Let z t z_t z t and c ≠ 0 c \ne0 c = 0 denote, respectively, the state and input components associated with this mode. Projecting Equation (26) onto the mode gives
z t + 1 = r z t + η c . (28) z_{t+1} = rz_t + \eta c. \tag*{(28)} z t + 1 = r z t + η c . (28)
Iterating this recursion from z 0 = 0 z_0 = 0 z 0 = 0 yields z t = η c ( r t − 1 ) / ( r − 1 ) z_t = \eta c (r^t - 1)/(r - 1) z t = η c ( r t − 1 ) / ( r − 1 ) , which grows exponentially with t t t because ∣ r ∣ > 1 |r| > 1 ∣ r ∣ > 1 . In our model, this exponential growth arises not merely from a failure to learn the update in some directions, but from learning an incorrect update that actively amplifies errors.
However, unit or unstable modes do not cause divergence unless they are excited by the context input. When α < 1 \alpha< 1 α < 1 , the context input is confined to a lower-dimensional subspace and may have zero component along these modes (c = 0 c = 0 c = 0 ). In that case, neither error accumulation nor amplification occurs, giving rise to the bounded regime.
These two mechanisms are also consistent with the empirical observations of Ainslie et al. [3 ] . In autoregressive dynamical-system prediction, they found that models with eigenvalues outside the unit circle (∣ r ∣ > 1 |r| > 1 ∣ r ∣ > 1 ) rapidly amplified errors and produced unphysical trajectories, whereas models with eigenvalues near the unit circle (∣ r ∣ ≈ 1 |r| \approx1 ∣ r ∣ ≈ 1 ) gradually accumulated prediction errors over time. Starting from the reasoning dynamics of a linear attention model, our study explains how the system undergoes sharp transitions among the three phases of error accumulation, error amplification, and bounded error depending on the balance between the training CoT budget and context length.
Non-monotonic Effects of the Training CoT Budget
Figure 1 C shows that, for α < 1 \alpha< 1 α < 1 , increasing the training CoT budget leads to successive transitions from quadratic divergence to exponential divergence, bounded error, and finally GD recovery. Notably, at intermediate budgets, adding teacher CoT can worsen long-time error growth.
This non-monotonicity can be understood as follows. With very little teacher CoT, repeated attention updates add nearly the same context information at each step, causing errors to accumulate. At intermediate training CoT budgets, the model learns to use its current estimate in the next update, but with short contexts it does not yet learn the correct update rule. The resulting reasoning dynamics amplify errors from one step to the next, causing exponential growth. As the training CoT budget increases further, the model learns reliable updates and eventually recovers GD.
A similar non-monotonic pattern has been observed in practical CoT training. Ren et al. [24 ] report that model performance initially declines and then recovers during supervised fine-tuning with long teacher CoT. Our theory offers a possible explanation for this behavior by showing that adding teacher CoT can temporarily worsen reasoning performance when short contexts do not sufficiently identify the update rule.
Experiments Beyond the Effective Model
This section evaluates whether the qualitative behaviors predicted by the effective model persist in more complex architectures. We retain the setup of § 3 and vary only the architecture. Specifically, we evaluate two end-to-end trained setups: a single-head linear-attention model (optimizing W Q , W K , W V \mathbf{W}_Q, \mathbf{W}_K, \mathbf{W}_V W Q , W K , W V ) and a two-head softmax-attention model (optimizing W Q , W K , W V , W O \mathbf{W}_Q, \mathbf{W}_K, \mathbf{W}_V, \mathbf{W}_O W Q , W K , W V , W O ). Both architectures incorporate a context-only mask: the current state serves as the query, whereas the labeled context examples supply the keys and values. Masking out the state token from the key–value sequence prevents state-only updates and ensures that every inference step depends on the context. Complete formulations, parameterizations, and optimization details are provided in Appendix § 16 .§ 1 .
Figure 2 reports the test-time generalization error dynamics for linear and softmax attention. The first observation is that, given sufficient training CoT, both linear and softmax attention maintain stable inference beyond the CoT length used in training. This suggests that end-to-end trained attention models can learn from finite-length CoT to continue reasoning effectively beyond the training horizon, as discussed in § 5.1 .
Figure 2. Training CoT budget produces non-monotonic long-horizon performance in fully trained attention. Numerical experiments of the test-time generalization error for (A) Single-head linear attention with learned Q/K/V and (B) Two-head softmax attention with learned Q/K/V/O. Parameters: (A,B) D = 32 D = 32 D = 32 , α = 0.75 \alpha= 0.75 α = 0.75 , K = 2 K = 2 K = 2 , η = 0.1 \eta= 0.1 η = 0.1 , and σ = 0.1 \sigma= 0.1 σ = 0.1 . Error bars represent one standard error of the 8 independent experiments per point.
More importantly, both models exhibit non-monotonic long-horizon performance as the training CoT budget increases: the error remains relatively low at small budgets, grows rapidly with inference depth at intermediate budgets, and then abruptly transitions to stable inference at larger budgets. This pattern suggests that the non-monotonicity and phase-transition-like behavior predicted in § 5.3 persist in more complex attention models.
Beyond the overall non-monotonicity described above, Figure 2 A shows a relatively sharp change within the failure region of linear attention. This is consistent with our finding in § 5.2 that overthinking takes two distinct forms: error accumulation and error amplification. For softmax attention, the corresponding change in Figure 2 B is more gradual, so the failure region is not clearly divided into these two regimes. To understand this, we write the state update for a fixed context Q Q Q as
w ^ t + 1 = F Q ( w ^ t ) : = w ^ t + Δ θ ( Q , w ^ t ) . (29) \hat{w}_{t+1} = F_Q(\hat{w}_t) := \hat{w}_t + \Delta_\theta(Q,\hat{w}_t). \tag*{(29)} w ^ t + 1 = F Q ( w ^ t ) := w ^ t + Δ θ ( Q , w ^ t ) . (29)
If the current state contains a small perturbation δ t \delta_t δ t , its one-step evolution can be linearized as
δ t + 1 : = F Q ( w ^ t + δ t ) − F Q ( w ^ t ) ≃ J t δ t , J t : = ∂ F Q ( w ) ∂ w ∣ w = w ^ t . (30) \delta_{t+1} := F_Q(\hat{w}_t + \delta_t) - F_Q(\hat{w}_t) \simeq J_t\delta_t,\qquad J_t := \left.\frac{\partial F_Q(w)}{\partial w}\right|_{w=\hat{w}_t}. \tag*{(30)} δ t + 1 := F Q ( w ^ t + δ t ) − F Q ( w ^ t ) ≃ J t δ t , J t := ∂ w ∂ F Q ( w ) w = w ^ t . (30)
Here, J t J_t J t describes the one-step evolution of a small state perturbation. For linear attention, the Jacobian is constant throughout inference for a fixed context. For softmax attention, it depends on the current state and changes along the inference trajectory. More generally, in nonlinear architectures, error propagation can vary along a single inference trajectory.
Conclusion
We studied how finite teacher CoT affects test-time reasoning and showed that finite trajectories can teach a GD update beyond the training horizon. When GD is not fully recovered, the model exhibits bounded error or two distinct forms of overthinking: polynomial error accumulation and exponential error amplification. In particular, with short contexts, increasing the training CoT budget can temporarily worsen long-horizon performance before ultimately recovering GD. Experiments with fully trained linear and softmax attention further reproduce these qualitative behaviors beyond the effective model. These results offer practical guidance for designing training CoT, while extending the theory to more complex models and tasks remains an important direction for future work.
Reproducibility Statement
Detailed derivations are provided in the appendices. Code for reproducing the numerical experiments is available at https://github.com/taka255/theory_of_cot_in_training .
AI Use Statement
Generative AI tools assisted with manuscript drafting, editing, translation, paper organization, numerical code, and the exploration and checking of mathematical derivations. All material was reviewed and verified by the authors, who take responsibility for the final manuscript.
Acknowledgments and Disclosure of Funding
K.T. was supported by JST BOOST NAIS Grant Number JPMJBS2418. C.P. is supported by an NSF CAREER Award (IIS-2239780), DARPA grants DIAL-FP-038 and AIQ-HR00112520041, the Simons Collaboration on the Physics of Learning and Neural Computation, and the William F. Milton Fund from Harvard University. This work has been made possible in part by a gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for the Study of Natural and Artificial Intelligence. The authors declare no competing interests.
Derivation of the Effective Parameterization
In this section, we explain the rationale behind the parameter simplification of the effective model in § 3.3 .
Readout-relevant blocks. Write
V : = W V , W : = W K ⊤ W Q , (31) V := W_V,\qquad W := W_K^\top W_Q, \tag*{(31)} V := W V , W := W K ⊤ W Q , (31)
and partition both matrices into blocks of dimensions ( D , 1 , D , 1 ) (D,1,D,1) ( D , 1 , D , 1 ) :
V = ( V 11 V 12 V 13 V 14 V 21 V 22 V 23 V 24 V 31 V 32 V 33 V 34 V 41 V 42 V 43 V 44 ) , W = ( W 11 W 12 W 13 W 14 W 21 W 22 W 23 W 24 W 31 W 32 W 33 W 34 W 41 W 42 W 43 W 44 ) . (32) V=\begin{pmatrix}
V_{11} & V_{12} & V_{13} & V_{14}\\
V_{21} & V_{22} & V_{23} & V_{24}\\
V_{31} & V_{32} & V_{33} & V_{34}\\
V_{41} & V_{42} & V_{43} & V_{44}
\end{pmatrix},\qquad
W=\begin{pmatrix}
W_{11} & W_{12} & W_{13} & W_{14}\\
W_{21} & W_{22} & W_{23} & W_{24}\\
W_{31} & W_{32} & W_{33} & W_{34}\\
W_{41} & W_{42} & W_{43} & W_{44}
\end{pmatrix}. \tag*{(32)} V = V 11 V 21 V 31 V 41 V 12 V 22 V 32 V 42 V 13 V 23 V 33 V 43 V 14 V 24 V 34 V 44 , W = W 11 W 21 W 31 W 41 W 12 W 22 W 32 W 42 W 13 W 23 W 33 W 43 W 14 W 24 W 34 W 44 . (32)
Here every block has the conformable dimension determined by its row and column; in particular, V 32 V_{32} V 32 , V 34 V_{34} V 34 , W 14 W_{14} W 14 , W 34 W_{34} W 34 are column vectors, and W 23 W_{23} W 23 , W 43 W_{43} W 43 are row vectors.
For notational simplicity, suppress the task and step indices and write a context token and the state token as
c l : = ( x l y l 0 D 0 ) , z ( s ) : = ( 0 D 0 s 1 ) , E = ( c 1 , … , c L , z ( s ) ) . (33) c_l := \begin{pmatrix}x_l\\y_l\\\mathbf{0}_D\\0\end{pmatrix},\qquad
z^{(s)} := \begin{pmatrix}\mathbf{0}_D\\0\\s\\1\end{pmatrix},\qquad
E=(c_1,\ldots,c_L,z^{(s)}). \tag*{(33)} c l := x l y l 0 D 0 , z ( s ) := 0 D 0 s 1 , E = ( c 1 , … , c L , z ( s ) ) . (33)
The state readout selects only the third block row of V V V . Moreover, the query z ( s ) z(s) z ( s ) has support only in its third and fourth blocks, so only the third and fourth block columns of W W W enter the attention scores. Direct multiplication gives
Readout ( Atten ( E ; θ ) ) = s + 1 L ( V 31 X + V 32 y ) T [ X T ( W 13 s + W 14 ) + y ( W 23 s + W 24 ) ] + 1 L ( V 33 s + V 34 ) [ s T W 33 s + s T W 34 + W 43 s + W 44 ] . (34) \operatorname{Readout}(\operatorname{Atten}(E;\theta))=s+\frac{1}{L}\left(V_{31}X+V_{32}y\right)^{\mathsf{T}}\left[X^{\mathsf{T}}\left(W_{13}s+W_{14}\right)+y\left(W_{23}s+W_{24}\right)\right]+\frac{1}{L}\left(V_{33}s+V_{34}\right)\left[s^{\mathsf{T}}W_{33}s+s^{\mathsf{T}}W_{34}+W_{43}s+W_{44}\right]. \tag*{(34)} Readout ( Atten ( E ; θ )) = s + L 1 ( V 31 X + V 32 y ) T [ X T ( W 13 s + W 14 ) + y ( W 23 s + W 24 ) ] + L 1 ( V 33 s + V 34 ) [ s T W 33 s + s T W 34 + W 43 s + W 44 ] . (34)
Consequently, all blocks outside the third block row of V V V , and the first two block columns of W W W , are exactly irrelevant to the state readout. They may be arbitrary, which gives the ∗ * ∗ blocks in Equation (8) .
Consequences of rotational symmetry. The data distribution is rotationally symmetric in the feature space. Motivated by this symmetry, we assume that the fixed blocks do not introduce preferred directions. The blocks V 32 V_{32} V 32 , V 34 V_{34} V 34 , W 14 W_{14} W 14 , W 34 W_{34} W 34 would otherwise introduce fixed vectors in R D \mathbb{R}^{D} R D , while W 23 W_{23} W 23 , W 43 W_{43} W 43 would select fixed directions from the state. We therefore set
V 32 = V 34 = W 14 = W 34 = 0 D , W 23 = W 43 = 0 D T . (35) V_{32}=V_{34}=W_{14}=W_{34}=0_{D},\qquad W_{23}=W_{43}=0_{D}^{\mathsf{T}}. \tag*{(35)} V 32 = V 34 = W 14 = W 34 = 0 D , W 23 = W 43 = 0 D T . (35)
For the same reason, we take the fixed square blocks to be proportional to I D I_D I D , while leaving W 13 = A W_{13}=A W 13 = A unrestricted. Thus,
V 31 = a I D , V 33 = b I D , W 33 = d I D , W 24 = c , W 44 = e . (36) V_{31}=aI_D,\qquad V_{33}=bI_D,\qquad W_{33}=dI_D,\qquad W_{24}=c,\qquad W_{44}=e. \tag*{(36)} V 31 = a I D , V 33 = b I D , W 33 = d I D , W 24 = c , W 44 = e . (36)
Substitution into Equation (A.4) gives
Readout ( Atten ( E ; θ ) ) = s + a L X ( X T A s + c y ) + b L s ( d ∥ s ∥ 2 + e ) . (37) \operatorname{Readout}(\operatorname{Atten}(E;\theta))=s+\frac{a}{L}X\left(X^{\mathsf{T}}As+cy\right)+\frac{b}{L}s\left(d\lVert s\rVert^2+e\right). \tag*{(37)} Readout ( Atten ( E ; θ )) = s + L a X ( X T A s + cy ) + L b s ( d ∥ s ∥ 2 + e ) . (37)
Scale convention and the label coefficient. The parameters in Equation (A.7) appear only through the products a A aA a A , a c ac a c , b d bd b d , and b e be b e . We fix this scalar gauge by absorbing a a a into A A A and c c c , and set a = 1 a=1 a = 1 . The value of b b b becomes irrelevant after the state-only terms are removed below; we choose b = 1 b=1 b = 1 , giving V 31 = V 33 = I D V_{31}=V_{33}=I_D V 31 = V 33 = I D .
The scalar c c c need not be fixed as an additional assumption. If it is included in the convex learning problem, the transition from s μ , 0 = 0 D s_{\mu,0}=0_D s μ , 0 = 0 D satisfies
s ^ μ , 1 = c L X μ y μ , s μ , 1 = η L X μ y μ . (38) \hat{s}_{\mu,1}=\frac{c}{L}X_{\mu}y_{\mu},\qquad s_{\mu,1}=\frac{\eta}{L}X_{\mu}y_{\mu}. \tag*{(38)} s ^ μ , 1 = L c X μ y μ , s μ , 1 = L η X μ y μ . (38)
The teacher parameters interpolate all training transitions, so the λ → 0 \lambda\to0 λ → 0 solution has zero training error. Equation (A.8) then requires ( c − η ) X μ y μ = 0 D (c-\eta)X_{\mu}y_{\mu}=0_D ( c − η ) X μ y μ = 0 D . Since X μ y μ ≠ 0 D X_{\mu}y_{\mu}\ne0_D X μ y μ = 0 D almost surely, every zero-loss solution has
c = η . (39) c=\eta. \tag*{(39)} c = η . (39)
Thus fixing this scalar from the outset entails no loss of generality for the λ → 0 \lambda\to0 λ → 0 results.
Excluding context-free inference. The last term of Equation (A.7) depends only on s s s and is independent of the context ( X , y ) (X,y) ( X , y ) . We therefore set
d = e = 0 (40) d=e=0 \tag*{(40)} d = e = 0 (40)
to exclude context-independent state updates. Combining Equations (A.5), (A.9), and (A.10) yields
V = ( ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ I D 0 D I D 0 D ∗ ∗ ∗ ∗ ) , W = ( ∗ ∗ A 0 D ∗ ∗ 0 D T η ∗ ∗ 0 D × D 0 D ∗ ∗ 0 D 0 ) . (41) V=\begin{pmatrix}
* & * & * & *\\
* & * & * & *\\
I_D & 0_D & I_D & 0_D\\
* & * & * & *
\end{pmatrix},
\qquad
W=\begin{pmatrix}
* & * & A & 0_D\\
* & * & 0_D^{\mathsf{T}} & \eta\\
* & * & 0_{D\times D} & 0_D\\
* & * & 0_D & 0
\end{pmatrix}. \tag*{(41)} V = ∗ ∗ I D ∗ ∗ ∗ 0 D ∗ ∗ ∗ I D ∗ ∗ ∗ 0 D ∗ , W = ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ A 0 D T 0 D × D 0 D 0 D η 0 D 0 . (41)
The unrestricted attention output therefore reduces to
Readout ( Atten ( E ; θ ) ) = s + 1 L X ( X T A s + η y ) , (42) \operatorname{Readout}(\operatorname{Atten}(E;\theta))=s+\frac{1}{L}X\left(X^{\mathsf{T}}As+\eta y\right), \tag*{(42)} Readout ( Atten ( E ; θ )) = s + L 1 X ( X T A s + η y ) , (42)
which is Equation (9) . In particular, A = − η I D A=-\eta I_D A = − η I D recovers the teacher GD update exactly.
Summary of the Parameter Regimes
Table 1 summarizes the finite-time and long-time behavior in every open region of the ( α , φ ) (\alpha,\varphi) ( α , φ ) plane. The two boundaries for 0 < α < 1 0 < \alpha< 1 0 < α < 1 are derived in Propositions E.6 and E.7.
Table 1. Summary of the parameter regimes.
The α > 1 \alpha> 1 α > 1 , φ > 1 \varphi> 1 φ > 1 Case
In this section, we derive the finite-depth generalization error in the GD-recovery regime of Result 4.1, especially in the α > 1 \alpha> 1 α > 1 case. The projected-GD error is evaluated separately in Appendix D. We write the task and inference covariances as
H μ : = X μ X μ T L , H i n : = X i n ( X i n ) T L . (43) \mathbf{H}_{\mu} := \frac{\mathbf{X}_{\mu}\mathbf{X}_{\mu}^{\mathsf{T}}}{L}, \qquad\mathbf{H}^{\mathrm{in}} := \frac{\mathbf{X}^{\mathrm{in}}(\mathbf{X}^{\mathrm{in}})^{\mathsf{T}}}{L}. \tag*{(43)} H μ := L X μ X μ T , H in := L X in ( X in ) T . (43)
First, we verify that the GD parameters satisfy L e f f ( A ⋆ ) = 0 \mathcal{L}_{\mathrm{eff}}(\mathbf{A}_{\star}) = 0 L eff ( A ⋆ ) = 0 . This is a direct substitution into the model update, after which only uniqueness remains to be shown.
Proposition C.1 (The GD parameters satisfy L e f f = 0 \mathcal{L}_{\mathrm{eff}} = 0 L eff = 0 ). Suppose λ → 0 \lambda\to0 λ → 0 . For every α > 0 \alpha> 0 α > 0 , the parameter A ⋆ = − η I D \mathbf{A}_{\star} = -\eta\mathbf{I}_{D} A ⋆ = − η I D satisfies
L e f f ( A ⋆ ) = 1 M K ∑ μ = 1 M ∑ k = 0 K − 1 ∥ s ^ μ , k + 1 − s μ , k + 1 ∥ 2 2 ∣ A = A ⋆ = 0. (44) \mathcal{L}_{\mathrm{eff}}(\mathbf{A}_{\star}) = \left.\frac{1}{MK}\sum_{\mu=1}^{M}\sum_{k=0}^{K-1}\left\lVert\hat{\mathbf{s}}_{\mu,k+1} - \mathbf{s}_{\mu,k+1}\right\rVert_{2}^{2}\right|_{\mathbf{A}=\mathbf{A}_{\star}} = 0. \tag*{(44)} L eff ( A ⋆ ) = M K 1 μ = 1 ∑ M k = 0 ∑ K − 1 ∥ s ^ μ , k + 1 − s μ , k + 1 ∥ 2 2 A = A ⋆ = 0. (44)
Proof. Substituting A ⋆ = − η I D \mathbf{A}_{\star} = -\eta\mathbf{I}_{D} A ⋆ = − η I D into the model update in (9) gives
s ^ μ , k + 1 = s μ , k + 1 L X μ [ − η X μ T s μ , k + η y μ ] (45) \hat{\mathbf{s}}_{\mu,k+1} = \mathbf{s}_{\mu,k} + \frac{1}{L}\mathbf{X}_{\mu}\left[-\eta\mathbf{X}_{\mu}^{\mathsf{T}}\mathbf{s}_{\mu,k} + \eta\mathbf{y}_{\mu}\right] \tag*{(45)} s ^ μ , k + 1 = s μ , k + L 1 X μ [ − η X μ T s μ , k + η y μ ] (45)
= s μ , k − η L X μ ( X μ T s μ , k − y μ ) (46) = \mathbf{s}_{\mu,k} - \frac{\eta}{L}\mathbf{X}_{\mu}\left(\mathbf{X}_{\mu}^{\mathsf{T}}\mathbf{s}_{\mu,k} - \mathbf{y}_{\mu}\right) \tag*{(46)} = s μ , k − L η X μ ( X μ T s μ , k − y μ ) (46)
= s μ , k + 1 , (47) = \mathbf{s}_{\mu,k+1}, \tag*{(47)} = s μ , k + 1 , (47)
where the last equality is the teacher update in Equation (3.2). Substituting Equation (C.5) into Equation (3.10) proves Equation (C.2) in the limit λ → 0 \lambda\to0 λ → 0 .
Proposition C.1 establishes that L e f f ( A ⋆ ) = 0 \mathcal{L}_{\mathrm{eff}}(\mathbf{A}_{\star}) = 0 L eff ( A ⋆ ) = 0 . We now assume α > 1 \alpha> 1 α > 1 and show that A ⋆ \mathbf{A}_{\star} A ⋆ is the unique matrix satisfying L e f f ( A ) = 0 \mathcal{L}_{\mathrm{eff}}(\mathbf{A}) = 0 L eff ( A ) = 0 when φ > 1 \varphi> 1 φ > 1 . Because every task covariance is then invertible, the proof reduces to the rank of one matrix containing all training states.
Proposition C.2 (Uniqueness for full-rank contexts). Suppose α > 1 \alpha> 1 α > 1 , φ > 1 \varphi> 1 φ > 1 , and λ → 0 \lambda\to0 λ → 0 . Then A ⋆ \mathbf{A}_{\star} A ⋆ is the unique solution that satisfies L e f f ( A ) = 0 \mathcal{L}_{\mathrm{eff}}(\mathbf{A}) = 0 L eff ( A ) = 0 , and thus
A ^ = − η I D . (48) \hat{\mathbf{A}} = -\eta\mathbf{I}_{D}. \tag*{(48)} A ^ = − η I D . (48)
Proof. Subtracting the teacher update in Equation (2) from the model update in Equation (9) gives
s ^ μ , k + 1 − s μ , k + 1 = H μ ( A + η I D ) s μ , k . (49) \hat{s}_{\mu,k+1}-s_{\mu,k+1}=\mathbf{H}_{\mu}(\mathbf{A}+\eta\mathbf{I}_{D})s_{\mu,k}. \tag*{(49)} s ^ μ , k + 1 − s μ , k + 1 = H μ ( A + η I D ) s μ , k . (49)
Since s μ , 0 = 0 s_{\mu,0}=0 s μ , 0 = 0 , the k = 0 k=0 k = 0 term in L e f f ( A ) \mathcal{L}_{\mathrm{eff}}(\mathbf{A}) L eff ( A ) vanishes for every A \mathbf{A} A . Equation (C.7) therefore shows that L e f f ( A ) = 0 \mathcal{L}_{\mathrm{eff}}(\mathbf{A})=0 L eff ( A ) = 0 requires
H μ ( A + η I D ) s μ , k = 0 D ( μ = 1 , … , M , k = 1 , … , K − 1 ) . (50) \mathbf{H}_{\mu}(\mathbf{A}+\eta\mathbf{I}_{D})s_{\mu,k}=\mathbf{0}_{D}\qquad(\mu=1,\ldots,M,\ k=1,\ldots,K-1). \tag*{(50)} H μ ( A + η I D ) s μ , k = 0 D ( μ = 1 , … , M , k = 1 , … , K − 1 ) . (50)
Because α > 1 \alpha>1 α > 1 , every H μ \mathbf{H}_{\mu} H μ is invertible almost surely. Collect all noninitial teacher states in
S : = ( s 1 , 1 , … , s 1 , K − 1 , … , s M , 1 , … , s M , K − 1 ) . (51) \mathbf{S}:=(s_{1,1},\ldots,s_{1,K-1},\ldots,s_{M,1},\ldots,s_{M,K-1}). \tag*{(51)} S := ( s 1 , 1 , … , s 1 , K − 1 , … , s M , 1 , … , s M , K − 1 ) . (51)
Then Equation (C.8) is equivalent to
L e f f ( A ) = 0 ⟺ ( A + η I D ) S = 0. (52) \mathcal{L}_{\mathrm{eff}}(\mathbf{A})=0\quad\Longleftrightarrow\quad(\mathbf{A}+\eta\mathbf{I}_{D})\mathbf{S}=\mathbf{0}. \tag*{(52)} L eff ( A ) = 0 ⟺ ( A + η I D ) S = 0 . (52)
The teacher recursion in Equation (2) yields
s μ , k = 1 L q k ( H μ ) X μ y μ , (53) s_{\mu,k}=\frac{1}{L}q_k(\mathbf{H}_{\mu})\mathbf{X}_{\mu}\mathbf{y}_{\mu}, \tag*{(53)} s μ , k = L 1 q k ( H μ ) X μ y μ , (53)
where q k ( x ) q_k(x) q k ( x ) is defined in Equation (21) . Write
H μ = U μ diag ( x μ , 1 , … , x μ , D ) U μ T . (54) \mathbf{H}_{\mu}=\mathbf{U}_{\mu}\operatorname{diag}(x_{\mu,1},\ldots,x_{\mu,D})\mathbf{U}_{\mu}^{\mathsf{T}}. \tag*{(54)} H μ = U μ diag ( x μ , 1 , … , x μ , D ) U μ T . (54)
Equation (C.11) then gives
U μ T ( s μ , 1 , … , s μ , K − 1 ) = diag ( 1 L U μ T X μ y μ ) ( q 1 ( x μ , 1 ) ⋯ q K − 1 ( x μ , 1 ) ⋮ ⋮ q 1 ( x μ , D ) ⋯ q K − 1 ( x μ , D ) ) . (55) \mathbf{U}_{\mu}^{\mathsf{T}}(s_{\mu,1},\ldots,s_{\mu,K-1})=\operatorname{diag}\left(\frac{1}{L}\mathbf{U}_{\mu}^{\mathsf{T}}\mathbf{X}_{\mu}\mathbf{y}_{\mu}\right)
\begin{pmatrix}
q_1(x_{\mu,1}) & \cdots& q_{K-1}(x_{\mu,1})\\
\vdots& & \vdots\\
q_1(x_{\mu,D}) & \cdots& q_{K-1}(x_{\mu,D})
\end{pmatrix}. \tag*{(55)} U μ T ( s μ , 1 , … , s μ , K − 1 ) = diag ( L 1 U μ T X μ y μ ) q 1 ( x μ , 1 ) ⋮ q 1 ( x μ , D ) ⋯ ⋯ q K − 1 ( x μ , 1 ) ⋮ q K − 1 ( x μ , D ) . (55)
The polynomial q k q_k q k has degree k − 1 k-1 k − 1 and leading coefficient ( − 1 ) k − 1 η k (-1)^{k-1}\eta^k ( − 1 ) k − 1 η k . Therefore, the determinant of the first K − 1 K-1 K − 1 rows of the polynomial matrix in Equation (C.13) is
det [ q k ( x μ , i ) ] i , k = 1 K − 1 = [ ∏ k = 1 K − 1 ( − 1 ) k − 1 η k ] ∏ 1 ≤ i < j ≤ K − 1 ( x μ , j − x μ , i ) . (56) \det[q_k(x_{\mu,i})]_{i,k=1}^{K-1}=\left[\prod_{k=1}^{K-1}(-1)^{k-1}\eta^k\right]\prod_{1\le i<j\le K-1}(x_{\mu,j}-x_{\mu,i}). \tag*{(56)} det [ q k ( x μ , i ) ] i , k = 1 K − 1 = [ k = 1 ∏ K − 1 ( − 1 ) k − 1 η k ] 1 ≤ i < j ≤ K − 1 ∏ ( x μ , j − x μ , i ) . (56)
The positive Gaussian-Wishart eigenvalues are distinct almost surely, and every entry of U μ T X μ y μ / L \mathbf{U}_{\mu}^{\mathsf{T}}\mathbf{X}_{\mu}\mathbf{y}_{\mu}/L U μ T X μ y μ / L is nonzero almost surely. Hence Equation (C.14) is nonzero, and each task contributes exactly K − 1 K-1 K − 1 linearly independent states. Because the tasks are independent and Gaussian, their state spans are independent random subspaces and are in general position almost surely. Consequently,
rank S = min { D , M ( K − 1 ) } , rank S D ⟶ min { 1 , φ } . (57) \operatorname{rank}\mathbf{S}=\min\{D,M(K-1)\},\qquad\frac{\operatorname{rank}\mathbf{S}}{D}\longrightarrow\min\{1,\varphi\}. \tag*{(57)} rank S = min { D , M ( K − 1 )} , D rank S ⟶ min { 1 , φ } . (57)
When φ > 1 \varphi>1 φ > 1 , Equation (C.15) gives rank S = D \operatorname{rank}\mathbf{S}=D rank S = D . Equation (C.10) then gives A = − η I D = A ⋆ \mathbf{A}=-\eta\mathbf{I}_{D}=\mathbf{A}_{\star} A = − η I D = A ⋆ . Hence A ⋆ \mathbf{A}_{\star} A ⋆ is the unique matrix satisfying L e f f ( A ) = 0 \mathcal{L}_{\mathrm{eff}}(\mathbf{A})=0 L eff ( A ) = 0 , and the λ → 0 \lambda\to0 λ → 0 estimator obeys A ^ = − η I D \hat{\mathbf{A}}=-\eta\mathbf{I}_{D} A ^ = − η I D .
Propositions C.1 and C.2 establish GD recovery for α > 1 \alpha>1 α > 1 and φ > 1 \varphi>1 φ > 1 . Finally, we compute the generalization error after GD recovery. This calculation applies whenever A ^ = − η I D \hat{\mathbf{A}}=-\eta\mathbf{I}_{D} A ^ = − η I D .
Proposition C.3 (Generalization error after GD recovery). Suppose λ → 0 \lambda\to0 λ → 0 and A ^ = − η I D \hat{\mathbf{A}}=-\eta\mathbf{I}_{D} A ^ = − η I D . For every fixed test-time depth t t t ,
E ( t ) = E G D ( t ) = ⟨ ( 1 − x q t ) 2 ⟩ α + σ 2 α ⟨ x q t 2 ⟩ α . (58) \mathcal{E}(t)=\mathcal{E}_{\mathrm{GD}}(t)=\left\langle(1-xq_t)^2\right\rangle_{\alpha}+\frac{\sigma^2}{\alpha}\left\langle xq_t^2\right\rangle_{\alpha}. \tag*{(58)} E ( t ) = E GD ( t ) = ⟨ ( 1 − x q t ) 2 ⟩ α + α σ 2 ⟨ x q t 2 ⟩ α . (58)
Proof. Define
Q t : = η ∑ j = 0 t − 1 ( I D + H i n A ^ ) j . (59) \mathbf{Q}_t:=\eta\sum_{j=0}^{t-1}(\mathbf{I}_{D}+\mathbf{H}^{\mathrm{in}}\hat{\mathbf{A}})^j. \tag*{(59)} Q t := η j = 0 ∑ t − 1 ( I D + H in A ^ ) j . (59)
Iterating the learned update in Equation (13) and substituting the test labels gives
w ^ t − w i n = ( Q t H i n − I D ) w i n + 1 L Q t X i n e i n . (60) \widehat{w}_t-w^{\mathrm{in}} = \left(Q_tH^{\mathrm{in}}-I_D\right)w^{\mathrm{in}}+\frac{1}{L}Q_tX^{\mathrm{in}}e^{\mathrm{in}}. \tag*{(60)} w t − w in = ( Q t H in − I D ) w in + L 1 Q t X in e in . (60)
The two terms in Equation (C.18) are conditionally independent and centered. Their covariances give
E [ ∥ w ^ t − w i n ∥ 2 2 ∣ A ^ , X i n ] = 1 − 2 D tr ( Q t H i n ) + 1 D ∥ Q t H i n ∥ F 2 + σ 2 L tr ( Q t H i n Q t T ) . (61) \mathbb{E}\left[\left\|\widehat{w}_t-w^{\mathrm{in}}\right\|_2^2\mid\widehat{A},X^{\mathrm{in}}\right]=1-\frac{2}{D}\operatorname{tr}\left(Q_tH^{\mathrm{in}}\right)+\frac{1}{D}\left\|Q_tH^{\mathrm{in}}\right\|_{\mathrm{F}}^2+\frac{\sigma^2}{L}\operatorname{tr}\left(Q_tH^{\mathrm{in}}Q_t^{\mathsf{T}}\right). \tag*{(61)} E [ w t − w in 2 2 ∣ A , X in ] = 1 − D 2 tr ( Q t H in ) + D 1 Q t H in F 2 + L σ 2 tr ( Q t H in Q t T ) . (61)
Substituting A ^ = − η I D \widehat{A}=-\eta I_D A = − η I D into Equation (C.17) gives
Q t = η ∑ j = 0 t − 1 ( I D − η H i n ) j = q t ( H i n ) . (62) Q_t=\eta\sum_{j=0}^{t-1}\left(I_D-\eta H^{\mathrm{in}}\right)^j=q_t\left(H^{\mathrm{in}}\right). \tag*{(62)} Q t = η j = 0 ∑ t − 1 ( I D − η H in ) j = q t ( H in ) . (62)
Let x 1 , D , … , x D , D x_{1,D},\ldots,x_{D,D} x 1 , D , … , x D , D be the eigenvalues of H i n H^{\mathrm{in}} H in . For fixed t t t , q t q_t q t is a polynomial, so the Marchenko–Pastur law applies term by term in Equation (C.19). Using Equation (C.20),
1 D tr ( Q t H i n ) = 1 D ∑ i = 1 D x i , D q t ( x i , D ) ⟶ ⟨ x q t ⟩ α . (63) \frac{1}{D}\operatorname{tr}\left(Q_tH^{\mathrm{in}}\right)=\frac{1}{D}\sum_{i=1}^{D}x_{i,D}q_t(x_{i,D})\longrightarrow\langle xq_t\rangle_{\alpha}. \tag*{(63)} D 1 tr ( Q t H in ) = D 1 i = 1 ∑ D x i , D q t ( x i , D ) ⟶ ⟨ x q t ⟩ α . (63)
1 D ∥ Q t H i n ∥ F 2 = 1 D tr [ ( H i n ) 2 q t ( H i n ) 2 ] (64) \frac{1}{D}\left\|Q_tH^{\mathrm{in}}\right\|_{\mathrm{F}}^2=\frac{1}{D}\operatorname{tr}\left[\left(H^{\mathrm{in}}\right)^2q_t\left(H^{\mathrm{in}}\right)^2\right] \tag*{(64)} D 1 Q t H in F 2 = D 1 tr [ ( H in ) 2 q t ( H in ) 2 ] (64)
= 1 D ∑ i = 1 D x i , D 2 q t ( x i , D ) 2 ⟶ ⟨ x 2 q t 2 ⟩ α . (65) =\frac{1}{D}\sum_{i=1}^{D}x_{i,D}^2q_t(x_{i,D})^2\longrightarrow\langle x^2q_t^2\rangle_{\alpha}. \tag*{(65)} = D 1 i = 1 ∑ D x i , D 2 q t ( x i , D ) 2 ⟶ ⟨ x 2 q t 2 ⟩ α . (65)
σ 2 L tr ( Q t H i n Q t T ) = σ 2 D L 1 D tr [ H i n q t ( H i n ) 2 ] (66) \frac{\sigma^2}{L}\operatorname{tr}\left(Q_tH^{\mathrm{in}}Q_t^{\mathsf{T}}\right)=\sigma^2\frac{D}{L}\frac{1}{D}\operatorname{tr}\left[H^{\mathrm{in}}q_t\left(H^{\mathrm{in}}\right)^2\right] \tag*{(66)} L σ 2 tr ( Q t H in Q t T ) = σ 2 L D D 1 tr [ H in q t ( H in ) 2 ] (66)
= σ 2 D L 1 D ∑ i = 1 D x i , D q t ( x i , D ) 2 ⟶ σ 2 α ⟨ x q t 2 ⟩ α . (67) =\sigma^2\frac{D}{L}\frac{1}{D}\sum_{i=1}^{D}x_{i,D}q_t(x_{i,D})^2\longrightarrow\frac{\sigma^2}{\alpha}\langle xq_t^2\rangle_{\alpha}. \tag*{(67)} = σ 2 L D D 1 i = 1 ∑ D x i , D q t ( x i , D ) 2 ⟶ α σ 2 ⟨ x q t 2 ⟩ α . (67)
Substitution into Equation (C.19) gives
E G D ( t ) = 1 − 2 ⟨ x q t ⟩ α + ⟨ x 2 q t 2 ⟩ α + σ 2 α ⟨ x q t 2 ⟩ α (68) \mathcal{E}_{\mathrm{GD}}(t)=1-2\langle xq_t\rangle_{\alpha}+\langle x^2q_t^2\rangle_{\alpha}+\frac{\sigma^2}{\alpha}\langle xq_t^2\rangle_{\alpha} \tag*{(68)} E GD ( t ) = 1 − 2 ⟨ x q t ⟩ α + ⟨ x 2 q t 2 ⟩ α + α σ 2 ⟨ x q t 2 ⟩ α (68)
= ⟨ ( 1 − x q t ) 2 ⟩ α + σ 2 α ⟨ x q t 2 ⟩ α . (69) =\left\langle(1-xq_t)^2\right\rangle_{\alpha}+\frac{\sigma^2}{\alpha}\langle xq_t^2\rangle_{\alpha}. \tag*{(69)} = ⟨ ( 1 − x q t ) 2 ⟩ α + α σ 2 ⟨ x q t 2 ⟩ α . (69)
which proves Equation (C.16).
This completes the α > 1 \alpha>1 α > 1 and φ > 1 \varphi>1 φ > 1 case.
The > 1 >1 > 1 , 0 < < 1 0<<1 0 << 1 Case
In this section, we compute the generalization error for α > 1 \alpha>1 α > 1 and 0 < φ < 1 0<\varphi<1 0 < φ < 1 . First, we state the finite-time error and derive both the learned matrix and its risk.
Proposition D.1 (Finite-time error of projected GD). Suppose α > 1 \alpha>1 α > 1 , 0 < φ < 1 0<\varphi<1 0 < φ < 1 , and λ → 0 \lambda\to0 λ → 0 . For every fixed test-time depth t t t , the quantities defined in Equation (21) give
E ( t ) = 1 − φ + φ ⟨ ( 1 − x q t ) 2 ⟩ α / φ + φ [ 2 ( 1 − φ ) + σ 2 ] α ⟨ x q t 2 ⟩ α / φ − 2 ( 1 − φ ) α κ 1 , t + ( 1 − φ ) ( 1 − φ + σ 2 ) α 2 κ 2 , t + 1 − φ α 2 κ 1 , t 2 . (70) \mathcal{E}(t)=1-\varphi+\varphi\left\langle(1-xq_t)^2\right\rangle_{\alpha/\varphi}+\frac{\varphi\left[2(1-\varphi)+\sigma^2\right]}{\alpha}\left\langle xq_t^2\right\rangle_{\alpha/\varphi}
-\frac{2(1-\varphi)}{\alpha}\kappa_{1,t}+\frac{(1-\varphi)(1-\varphi+\sigma^2)}{\alpha^2}\kappa_{2,t}+\frac{1-\varphi}{\alpha^2}\kappa_{1,t}^2. \tag*{(70)} E ( t ) = 1 − φ + φ ⟨ ( 1 − x q t ) 2 ⟩ α / φ + α φ [ 2 ( 1 − φ ) + σ 2 ] ⟨ x q t 2 ⟩ α / φ − α 2 ( 1 − φ ) κ 1 , t + α 2 ( 1 − φ ) ( 1 − φ + σ 2 ) κ 2 , t + α 2 1 − φ κ 1 , t 2 . (70)
Proof. Define the projector onto the training-state span:
P : = S S † . (71) P:=SS^\dagger. \tag*{(71)} P := S S † . (71)
Every noninitial training state is a column of S S S , so P s μ , k = s μ , k Ps_{\mu,k}=s_{\mu,k} P s μ , k = s μ , k for k = 1 , … , K − 1 k=1,\ldots,K-1 k = 1 , … , K − 1 . Using Equation (C.7),
( s ^ μ , k + 1 − s μ , k + 1 ) ∣ A = − η P = η H μ ( I D − P ) s μ , k = 0 D . (72) \left.(\widehat{s}_{\mu,k+1}-s_{\mu,k+1})\right|_{A=-\eta P}=\eta H_\mu(I_D-P)s_{\mu,k}=0_D. \tag*{(72)} ( s μ , k + 1 − s μ , k + 1 ) ∣ A = − η P = η H μ ( I D − P ) s μ , k = 0 D . (72)
The k = 0 k=0 k = 0 residual also vanishes because s μ , 0 = 0 D s_{\mu,0}=\mathbf{0}_D s μ , 0 = 0 D . Consequently,
L e f f ( − η P ) = λ η 2 D ∥ P ∥ F 2 = λ η 2 D tr P ⟶ 0 ( λ → 0 ) . (73) \mathcal{L}_{\mathrm{eff}}(-\eta\mathbf{P})=\frac{\lambda\eta^2}{D}\lVert\mathbf{P}\rVert_F^2=\frac{\lambda\eta^2}{D}\operatorname{tr}\mathbf{P}\longrightarrow0\qquad(\lambda\to0). \tag*{(73)} L eff ( − η P ) = D λ η 2 ∥ P ∥ F 2 = D λ η 2 tr P ⟶ 0 ( λ → 0 ) . (73)
Multiplying Equation (C.10) by S † \mathbf{S}^{\dagger} S † gives
A P = − η P . (74) \mathbf{A}\mathbf{P}=-\eta\mathbf{P}. \tag*{(74)} AP = − η P . (74)
Every matrix satisfying Equation (D.5) obeys
A = − η P + A ( I D − P ) , (75) \mathbf{A}=-\eta\mathbf{P}+\mathbf{A}(\mathbf{I}_D-\mathbf{P}), \tag*{(75)} A = − η P + A ( I D − P ) , (75)
∥ A ∥ F 2 = η 2 tr P + ∥ A ( I D − P ) ∥ F 2 . (76) \lVert\mathbf{A}\rVert_F^2=\eta^2\operatorname{tr}\mathbf{P}+\lVert\mathbf{A}(\mathbf{I}_D-\mathbf{P})\rVert_F^2. \tag*{(76)} ∥ A ∥ F 2 = η 2 tr P + ∥ A ( I D − P ) ∥ F 2 . (76)
Because λ → 0 \lambda\to0 λ → 0 selects the minimum-Frobenius-norm matrix satisfying L e f f ( A ) = 0 \mathcal{L}_{\mathrm{eff}}(\mathbf{A})=0 L eff ( A ) = 0 , Equation (D.7) gives
A ^ = − η P . (77) \widehat{\mathbf{A}}=-\eta\mathbf{P}. \tag*{(77)} A = − η P . (77)
Let r : = M ( K − 1 ) r:=M(K-1) r := M ( K − 1 ) . Because 0 < φ < 1 0<\varphi<1 0 < φ < 1 , Equation (C.15) gives rank P = r \operatorname{rank}\mathbf{P}=r rank P = r and r / D → φ r/D\to\varphi r / D → φ . The inference data are independent of P \mathbf{P} P , so rotational invariance allows us to choose a basis in which
P = ( I r 0 0 0 ) , X i n = ( X 1 X 2 ) , B : = X 1 X 1 T L . (78) \mathbf{P}=
\begin{pmatrix}
\mathbf{I}_r & 0\\
0 & 0
\end{pmatrix},
\qquad
\mathbf{X}^{\mathrm{in}}=
\begin{pmatrix}
\mathbf{X}_1\\
\mathbf{X}_2
\end{pmatrix},
\qquad
\mathbf{B}:=\frac{\mathbf{X}_1\mathbf{X}_1^{\mathsf{T}}}{L}. \tag*{(78)} P = ( I r 0 0 0 ) , X in = ( X 1 X 2 ) , B := L X 1 X 1 T . (78)
where X 1 ∈ R r × L \mathbf{X}_1\in\mathbb{R}^{r\times L} X 1 ∈ R r × L and X 2 ∈ R ( D − r ) × L \mathbf{X}_2\in\mathbb{R}^{(D-r)\times L} X 2 ∈ R ( D − r ) × L are independent standard Gaussian matrices. Substituting A ^ = − η P \widehat{\mathbf{A}}=-\eta\mathbf{P} A = − η P into Equation (C.17) gives
Q t = q t ( H i n P ) . (79) \mathbf{Q}_t=q_t(\mathbf{H}^{\mathrm{in}}\mathbf{P}). \tag*{(79)} Q t = q t ( H in P ) . (79)
The identity
( H i n P ) j X i n = X i n [ ( X i n ) T P X i n L ] j (80) (\mathbf{H}^{\mathrm{in}}\mathbf{P})^j\mathbf{X}^{\mathrm{in}}
=
\mathbf{X}^{\mathrm{in}}
\left[
\frac{(\mathbf{X}^{\mathrm{in}})^{\mathsf{T}}\mathbf{P}\mathbf{X}^{\mathrm{in}}}{L}
\right]^j \tag*{(80)} ( H in P ) j X in = X in [ L ( X in ) T P X in ] j (80)
and the block decomposition in Equation (D.9) give
Q t X i n = X i n q t ( X 1 T X 1 L ) = ( q t ( B ) X 1 X 2 K t ) , (81) \mathbf{Q}_t\mathbf{X}^{\mathrm{in}}
=
\mathbf{X}^{\mathrm{in}}q_t\left(\frac{\mathbf{X}_1^{\mathsf{T}}\mathbf{X}_1}{L}\right)
=
\begin{pmatrix}
q_t(\mathbf{B})\mathbf{X}_1\\
\mathbf{X}_2\mathbf{K}_t
\end{pmatrix}, \tag*{(81)} Q t X in = X in q t ( L X 1 T X 1 ) = ( q t ( B ) X 1 X 2 K t ) , (81)
where we introduced
K t : = q t ( X 1 T X 1 L ) . (82) \mathbf{K}_t:=q_t\left(\frac{\mathbf{X}_1^{\mathsf{T}}\mathbf{X}_1}{L}\right). \tag*{(82)} K t := q t ( L X 1 T X 1 ) . (82)
Multiplying Equation (D.12) by ( X i n ) T / L (\mathbf{X}^{\mathrm{in}})^{\mathsf{T}}/L ( X in ) T / L gives
Q t H i n = ( B q t ( B ) q t ( B ) X 1 X 2 T / L X 2 X 1 T q t ( B ) / L X 2 K t X 2 T / L ) . (83) \mathbf{Q}_t\mathbf{H}^{\mathrm{in}}
=
\begin{pmatrix}
\mathbf{B}q_t(\mathbf{B}) & q_t(\mathbf{B})\mathbf{X}_1\mathbf{X}_2^{\mathsf{T}}/L\\
\mathbf{X}_2\mathbf{X}_1^{\mathsf{T}}q_t(\mathbf{B})/L & \mathbf{X}_2\mathbf{K}_t\mathbf{X}_2^{\mathsf{T}}/L
\end{pmatrix}. \tag*{(83)} Q t H in = ( B q t ( B ) X 2 X 1 T q t ( B ) / L q t ( B ) X 1 X 2 T / L X 2 K t X 2 T / L ) . (83)
We next average the X 2 \mathbf{X}_2 X 2 blocks in Equations (D.12) and (D.14) conditional on X 1 \mathbf{X}_1 X 1 . The matrix K t \mathbf{K}_t K t is symmetric and independent of X 2 \mathbf{X}_2 X 2 . For independent standard Gaussian rows z i \mathbf{z}_i z i and z j \mathbf{z}_j z j of X 2 \mathbf{X}_2 X 2 , Wick’s identity gives
E ( z i T K t z i ) = tr K t , (84) \mathbb{E}(\mathbf{z}_i^{\mathsf{T}}\mathbf{K}_t\mathbf{z}_i)=\operatorname{tr}\mathbf{K}_t, \tag*{(84)} E ( z i T K t z i ) = tr K t , (84)
E ( z i T K t z i ) 2 = 2 tr ( K t 2 ) + ( tr K t ) 2 , (85) \mathbb{E}(\mathbf{z}_i^{\mathsf{T}}\mathbf{K}_t\mathbf{z}_i)^2
=
2\operatorname{tr}(\mathbf{K}_t^2)+(\operatorname{tr}\mathbf{K}_t)^2, \tag*{(85)} E ( z i T K t z i ) 2 = 2 tr ( K t 2 ) + ( tr K t ) 2 , (85)
E ( z i T K t z j ) 2 = tr ( K t 2 ) ( i ≠ j ) . (86) \mathbb{E}(\mathbf{z}_i^{\mathsf{T}}\mathbf{K}_t\mathbf{z}_j)^2
=
\operatorname{tr}(\mathbf{K}_t^2)
\qquad(i\ne j). \tag*{(86)} E ( z i T K t z j ) 2 = tr ( K t 2 ) ( i = j ) . (86)
Summing the diagonal and off-diagonal row pairs in Equation (D.17) gives
E X 2 tr ( X 2 K t X 2 T ) = ( D − r ) tr K t , (87) \mathbb{E}_{\mathbf{X}_2}\operatorname{tr}(\mathbf{X}_2\mathbf{K}_t\mathbf{X}_2^{\mathsf{T}})
=
(D-r)\operatorname{tr}\mathbf{K}_t, \tag*{(87)} E X 2 tr ( X 2 K t X 2 T ) = ( D − r ) tr K t , (87)
E X 2 ∥ X 2 K t X 2 T ∥ F 2 = ( D − r ) ( D − r + 1 ) tr ( K t 2 ) + ( D − r ) ( tr K t ) 2 . (88) \mathbb{E}_{\mathbf{X}_2}\lVert\mathbf{X}_2\mathbf{K}_t\mathbf{X}_2^{\mathsf{T}}\rVert_F^2
=
(D-r)(D-r+1)\operatorname{tr}(\mathbf{K}_t^2)
+
(D-r)(\operatorname{tr}\mathbf{K}_t)^2. \tag*{(88)} E X 2 ∥ X 2 K t X 2 T ∥ F 2 = ( D − r ) ( D − r + 1 ) tr ( K t 2 ) + ( D − r ) ( tr K t ) 2 . (88)
The off-diagonal block in Equation (D.14) satisfies
E X 2 ∥ q t ( B ) X 1 X 2 T L ∥ F 2 = D − r L 2 tr [ q t ( B ) X 1 X 1 T q t ( B ) ] = D − r L tr [ B q t ( B ) 2 ] . (89) \mathbb{E}_{X_2}\left\|q_t(\mathbf{B})\frac{\mathbf{X}_1\mathbf{X}_2^{\mathsf T}}{L}\right\|_{\mathrm{F}}^2
= \frac{D-r}{L^2}\operatorname{tr}\left[q_t(\mathbf{B})\mathbf{X}_1\mathbf{X}_1^{\mathsf T}q_t(\mathbf{B})\right]
= \frac{D-r}{L}\operatorname{tr}\left[\mathbf{B}q_t(\mathbf{B})^2\right]. \tag*{(89)} E X 2 q t ( B ) L X 1 X 2 T F 2 = L 2 D − r tr [ q t ( B ) X 1 X 1 T q t ( B ) ] = L D − r tr [ B q t ( B ) 2 ] . (89)
The source response in Equation (D.12) satisfies
E X 2 ∥ Q t X i n ∥ F 2 = ∥ q t ( B ) X 1 ∥ F 2 + E X 2 ∥ X 2 K t ∥ F 2 (90) \mathbb{E}_{X_2}\left\|\mathbf{Q}_t\mathbf{X}^{\mathrm{in}}\right\|_{\mathrm{F}}^2
= \left\|q_t(\mathbf{B})\mathbf{X}_1\right\|_{\mathrm{F}}^2+\mathbb{E}_{X_2}\left\|\mathbf{X}_2\mathbf{K}_t\right\|_{\mathrm{F}}^2 \tag*{(90)} E X 2 Q t X in F 2 = ∥ q t ( B ) X 1 ∥ F 2 + E X 2 ∥ X 2 K t ∥ F 2 (90)
= L tr [ B q t ( B ) 2 ] + ( D − r ) tr ( K t 2 ) . (91) = L\operatorname{tr}\left[\mathbf{B}q_t(\mathbf{B})^2\right]+(D-r)\operatorname{tr}\left(\mathbf{K}_t^2\right). \tag*{(91)} = L tr [ B q t ( B ) 2 ] + ( D − r ) tr ( K t 2 ) . (91)
Substituting Equations (D.19), (D.20), and (D.22) into Equation (C.19) gives
E [ ∥ w ^ t − w i n ∥ 2 2 ∣ X 1 ] = 1 − 2 D [ tr ( B q t ( B ) ) + D − r L tr K t ] + 1 D tr [ B 2 q t ( B ) 2 ] + [ 2 ( D − r ) D L + σ 2 L ] tr [ B q t ( B ) 2 ] + ( D − r ) ( D − r + 1 + σ 2 D ) D L 2 tr ( K t 2 ) + D − r D L 2 ( tr K t ) 2 . (92) \begin{aligned}
\mathbb{E}\left[\left\|\widehat{\mathbf{w}}_t-\mathbf{w}^{\mathrm{in}}\right\|_2^2\mid\mathbf{X}_1\right]
=1-\frac{2}{D}\left[\operatorname{tr}\left(\mathbf{B}q_t(\mathbf{B})\right)+\frac{D-r}{L}\operatorname{tr}\mathbf{K}_t\right] \\
&+\frac{1}{D}\operatorname{tr}\left[\mathbf{B}^2q_t(\mathbf{B})^2\right]
+\left[\frac{2(D-r)}{DL}+\frac{\sigma^2}{L}\right]\operatorname{tr}\left[\mathbf{B}q_t(\mathbf{B})^2\right] \\
&+\frac{(D-r)(D-r+1+\sigma^2D)}{DL^2}\operatorname{tr}\left(\mathbf{K}_t^2\right)
+\frac{D-r}{DL^2}\left(\operatorname{tr}\mathbf{K}_t\right)^2. \tag*{(92)}
\end{aligned} E [ w t − w in 2 2 ∣ X 1 ] = 1 − D 2 [ tr ( B q t ( B ) ) + L D − r tr K t ] + D 1 tr [ B 2 q t ( B ) 2 ] + [ D L 2 ( D − r ) + L σ 2 ] tr [ B q t ( B ) 2 ] + D L 2 ( D − r ) ( D − r + 1 + σ 2 D ) tr ( K t 2 ) + D L 2 D − r ( tr K t ) 2 . (92)
Finally, we evaluate the traces in Equation (D.23) by the Marchenko–Pastur law. The block covariance B \mathbf{B} B has aspect ratio
L r = L / D r / D ⟶ α φ . (93) \frac{L}{r}=\frac{L/D}{r/D}\longrightarrow\frac{\alpha}{\varphi}. \tag*{(93)} r L = r / D L / D ⟶ φ α . (93)
Therefore, for every fixed polynomial f f f ,
1 D tr f ( B ) = r D 1 r tr f ( B ) ⟶ φ ⟨ f ⟩ α / φ . (94) \frac{1}{D}\operatorname{tr}f(\mathbf{B})=\frac{r}{D}\frac{1}{r}\operatorname{tr}f(\mathbf{B})\longrightarrow\varphi\langle f\rangle_{\alpha/\varphi}. \tag*{(94)} D 1 tr f ( B ) = D r r 1 tr f ( B ) ⟶ φ ⟨ f ⟩ α / φ . (94)
The matrices X 1 T X 1 / L \mathbf{X}_1^{\mathsf T}\mathbf{X}_1/L X 1 T X 1 / L and B \mathbf{B} B have the same r r r nonzero eigenvalues. The matrix X 1 T X 1 / L \mathbf{X}_1^{\mathsf T}\mathbf{X}_1/L X 1 T X 1 / L also has L − r L-r L − r zero eigenvalues, and Equation (21) gives q t ( 0 ) = η t q_t(0)=\eta^t q t ( 0 ) = η t . Hence, for j = 1 , 2 j=1,2 j = 1 , 2 ,
1 D tr ( K t j ) = L − r D ( η t ) j + r D 1 r tr ( q t ( B ) j ) (95) \frac{1}{D}\operatorname{tr}\left(\mathbf{K}_t^j\right)
=\frac{L-r}{D}(\eta^t)^j+\frac{r}{D}\frac{1}{r}\operatorname{tr}\left(q_t(\mathbf{B})^j\right) \tag*{(95)} D 1 tr ( K t j ) = D L − r ( η t ) j + D r r 1 tr ( q t ( B ) j ) (95)
⟶ ( α − φ ) ( η t ) j + φ ⟨ q t j ⟩ α / φ = κ j , t . (96) \longrightarrow(\alpha-\varphi)(\eta^t)^j+\varphi\left\langle q_t^j\right\rangle_{\alpha/\varphi}
=\kappa_{j,t}. \tag*{(96)} ⟶ ( α − φ ) ( η t ) j + φ ⟨ q t j ⟩ α / φ = κ j , t . (96)
Substituting Equations (D.25) and (D.27) into Equation (D.23) gives Equation (D.1), which is Equation (23) in Result 4.1.
Proposition D.1 gives the exact fixed-time error without a cavity approximation. We now derive its long-time growth for α > 1 \alpha>1 α > 1 .
Proposition D.2 (Quadratic long-time growth of projected GD). Suppose α > 1 \alpha>1 α > 1 , 0 < φ < 1 0<\varphi<1 0 < φ < 1 , and
0 < η < 2 ( 1 + φ / α ) 2 . (97) 0<\eta<\frac{2}{\left(1+\sqrt{\varphi/\alpha}\right)^2}. \tag*{(97)} 0 < η < ( 1 + φ / α ) 2 2 . (97) Then
lim t → ∞ E ( t ) t 2 = η 2 ( 1 − φ ) ( α − φ ) ( α + 1 − 2 φ + σ 2 ) α 2 > 0. (98) \lim_{t\to\infty}\frac{\mathcal{E}(t)}{t^2}
=\frac{\eta^2(1-\varphi)(\alpha-\varphi)(\alpha+1-2\varphi+\sigma^2)}{\alpha^2}>0. \tag*{(98)} t → ∞ lim t 2 E ( t ) = α 2 η 2 ( 1 − φ ) ( α − φ ) ( α + 1 − 2 φ + σ 2 ) > 0. (98)
Proof. Because α / φ > 1 \alpha/\varphi>1 α / φ > 1 , the Marchenko–Pastur support is separated from zero. Under Equation (D.28), the nonzero modes are stable, and therefore
⟨ q t ⟩ α / φ = O ( 1 ) , ⟨ q t 2 ⟩ α / φ = O ( 1 ) , t → ∞ . (99) \left\langle q_t\right\rangle_{\alpha/\varphi}=O(1),\qquad
\left\langle q_t^2\right\rangle_{\alpha/\varphi}=O(1),\qquad t\to\infty. \tag*{(99)} ⟨ q t ⟩ α / φ = O ( 1 ) , ⟨ q t 2 ⟩ α / φ = O ( 1 ) , t → ∞. (99)
Equations (21) and (D.30) give
κ 1 , t = η t ( α − φ ) + O ( 1 ) , κ 2 , t = η 2 t 2 ( α − φ ) + O ( 1 ) . (100) \kappa_{1,t}=\eta^t(\alpha-\varphi)+O(1),\qquad
\kappa_{2,t}=\eta^2t^2(\alpha-\varphi)+O(1). \tag*{(100)} κ 1 , t = η t ( α − φ ) + O ( 1 ) , κ 2 , t = η 2 t 2 ( α − φ ) + O ( 1 ) . (100)
Substituting Equation (D.31) into Equation (D.1) gives
lim t → ∞ E ( t ) t 2 = η 2 ( 1 − φ ) ( 1 − φ + σ 2 ) ( α − φ ) α 2 + η 2 ( 1 − φ ) ( α − φ ) 2 α 2 (101) \lim_{t\to\infty}\frac{\mathcal{E}(t)}{t^2}
=\frac{\eta^2(1-\varphi)(1-\varphi+\sigma^2)(\alpha-\varphi)}{\alpha^2}
+\frac{\eta^2(1-\varphi)(\alpha-\varphi)^2}{\alpha^2} \tag*{(101)} t → ∞ lim t 2 E ( t ) = α 2 η 2 ( 1 − φ ) ( 1 − φ + σ 2 ) ( α − φ ) + α 2 η 2 ( 1 − φ ) ( α − φ ) 2 (101)
= η 2 ( 1 − φ ) ( α − φ ) ( α + 1 − 2 φ + σ 2 ) α 2 , (102) =\frac{\eta^2(1-\varphi)(\alpha-\varphi)(\alpha+1-2\varphi+\sigma^2)}{\alpha^2}, \tag*{(102)} = α 2 η 2 ( 1 − φ ) ( α − φ ) ( α + 1 − 2 φ + σ 2 ) , (102)
which proves Equation (D.29).
The rank deficit produces a unit-eigenvalue sector in the learned iteration. Each inference step adds a source component in that sector, so the state grows linearly and the squared error grows quadratically. Together with full-GD recovery for φ > 1 \varphi> 1 φ > 1 , Proposition D.2 completes the α > 1 \alpha> 1 α > 1 part of Result 4.2.
The 0 < α < 1 0 < \alpha< 1 0 < α < 1 Case
In this section, we derive the α < 1 \alpha< 1 α < 1 part of Result 4.2 by the cavity method and combine it with the exact α > 1 \alpha> 1 α > 1 calculation.
Statistical properties of learned matrix
First, we compute the moments of the learned matrix below the GD-recovery threshold using the cavity method in random matrix theory.
Proposition E.1 (Moments of the learned matrix). Suppose 0 < α < 1 0 < \alpha< 1 0 < α < 1 , 0 < φ < 1 / α 0 < \varphi< 1/\alpha 0 < φ < 1/ α , and λ → 0 \lambda\to0 λ → 0 . With the large-D D D replacements stated explicitly in the proof,
− lim D → ∞ tr A ^ η D = lim D → ∞ ∥ A ^ ∥ F 2 η 2 D = φ 1 + ( 1 − α ) φ . (103) -\lim_{D\to\infty} \frac{\operatorname{tr}\hat{A}}{\eta D}
= \lim_{D\to\infty} \frac{\lVert\hat{A}\rVert_{\mathrm{F}}^2}{\eta^2 D}
= \frac{\varphi}{1+(1-\alpha)\varphi}. \tag*{(103)} − D → ∞ lim η D tr A ^ = D → ∞ lim η 2 D ∥ A ^ ∥ F 2 = 1 + ( 1 − α ) φ φ . (103) lim D → ∞ ∥ A ^ + η I D ∥ F 2 η 2 D = 1 − α φ 1 + ( 1 − α ) φ , (104) \lim_{D\to\infty} \frac{\lVert\hat{A}+\eta I_D\rVert_{\mathrm{F}}^2}{\eta^2D}
= \frac{1-\alpha\varphi}{1+(1-\alpha)\varphi}, \tag*{(104)} D → ∞ lim η 2 D ∥ A ^ + η I D ∥ F 2 = 1 + ( 1 − α ) φ 1 − α φ , (104) and
lim D → ∞ tr ( A ^ 2 ) η 2 D = φ [ 1 + ( 1 − 2 α ) φ ] [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) . (105) \lim_{D\to\infty} \frac{\operatorname{tr}(\hat{A}^2)}{\eta^2D}
= \frac{\varphi[1+(1-2\alpha)\varphi]}{[1+(1-\alpha)\varphi]^2(1-\alpha^2\varphi)}. \tag*{(105)} D → ∞ lim η 2 D tr ( A ^ 2 ) = [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) φ [ 1 + ( 1 − 2 α ) φ ] . (105)
Proof. Proposition C.1 shows that L e f f ( A ⋆ ) = 0 \mathcal{L}_{\mathrm{eff}}(A_\star)=0 L eff ( A ⋆ ) = 0 for every α \alpha α . Because the training objective is quadratic, its λ → 0 \lambda\to0 λ → 0 limit selects the minimum-norm matrix among those satisfying L e f f ( A ) = 0 \mathcal{L}_{\mathrm{eff}}(A)=0 L eff ( A ) = 0 . The training contexts are then rank deficient, so the constraints need not identify the update. Define
P μ : = X μ ( X μ T X μ ) − 1 X μ T , (106) P_\mu:= X_\mu(X_\mu^{\mathsf{T}}X_\mu)^{-1}X_\mu^{\mathsf{T}}, \tag*{(106)} P μ := X μ ( X μ T X μ ) − 1 X μ T , (106)
Q μ : = S μ ( S μ T S μ ) − 1 S μ T , (107) Q_\mu:= S_\mu(S_\mu^{\mathsf{T}}S_\mu)^{-1}S_\mu^{\mathsf{T}}, \tag*{(107)} Q μ := S μ ( S μ T S μ ) − 1 S μ T , (107)
S μ : = ( s μ , 1 , … , s μ , K − 1 ) . (108) S_\mu:= (s_{\mu,1},\ldots,s_{\mu,K-1}). \tag*{(108)} S μ := ( s μ , 1 , … , s μ , K − 1 ) . (108)
By Equation (E.6), the teacher states lie in the context span and P μ Q μ = Q μ P_\mu Q_\mu=Q_\mu P μ Q μ = Q μ . The condition L e f f ( A ) = 0 \mathcal{L}_{\mathrm{eff}}(A)=0 L eff ( A ) = 0 is equivalent to
H μ ( A + η I D ) S μ = 0 ⟺ P μ ( A + η I D ) Q μ = 0 (109) H_\mu(A+\eta I_D)S_\mu=0
\Longleftrightarrow P_\mu(A+\eta I_D)Q_\mu=0 \tag*{(109)} H μ ( A + η I D ) S μ = 0 ⟺ P μ ( A + η I D ) Q μ = 0 (109)
⟺ ( Q μ ⊗ P μ ) vec ( A + η I D ) = 0. (110) \Longleftrightarrow(Q_\mu\otimes P_\mu)\operatorname{vec}(A+\eta I_D)=0. \tag*{(110)} ⟺ ( Q μ ⊗ P μ ) vec ( A + η I D ) = 0. (110)
The minimum-norm solution is unchanged if the original loss is replaced by the squared norm of these equivalent constraints. With an auxiliary regularizer ϵ > 0 \epsilon>0 ϵ > 0 , define
R ϵ : = [ ∑ μ = 1 M Q μ ⊗ P μ + ϵ I D 2 ] − 1 . (111) R_\epsilon:= \left[\sum_{\mu=1}^{M} Q_\mu\otimes P_\mu+\epsilon I_{D^2}\right]^{-1}. \tag*{(111)} R ϵ := [ μ = 1 ∑ M Q μ ⊗ P μ + ϵ I D 2 ] − 1 . (111)
Vectorizing Equation (E.8) and using Equation (E.9) gives
vec ( A ^ ) = − η lim ϵ → 0 R ϵ [ ∑ μ Q μ ⊗ P μ ] vec I D (112) \operatorname{vec}(\hat{A})=-\eta\lim_{\epsilon\to0}R_\epsilon
\left[\sum_\mu Q_\mu\otimes P_\mu\right]\operatorname{vec}I_D \tag*{(112)} vec ( A ^ ) = − η ϵ → 0 lim R ϵ [ μ ∑ Q μ ⊗ P μ ] vec I D (112)
= − η vec I D + η lim ϵ → 0 ϵ R ϵ vec I D . (113) =-\eta\operatorname{vec}I_D+\eta\lim_{\epsilon\to0}\epsilon R_\epsilon\operatorname{vec}I_D. \tag*{(113)} = − η vec I D + η ϵ → 0 lim ϵ R ϵ vec I D . (113)
Equation (E.11) gives
vec ( A ^ ) η = − vec I D + [ lim ϵ → 0 ϵ R ϵ ] vec I D . (114) \frac{\operatorname{vec}(\hat{A})}{\eta}
=-\operatorname{vec}I_D+
\left[\lim_{\epsilon\to0}\epsilon R_\epsilon\right]\operatorname{vec}I_D. \tag*{(114)} η vec ( A ^ ) = − vec I D + [ ϵ → 0 lim ϵ R ϵ ] vec I D . (114)
The matrix lim ϵ → 0 ϵ R ϵ \lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon} lim ϵ → 0 ϵ R ϵ is an orthogonal projector, and hence its transpose and its square are equal to itself. Therefore,
− tr A ^ η D = 1 − 1 D ( vec I D ) T [ lim ϵ → 0 ϵ R ϵ ] vec I D , (115) -\frac{\operatorname{tr}\widehat{A}}{\eta D}=1-\frac{1}{D}(\operatorname{vec}I_D)^{\mathsf{T}}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]\operatorname{vec}I_D, \tag*{(115)} − η D tr A = 1 − D 1 ( vec I D ) T [ ϵ → 0 lim ϵ R ϵ ] vec I D , (115)
∥ A ^ ∥ F 2 η 2 D = 1 D ( vec I D ) T [ I D 2 − lim ϵ → 0 ϵ R ϵ ] 2 vec I D (116) \frac{\lVert\widehat{A}\rVert_{\mathrm{F}}^2}{\eta^2D}=\frac{1}{D}(\operatorname{vec}I_D)^{\mathsf{T}}\left[I_{D^2}-\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]^2\operatorname{vec}I_D \tag*{(116)} η 2 D ∥ A ∥ F 2 = D 1 ( vec I D ) T [ I D 2 − ϵ → 0 lim ϵ R ϵ ] 2 vec I D (116)
= 1 − 1 D ( vec I D ) T [ lim ϵ → 0 ϵ R ϵ ] vec I D , (117) =1-\frac{1}{D}(\operatorname{vec}I_D)^{\mathsf{T}}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]\operatorname{vec}I_D, \tag*{(117)} = 1 − D 1 ( vec I D ) T [ ϵ → 0 lim ϵ R ϵ ] vec I D , (117)
tr ( A ^ 2 ) η 2 D = 1 − 2 D ( vec I D ) T [ lim ϵ → 0 ϵ R ϵ ] vec I D (118) \frac{\operatorname{tr}(\widehat{A}^2)}{\eta^2D}=1-\frac{2}{D}(\operatorname{vec}I_D)^{\mathsf{T}}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]\operatorname{vec}I_D \tag*{(118)} η 2 D tr ( A 2 ) = 1 − D 2 ( vec I D ) T [ ϵ → 0 lim ϵ R ϵ ] vec I D (118)
+ 1 D ( vec I D ) T [ lim ϵ → 0 ϵ R ϵ ] T D [ lim ϵ → 0 ϵ R ϵ ] vec I D , (119) +\frac{1}{D}(\operatorname{vec}I_D)^{\mathsf{T}}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]T_D\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]\operatorname{vec}I_D, \tag*{(119)} + D 1 ( vec I D ) T [ ϵ → 0 lim ϵ R ϵ ] T D [ ϵ → 0 lim ϵ R ϵ ] vec I D , (119)
where T D : R D 2 → R D 2 T_D:\mathbb{R}^{D^2}\to\mathbb{R}^{D^2} T D : R D 2 → R D 2 denotes the transpose operator defined by
T D vec ( B ) = vec ( B T ) . (120) T_D\operatorname{vec}(B)=\operatorname{vec}(B^{\mathsf{T}}). \tag*{(120)} T D vec ( B ) = vec ( B T ) . (120)
It therefore suffices to calculate the following two scalars separately:
1 D ( vec I D ) T [ lim ϵ → 0 ϵ R ϵ ] vec I D , (121) \frac{1}{D}(\operatorname{vec}I_D)^{\mathsf{T}}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]\operatorname{vec}I_D, \tag*{(121)} D 1 ( vec I D ) T [ ϵ → 0 lim ϵ R ϵ ] vec I D , (121)
and
1 D ( vec I D ) T [ lim ϵ → 0 ϵ R ϵ ] T D [ lim ϵ → 0 ϵ R ϵ ] vec I D . (122) \frac{1}{D}(\operatorname{vec}I_D)^{\mathsf{T}}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]T_D\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]\operatorname{vec}I_D. \tag*{(122)} D 1 ( vec I D ) T [ ϵ → 0 lim ϵ R ϵ ] T D [ ϵ → 0 lim ϵ R ϵ ] vec I D . (122)
Calculation of Equation (E.19). First, we calculate Equation (E.19). Define the order parameter:
χ : = − lim D → ∞ tr A ^ η D . (123) \chi:=-\lim_{D\to\infty}\frac{\operatorname{tr}\widehat{A}}{\eta D}. \tag*{(123)} χ := − D → ∞ lim η D tr A . (123)
Equations (E.17) and (E.19) give
1 D ( vec I D ) T [ lim ϵ → 0 ϵ R ϵ ] vec I D = 1 − χ . (124) \frac{1}{D}(\operatorname{vec}I_D)^{\mathsf{T}}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]\operatorname{vec}I_D=1-\chi. \tag*{(124)} D 1 ( vec I D ) T [ ϵ → 0 lim ϵ R ϵ ] vec I D = 1 − χ . (124)
Since R ϵ \mathcal{R}_{\epsilon} R ϵ is the resolvent of a sum of independent task contributions, we use a leave-one-task cavity calculation, in which the removed task is independent of the resolvent formed by the remaining tasks. In this approach, deleting task μ \mu μ defines
R ϵ − μ : = [ ∑ ν ≠ μ Q ν ⊗ P ν + ϵ I D 2 ] − 1 . (125) \mathcal{R}_{\epsilon}^{-\mu}:=\left[\sum_{\nu\ne\mu}Q_{\nu}\otimes P_{\nu}+\epsilon I_{D^2}\right]^{-1}. \tag*{(125)} R ϵ − μ := ν = μ ∑ Q ν ⊗ P ν + ϵ I D 2 − 1 . (125)
Because P μ P_{\mu} P μ and Q μ Q_{\mu} Q μ are projectors,
( Q μ ⊗ P μ ) 2 = ( Q μ 2 ⊗ P μ 2 ) = Q μ ⊗ P μ (126) (Q_{\mu}\otimes P_{\mu})^2=(Q_{\mu}^2\otimes P_{\mu}^2)=Q_{\mu}\otimes P_{\mu} \tag*{(126)} ( Q μ ⊗ P μ ) 2 = ( Q μ 2 ⊗ P μ 2 ) = Q μ ⊗ P μ (126)
( vec I D ) T ( Q μ ⊗ P μ ) vec I D = tr ( P μ Q μ ) = K − 1. (127) (\operatorname{vec}I_D)^{\mathsf{T}}(Q_{\mu}\otimes P_{\mu})\operatorname{vec}I_D=\operatorname{tr}(P_{\mu}Q_{\mu})=K-1. \tag*{(127)} ( vec I D ) T ( Q μ ⊗ P μ ) vec I D = tr ( P μ Q μ ) = K − 1. (127)
Applying the Woodbury formula to Equations (E.9) and (E.23), and using Equation (E.25), gives
( Q μ ⊗ P μ ) R ϵ = [ ϵ I D 2 + ( Q μ ⊗ P μ ) ϵ R ϵ − μ ( Q μ ⊗ P μ ) ] − 1 ( Q μ ⊗ P μ ) ϵ R ϵ − μ . (128) (Q_{\mu}\otimes P_{\mu})\mathcal{R}_{\epsilon}=\left[\epsilon I_{D^2}+(Q_{\mu}\otimes P_{\mu})\epsilon\mathcal{R}_{\epsilon}^{-\mu}(Q_{\mu}\otimes P_{\mu})\right]^{-1}(Q_{\mu}\otimes P_{\mu})\epsilon\mathcal{R}_{\epsilon}^{-\mu}. \tag*{(128)} ( Q μ ⊗ P μ ) R ϵ = [ ϵ I D 2 + ( Q μ ⊗ P μ ) ϵ R ϵ − μ ( Q μ ⊗ P μ ) ] − 1 ( Q μ ⊗ P μ ) ϵ R ϵ − μ . (128)
We first evaluate the matrix inside the inverse in Equation (E.26). The matrix R ϵ − μ \mathcal{R}_{\epsilon}^{-\mu} R ϵ − μ depends only on the tasks ν ≠ μ \nu\ne\mu ν = μ , and is therefore independent of ( P μ , Q μ ) (P_{\mu},Q_{\mu}) ( P μ , Q μ ) . Throughout this cavity calculation, ≃ \simeq ≃ denotes equality at the retained leading order after the displayed normalization, with discarded terms vanishing in probability as D → ∞ D\to\infty D → ∞ . Its compression by task μ \mu μ concentrates around its conditional average, so
( Q μ ⊗ P μ ) [ lim ϵ → 0 ϵ R ϵ − μ ] ( Q μ ⊗ P μ ) ≃ 1 D 2 tr [ lim ϵ → 0 ϵ R ϵ − μ ( Q μ ⊗ P μ ) ] . (129) (Q_{\mu}\otimes P_{\mu})\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}^{-\mu}\right](Q_{\mu}\otimes P_{\mu})\simeq\frac{1}{D^2}\operatorname{tr}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}^{-\mu}(Q_{\mu}\otimes P_{\mu})\right]. \tag*{(129)} ( Q μ ⊗ P μ ) [ ϵ → 0 lim ϵ R ϵ − μ ] ( Q μ ⊗ P μ ) ≃ D 2 1 tr [ ϵ → 0 lim ϵ R ϵ − μ ( Q μ ⊗ P μ ) ] . (129)
To calculate the normalized trace in this expression, let λ 1 , … , λ D 2 \lambda_1,\ldots,\lambda_{D^2} λ 1 , … , λ D 2 be the eigenvalues of
∑ ν ≠ μ Q ν ⊗ P ν . (130) \sum_{\nu\ne\mu} \mathbf{Q}_{\nu}\otimes\mathbf{P}_{\nu}. \tag*{(130)} ν = μ ∑ Q ν ⊗ P ν . (130)
The eigenvalues of R ϵ − μ \mathcal{R}_{\epsilon}^{-\mu} R ϵ − μ are 1 / ( λ j + ϵ ) 1/(\lambda_j+\epsilon) 1/ ( λ j + ϵ ) , and hence the eigenvalues of ϵ R ϵ − μ \epsilon\mathcal{R}_{\epsilon}^{-\mu} ϵ R ϵ − μ satisfy
ϵ λ j + ϵ → { 0 , λ j > 0 , 1 , λ j = 0. (131) \frac{\epsilon}{\lambda_j+\epsilon}\to
\begin{cases}
0, & \lambda_j>0,\\
1, & \lambda_j=0.
\end{cases} \tag*{(131)} λ j + ϵ ϵ → { 0 , 1 , λ j > 0 , λ j = 0. (131)
Therefore,
tr [ lim ϵ → 0 ϵ R ϵ − μ ] = # { j : λ j = 0 } = D 2 − rank ( ∑ ν ≠ μ Q ν ⊗ P ν ) . (132) \operatorname{tr}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}^{-\mu}\right]=\#\{j:\lambda_j=0\}=D^2-\operatorname{rank}\left(\sum_{\nu\ne\mu}\mathbf{Q}_{\nu}\otimes\mathbf{P}_{\nu}\right). \tag*{(132)} tr [ ϵ → 0 lim ϵ R ϵ − μ ] = # { j : λ j = 0 } = D 2 − rank ν = μ ∑ Q ν ⊗ P ν . (132)
For each task,
rank ( Q ν ⊗ P ν ) = rank ( Q ν ) rank ( P ν ) = L ( K − 1 ) . (133) \operatorname{rank}(\mathbf{Q}_{\nu}\otimes\mathbf{P}_{\nu})=\operatorname{rank}(\mathbf{Q}_{\nu})\operatorname{rank}(\mathbf{P}_{\nu})=L(K-1). \tag*{(133)} rank ( Q ν ⊗ P ν ) = rank ( Q ν ) rank ( P ν ) = L ( K − 1 ) . (133)
Since the constraints from different tasks are linearly independent,
rank ( ∑ ν ≠ μ Q ν ⊗ P ν ) = ( M − 1 ) L ( K − 1 ) . (134) \operatorname{rank}\left(\sum_{\nu\ne\mu}\mathbf{Q}_{\nu}\otimes\mathbf{P}_{\nu}\right)=(M-1)L(K-1). \tag*{(134)} rank ν = μ ∑ Q ν ⊗ P ν = ( M − 1 ) L ( K − 1 ) . (134)
It follows that
1 D 2 tr [ lim ϵ → 0 ϵ R ϵ − μ ] = 1 − ( M − 1 ) L ( K − 1 ) D 2 (135) \frac{1}{D^2}\operatorname{tr}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}^{-\mu}\right]=1-\frac{(M-1)L(K-1)}{D^2} \tag*{(135)} D 2 1 tr [ ϵ → 0 lim ϵ R ϵ − μ ] = 1 − D 2 ( M − 1 ) L ( K − 1 ) (135)
= 1 − L D ( M − 1 ) ( K − 1 ) D (136) =1-\frac{L}{D}\frac{(M-1)(K-1)}{D} \tag*{(136)} = 1 − D L D ( M − 1 ) ( K − 1 ) (136)
→ 1 − α φ . (137) \to1-\alpha\varphi. \tag*{(137)} → 1 − α φ . (137)
Consequently, the compression in Equation (E.26) satisfies
( Q μ ⊗ P μ ) [ lim ϵ → 0 ϵ R ϵ − μ ] ( Q μ ⊗ P μ ) ≃ ( 1 − α φ ) ( Q μ ⊗ P μ ) . (138) (\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}^{-\mu}\right](\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\simeq(1-\alpha\varphi)(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu}). \tag*{(138)} ( Q μ ⊗ P μ ) [ ϵ → 0 lim ϵ R ϵ − μ ] ( Q μ ⊗ P μ ) ≃ ( 1 − α φ ) ( Q μ ⊗ P μ ) . (138)
Multiplying Equation (E.26) by vec I D \operatorname{vec}I_D vec I D and then by ( vec I D ) T / ( K − 1 ) (\operatorname{vec}I_D)^{\mathsf{T}}/(K-1) ( vec I D ) T / ( K − 1 ) from the left gives
lim ϵ → 0 1 K − 1 ( vec I D ) T ( Q μ ⊗ P μ ) R ϵ vec I D (139) \lim_{\epsilon\to0}\frac{1}{K-1}(\operatorname{vec}I_D)^{\mathsf{T}}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\mathcal{R}_{\epsilon}\operatorname{vec}I_D \tag*{(139)} ϵ → 0 lim K − 1 1 ( vec I D ) T ( Q μ ⊗ P μ ) R ϵ vec I D (139)
= lim ϵ → 0 1 K − 1 ( vec I D ) T [ ϵ I D 2 + ( Q μ ⊗ P μ ) ϵ R ϵ − μ ( Q μ ⊗ P μ ) ] − 1 ( Q μ ⊗ P μ ) ϵ R ϵ − μ vec I D (140) =\lim_{\epsilon\to0}\frac{1}{K-1}(\operatorname{vec}I_D)^{\mathsf{T}}\left[\epsilon I_{D^2}+(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\epsilon\mathcal{R}_{\epsilon}^{-\mu}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\right]^{-1}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\epsilon\mathcal{R}_{\epsilon}^{-\mu}\operatorname{vec}I_D \tag*{(140)} = ϵ → 0 lim K − 1 1 ( vec I D ) T [ ϵ I D 2 + ( Q μ ⊗ P μ ) ϵ R ϵ − μ ( Q μ ⊗ P μ ) ] − 1 ( Q μ ⊗ P μ ) ϵ R ϵ − μ vec I D (140)
≃ lim ϵ → 0 1 K − 1 ( vec I D ) T [ ϵ I D 2 + ( 1 − α φ ) ( Q μ ⊗ P μ ) ] − 1 ( Q μ ⊗ P μ ) ϵ R ϵ − μ vec I D (141) \simeq\lim_{\epsilon\to0}\frac{1}{K-1}(\operatorname{vec}I_D)^{\mathsf{T}}\left[\epsilon I_{D^2}+(1-\alpha\varphi)(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\right]^{-1}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\epsilon\mathcal{R}_{\epsilon}^{-\mu}\operatorname{vec}I_D \tag*{(141)} ≃ ϵ → 0 lim K − 1 1 ( vec I D ) T [ ϵ I D 2 + ( 1 − α φ ) ( Q μ ⊗ P μ ) ] − 1 ( Q μ ⊗ P μ ) ϵ R ϵ − μ vec I D (141)
= lim ϵ → 0 1 ( K − 1 ) ( ϵ + 1 − α φ ) ( vec I D ) T ( Q μ ⊗ P μ ) ϵ R ϵ − μ vec I D (142) =\lim_{\epsilon\to0}\frac{1}{(K-1)(\epsilon+1-\alpha\varphi)}(\operatorname{vec}I_D)^{\mathsf{T}}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\epsilon\mathcal{R}_{\epsilon}^{-\mu}\operatorname{vec}I_D \tag*{(142)} = ϵ → 0 lim ( K − 1 ) ( ϵ + 1 − α φ ) 1 ( vec I D ) T ( Q μ ⊗ P μ ) ϵ R ϵ − μ vec I D (142)
= 1 ( K − 1 ) ( 1 − α φ ) ( vec I D ) T ( Q μ ⊗ P μ ) [ lim ϵ → 0 ϵ R ϵ − μ ] vec I D (143) =\frac{1}{(K-1)(1-\alpha\varphi)}(\operatorname{vec}I_D)^{\mathsf{T}}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}^{-\mu}\right]\operatorname{vec}I_D \tag*{(143)} = ( K − 1 ) ( 1 − α φ ) 1 ( vec I D ) T ( Q μ ⊗ P μ ) [ ϵ → 0 lim ϵ R ϵ − μ ] vec I D (143)
≃ 1 1 − α φ 1 D ( vec I D ) T [ lim ϵ → 0 ϵ R ϵ − μ ] vec I D (144) \simeq\frac{1}{1-\alpha\varphi}\frac{1}{D}(\operatorname{vec}I_D)^{\mathsf{T}}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}^{-\mu}\right]\operatorname{vec}I_D \tag*{(144)} ≃ 1 − α φ 1 D 1 ( vec I D ) T [ ϵ → 0 lim ϵ R ϵ − μ ] vec I D (144)
≃ 1 1 − α φ 1 D ( vec I D ) T [ lim ϵ → 0 ϵ R ϵ ] vec I D (145) \simeq\frac{1}{1-\alpha\varphi}\frac{1}{D}(\operatorname{vec}I_D)^{\mathsf{T}}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]\operatorname{vec}I_D \tag*{(145)} ≃ 1 − α φ 1 D 1 ( vec I D ) T [ ϵ → 0 lim ϵ R ϵ ] vec I D (145)
= 1 − χ 1 − α φ . (146) =\frac{1-\chi}{1-\alpha\varphi}. \tag*{(146)} = 1 − α φ 1 − χ . (146)
Here the first ≃ \simeq ≃ uses Equation (E.36). The following equality uses
[ ϵ I D 2 + ( 1 − α φ ) ( Q μ ⊗ P μ ) ] − 1 ( Q μ ⊗ P μ ) = 1 ϵ + 1 − α φ ( Q μ ⊗ P μ ) . (147) \left[\epsilon I_{D^2}+(1-\alpha\varphi)(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\right]^{-1}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})=\frac{1}{\epsilon+1-\alpha\varphi}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu}). \tag*{(147)} [ ϵ I D 2 + ( 1 − α φ ) ( Q μ ⊗ P μ ) ] − 1 ( Q μ ⊗ P μ ) = ϵ + 1 − α φ 1 ( Q μ ⊗ P μ ) . (147)
which follows from ( Q μ ⊗ P μ ) 2 = Q μ ⊗ P μ (\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})^2=\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu} ( Q μ ⊗ P μ ) 2 = Q μ ⊗ P μ . The second ≃ \simeq ≃ uses the following large-D D D concentration for the contraction with the independent task μ \mu μ :
1 K − 1 ( vec I D ) ⊤ ( Q μ ⊗ P μ ) [ lim ϵ → 0 ϵ R ϵ − μ ] vec I D ≃ 1 D ( vec I D ) ⊤ [ lim ϵ → 0 ϵ R ϵ − μ ] vec I D . (148) \frac{1}{K-1}(\operatorname{vec}I_D)^{\top}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}^{-\mu}\right]\operatorname{vec}I_D \simeq\frac{1}{D}(\operatorname{vec}I_D)^{\top}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}^{-\mu}\right]\operatorname{vec}I_D. \tag*{(148)} K − 1 1 ( vec I D ) ⊤ ( Q μ ⊗ P μ ) [ ϵ → 0 lim ϵ R ϵ − μ ] vec I D ≃ D 1 ( vec I D ) ⊤ [ ϵ → 0 lim ϵ R ϵ − μ ] vec I D . (148)
On the other hand, averaging the left-hand side over μ \mu μ gives
1 M ( K − 1 ) ( vec I D ) ⊤ [ ∑ μ = 1 M Q μ ⊗ P μ ] R ϵ vec I D = 1 M ( K − 1 ) ( vec I D ) ⊤ ( I D 2 − ϵ R ϵ ) vec I D → χ φ . (149) \frac{1}{M(K-1)}(\operatorname{vec}I_D)^{\top}\left[\sum_{\mu=1}^{M}\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu}\right]\mathcal{R}_{\epsilon}\operatorname{vec}I_D=\frac{1}{M(K-1)}(\operatorname{vec}I_D)^{\top}(I_{D^2}-\epsilon\mathcal{R}_{\epsilon})\operatorname{vec}I_D\to\frac{\chi}{\varphi}. \tag*{(149)} M ( K − 1 ) 1 ( vec I D ) ⊤ [ μ = 1 ∑ M Q μ ⊗ P μ ] R ϵ vec I D = M ( K − 1 ) 1 ( vec I D ) ⊤ ( I D 2 − ϵ R ϵ ) vec I D → φ χ . (149)
Equating Equations (E.44) and (E.47) gives the following self-consistent equation:
χ φ = 1 − χ 1 − α φ , (150) \frac{\chi}{\varphi}=\frac{1-\chi}{1-\alpha\varphi}, \tag*{(150)} φ χ = 1 − α φ 1 − χ , (150)
which gives
χ = φ 1 + ( 1 − α ) φ . (151) \chi=\frac{\varphi}{1+(1-\alpha)\varphi}. \tag*{(151)} χ = 1 + ( 1 − α ) φ φ . (151)
The estimator is the orthogonal projection of − η I D -\eta I_D − η I D onto the row space of the constraints. Therefore
lim D → ∞ ∥ A ^ ∥ F 2 η 2 D = − lim D → ∞ tr A ^ η D = χ = φ 1 + ( 1 − α ) φ . (152) \lim_{D\to\infty}\frac{\lVert\widehat{A}\rVert_{\mathrm{F}}^2}{\eta^2D}=-\lim_{D\to\infty}\frac{\operatorname{tr}\widehat{A}}{\eta D}=\chi=\frac{\varphi}{1+(1-\alpha)\varphi}. \tag*{(152)} D → ∞ lim η 2 D ∥ A ∥ F 2 = − D → ∞ lim η D tr A = χ = 1 + ( 1 − α ) φ φ . (152)
Equation (E.11) also gives
lim D → ∞ ∥ A ^ + η I D ∥ F 2 η 2 D = lim D → ∞ 1 D ( vec I D ) ⊤ [ lim ϵ → 0 ϵ R ϵ ] 2 vec I D (153) \lim_{D\to\infty}\frac{\lVert\widehat{A}+\eta I_D\rVert_{\mathrm{F}}^2}{\eta^2D}=\lim_{D\to\infty}\frac{1}{D}(\operatorname{vec}I_D)^{\top}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]^2\operatorname{vec}I_D \tag*{(153)} D → ∞ lim η 2 D ∥ A + η I D ∥ F 2 = D → ∞ lim D 1 ( vec I D ) ⊤ [ ϵ → 0 lim ϵ R ϵ ] 2 vec I D (153)
= lim D → ∞ 1 D ( vec I D ) ⊤ [ lim ϵ → 0 ϵ R ϵ ] vec I D (154) =\lim_{D\to\infty}\frac{1}{D}(\operatorname{vec}I_D)^{\top}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]\operatorname{vec}I_D \tag*{(154)} = D → ∞ lim D 1 ( vec I D ) ⊤ [ ϵ → 0 lim ϵ R ϵ ] vec I D (154)
= 1 − χ = 1 − α φ 1 + ( 1 − α ) φ . (155) =1-\chi=\frac{1-\alpha\varphi}{1+(1-\alpha)\varphi}. \tag*{(155)} = 1 − χ = 1 + ( 1 − α ) φ 1 − α φ . (155)
The second equality uses the projector identity [ lim ϵ → 0 ϵ R ϵ ] 2 = lim ϵ → 0 ϵ R ϵ [\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}]^2=\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon} [ lim ϵ → 0 ϵ R ϵ ] 2 = lim ϵ → 0 ϵ R ϵ . The third equality uses Equation (E.22).
Calculation of Equation (E.20). Second, we calculate Equation (E.20) by deriving a second self-consistent equation from the same Woodbury identity. Define the order parameters:
m F : = lim D → ∞ 1 D ∥ A ^ + η χ I D ∥ F 2 , (156) m_{\mathrm{F}}:=\lim_{D\to\infty}\frac{1}{D}\lVert\widehat{A}+\eta\chi I_D\rVert_{\mathrm{F}}^2, \tag*{(156)} m F := D → ∞ lim D 1 ∥ A + η χ I D ∥ F 2 , (156)
m T : = lim D → ∞ 1 D tr ( A ^ + η χ I D ) 2 . (157) m_{\mathrm{T}}:=\lim_{D\to\infty}\frac{1}{D}\operatorname{tr}(\widehat{A}+\eta\chi I_D)^2. \tag*{(157)} m T := D → ∞ lim D 1 tr ( A + η χ I D ) 2 . (157)
By Equations (E.11) and (E.22), the second target satisfies
m T η 2 = lim D → ∞ { 1 D ( vec I D ) ⊤ [ lim ϵ → 0 ϵ R ϵ ] T D [ lim ϵ → 0 ϵ R ϵ ] vec I D − ( 1 − χ ) 2 } . (158) \frac{m_{\mathrm{T}}}{\eta^2}=\lim_{D\to\infty}\left\{\frac{1}{D}(\operatorname{vec}I_D)^{\top}\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]T_D\left[\lim_{\epsilon\to0}\epsilon\mathcal{R}_{\epsilon}\right]\operatorname{vec}I_D-(1-\chi)^2\right\}. \tag*{(158)} η 2 m T = D → ∞ lim { D 1 ( vec I D ) ⊤ [ ϵ → 0 lim ϵ R ϵ ] T D [ ϵ → 0 lim ϵ R ϵ ] vec I D − ( 1 − χ ) 2 } . (158)
The trace and Frobenius identities obtained above give
m F = lim D → ∞ [ ∥ A ^ ∥ F 2 D + 2 η χ D tr A ^ + η 2 χ 2 ] (159) m_{\mathrm{F}}=\lim_{D\to\infty}\left[\frac{\lVert\widehat{A}\rVert_{\mathrm{F}}^2}{D}+\frac{2\eta\chi}{D}\operatorname{tr}\widehat{A}+\eta^2\chi^2\right] \tag*{(159)} m F = D → ∞ lim [ D ∥ A ∥ F 2 + D 2 η χ tr A + η 2 χ 2 ] (159)
= η 2 χ − 2 η 2 χ 2 + η 2 χ 2 (160) =\eta^2\chi-2\eta^2\chi^2+\eta^2\chi^2 \tag*{(160)} = η 2 χ − 2 η 2 χ 2 + η 2 χ 2 (160)
= η 2 ( χ − χ 2 ) . (161) =\eta^2(\chi-\chi^2). \tag*{(161)} = η 2 ( χ − χ 2 ) . (161)
We now start again from the Woodbury identity (Equation (E.26)):
( Q μ ⊗ P μ ) R ϵ vec I D = [ ϵ I D 2 + ( Q μ ⊗ P μ ) ϵ R − μ ( Q μ ⊗ P μ ) ] − 1 ( Q μ ⊗ P μ ) ϵ R − μ vec I D . (162) (\mathbf{Q}_{\mu} \otimes\mathbf{P}_{\mu})\mathcal{R}_{\epsilon}\operatorname{vec} I_D = \left[\epsilon I_{D^2} + (\mathbf{Q}_{\mu} \otimes\mathbf{P}_{\mu})\epsilon\mathcal{R}_{-\mu}(\mathbf{Q}_{\mu} \otimes\mathbf{P}_{\mu})\right]^{-1}(\mathbf{Q}_{\mu} \otimes\mathbf{P}_{\mu})\epsilon\mathcal{R}_{-\mu}\operatorname{vec} I_D. \tag*{(162)} ( Q μ ⊗ P μ ) R ϵ vec I D = [ ϵ I D 2 + ( Q μ ⊗ P μ ) ϵ R − μ ( Q μ ⊗ P μ ) ] − 1 ( Q μ ⊗ P μ ) ϵ R − μ vec I D . (162)
Equation (E.11) can also be written as
vec ( A ^ + η χ I D ) η = χ vec I D − lim ϵ → 0 ∑ μ = 1 M ( Q μ ⊗ P μ ) R ϵ vec I D . (163) \frac{\operatorname{vec}(\widehat{\mathbf{A}}+\eta\chi I_D)}{\eta} = \chi\operatorname{vec} I_D-\lim_{\epsilon\to0}\sum_{\mu=1}^{M}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\mathcal{R}_{\epsilon}\operatorname{vec} I_D. \tag*{(163)} η vec ( A + η χ I D ) = χ vec I D − ϵ → 0 lim μ = 1 ∑ M ( Q μ ⊗ P μ ) R ϵ vec I D . (163)
Applying η 2 D − 1 ( ⋅ ) ⊤ T D ( ⋅ ) \eta^2D^{-1}(\cdot)^{\top}T_D(\cdot) η 2 D − 1 ( ⋅ ) ⊤ T D ( ⋅ ) to both sides of Equation (E.61) gives
lim D → ∞ 1 D vec ( A ^ + η χ I D ) ⊤ T D vec ( A ^ + η χ I D ) (164) \lim_{D\to\infty}\frac{1}{D}\operatorname{vec}(\widehat{\mathbf{A}}+\eta\chi I_D)^{\top}T_D\operatorname{vec}(\widehat{\mathbf{A}}+\eta\chi I_D) \tag*{(164)} D → ∞ lim D 1 vec ( A + η χ I D ) ⊤ T D vec ( A + η χ I D ) (164)
= lim D → ∞ η 2 D [ χ vec I D − lim ϵ → 0 ∑ μ = 1 M ( Q μ ⊗ P μ ) R ϵ vec I D ] ⊤ T D [ χ vec I D − lim ϵ → 0 ∑ ν = 1 M ( Q ν ⊗ P ν ) R ϵ vec I D ] . (165) =\lim_{D\to\infty}\frac{\eta^2}{D}\left[\chi\operatorname{vec} I_D-\lim_{\epsilon\to0}\sum_{\mu=1}^{M}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\mathcal{R}_{\epsilon}\operatorname{vec} I_D\right]^{\top}T_D
\left[\chi\operatorname{vec} I_D-\lim_{\epsilon\to0}\sum_{\nu=1}^{M}(\mathbf{Q}_{\nu}\otimes\mathbf{P}_{\nu})\mathcal{R}_{\epsilon}\operatorname{vec} I_D\right]. \tag*{(165)} = D → ∞ lim D η 2 [ χ vec I D − ϵ → 0 lim μ = 1 ∑ M ( Q μ ⊗ P μ ) R ϵ vec I D ] ⊤ T D [ χ vec I D − ϵ → 0 lim ν = 1 ∑ M ( Q ν ⊗ P ν ) R ϵ vec I D ] . (165)
= lim D → ∞ η 2 D { χ 2 ( vec I D ) ⊤ T D vec I D − 2 χ lim ϵ → 0 ∑ μ = 1 M ( vec I D ) ⊤ T D ( Q μ ⊗ P μ ) R ϵ vec I D + lim ϵ → 0 ∑ μ , ν = 1 M ( vec I D ) ⊤ R ϵ ( Q μ ⊗ P μ ) T D ( Q ν ⊗ P ν ) R ϵ vec I D } . (166) =\lim_{D\to\infty}\frac{\eta^2}{D}\left\{\chi^2(\operatorname{vec} I_D)^{\top}T_D\operatorname{vec} I_D-2\chi\lim_{\epsilon\to0}\sum_{\mu=1}^{M}(\operatorname{vec} I_D)^{\top}T_D(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\mathcal{R}_{\epsilon}\operatorname{vec} I_D
+\lim_{\epsilon\to0}\sum_{\mu,\nu=1}^{M}(\operatorname{vec} I_D)^{\top}\mathcal{R}_{\epsilon}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})T_D(\mathbf{Q}_{\nu}\otimes\mathbf{P}_{\nu})\mathcal{R}_{\epsilon}\operatorname{vec} I_D\right\}. \tag*{(166)} = D → ∞ lim D η 2 { χ 2 ( vec I D ) ⊤ T D vec I D − 2 χ ϵ → 0 lim μ = 1 ∑ M ( vec I D ) ⊤ T D ( Q μ ⊗ P μ ) R ϵ vec I D + ϵ → 0 lim μ , ν = 1 ∑ M ( vec I D ) ⊤ R ϵ ( Q μ ⊗ P μ ) T D ( Q ν ⊗ P ν ) R ϵ vec I D } . (166)
= lim D → ∞ η 2 D { χ 2 ( vec I D ) ⊤ T D vec I D − 2 χ lim ϵ → 0 ∑ μ = 1 M ( vec I D ) ⊤ T D ( Q μ ⊗ P μ ) R ϵ vec I D + lim ϵ → 0 ∑ μ = ν ( vec I D ) ⊤ R ϵ ( Q μ ⊗ P μ ) T D ( Q ν ⊗ P ν ) R ϵ vec I D + lim ϵ → 0 ∑ μ ≠ ν ( vec I D ) ⊤ R ϵ ( Q μ ⊗ P μ ) T D ( Q ν ⊗ P ν ) R ϵ vec I D } . (167) =\lim_{D\to\infty}\frac{\eta^2}{D}\left\{\chi^2(\operatorname{vec} I_D)^{\top}T_D\operatorname{vec} I_D-2\chi\lim_{\epsilon\to0}\sum_{\mu=1}^{M}(\operatorname{vec} I_D)^{\top}T_D(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})\mathcal{R}_{\epsilon}\operatorname{vec} I_D
+\lim_{\epsilon\to0}\sum_{\mu=\nu}(\operatorname{vec} I_D)^{\top}\mathcal{R}_{\epsilon}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})T_D(\mathbf{Q}_{\nu}\otimes\mathbf{P}_{\nu})\mathcal{R}_{\epsilon}\operatorname{vec} I_D
+\lim_{\epsilon\to0}\sum_{\mu\ne\nu}(\operatorname{vec} I_D)^{\top}\mathcal{R}_{\epsilon}(\mathbf{Q}_{\mu}\otimes\mathbf{P}_{\mu})T_D(\mathbf{Q}_{\nu}\otimes\mathbf{P}_{\nu})\mathcal{R}_{\epsilon}\operatorname{vec} I_D\right\}. \tag*{(167)} = D → ∞ lim D η 2 ⎩ ⎨ ⎧ χ 2 ( vec I D ) ⊤ T D vec I D − 2 χ ϵ → 0 lim μ = 1 ∑ M ( vec I D ) ⊤ T D ( Q μ ⊗ P μ ) R ϵ vec I D + ϵ → 0 lim μ = ν ∑ ( vec I D ) ⊤ R ϵ ( Q μ ⊗ P μ ) T D ( Q ν ⊗ P ν ) R ϵ vec I D + ϵ → 0 lim μ = ν ∑ ( vec I D ) ⊤ R ϵ ( Q μ ⊗ P μ ) T D ( Q ν ⊗ P ν ) R ϵ vec I D ⎭ ⎬ ⎫ . (167)
The left-hand side of Equation (E.65) is
lim D → ∞ 1 D vec ( A ^ + η χ I D ) ⊤ T D vec ( A ^ + η χ I D ) (168) \lim_{D\to\infty}\frac{1}{D}\operatorname{vec}(\widehat{\mathbf{A}}+\eta\chi I_D)^{\top}T_D\operatorname{vec}(\widehat{\mathbf{A}}+\eta\chi I_D) \tag*{(168)} D → ∞ lim D 1 vec ( A + η χ I D ) ⊤ T D vec ( A + η χ I D ) (168)
= lim D → ∞ 1 D tr ( A ^ + η χ I D ) 2 (169) =\lim_{D\to\infty}\frac{1}{D}\operatorname{tr}(\widehat{\mathbf{A}}+\eta\chi I_D)^2 \tag*{(169)} = D → ∞ lim D 1 tr ( A + η χ I D ) 2 (169)
= m T . (170) =m_T. \tag*{(170)} = m T . (170)
For each task contribution on the right-hand side of Equation (E.65), we substitute Equation (E.60). Next, to calculate the right-hand side, we introduce the following proposition.
Proposition E.2 (Moments of the task projectors). Let B ∈ R D × D \mathbf{B}\in\mathbb{R}^{D\times D} B ∈ R D × D be any matrix independent of task μ \mu μ .
E μ [ P μ B P μ ] ≃ α 2 B + α ( 1 − α ) D ( B ⊤ + tr ( B ) I D ) , (171) \mathbb{E}_{\mu}[\mathbf{P}_{\mu}\mathbf{B}\mathbf{P}_{\mu}]\simeq\alpha^2\mathbf{B}+\frac{\alpha(1-\alpha)}{D}\left(\mathbf{B}^{\top}+\operatorname{tr}(\mathbf{B})I_D\right), \tag*{(171)} E μ [ P μ B P μ ] ≃ α 2 B + D α ( 1 − α ) ( B ⊤ + tr ( B ) I D ) , (171) E μ [ Q μ B Q μ ] ≃ ( K − 1 ) 2 D 2 B + K − 1 D 2 ( B ⊤ + tr ( B ) I D ) . (172) \mathbb{E}_{\mu}[\mathbf{Q}_{\mu}\mathbf{B}\mathbf{Q}_{\mu}]\simeq\frac{(K-1)^2}{D^2}\mathbf{B}+\frac{K-1}{D^2}\left(\mathbf{B}^{\top}+\operatorname{tr}(\mathbf{B})I_D\right). \tag*{(172)} E μ [ Q μ B Q μ ] ≃ D 2 ( K − 1 ) 2 B + D 2 K − 1 ( B ⊤ + tr ( B ) I D ) . (172)
Proof. Marginally, P μ \mathbf{P}_{\mu} P μ and Q μ \mathbf{Q}_{\mu} Q μ are rotationally invariant orthogonal projectors of ranks L L L and K − 1 K-1 K − 1 , respectively. The entrywise second moment of either projector has the form
E μ [ ( Π μ ) i j ( Π μ ) k l ] = a D , r δ i j δ k l + b D , r ( δ i k δ j l + δ i l δ j k ) , (173) \mathbb{E}_{\mu}[(\Pi_{\mu})_{ij}(\Pi_{\mu})_{kl}]=a_{D,r}\delta_{ij}\delta_{kl}+b_{D,r}(\delta_{ik}\delta_{jl}+\delta_{il}\delta_{jk}), \tag*{(173)} E μ [( Π μ ) ij ( Π μ ) k l ] = a D , r δ ij δ k l + b D , r ( δ ik δ j l + δ i l δ j k ) , (173)
where Π μ = P μ \Pi_\mu= P_\mu Π μ = P μ for r = L r = L r = L and Π μ = Q μ \Pi_\mu= Q_\mu Π μ = Q μ for r = K − 1 r = K - 1 r = K − 1 . Using ( tr Π μ ) 2 = r 2 (\operatorname{tr}\Pi_\mu)^2 = r^2 ( tr Π μ ) 2 = r 2 and tr ( Π μ 2 ) = r \operatorname{tr}(\Pi_\mu^2) = r tr ( Π μ 2 ) = r gives
D 2 a D , r + 2 D b D , r = r 2 , (174) D^2a_{D,r}+2Db_{D,r}=r^2, \tag*{(174)} D 2 a D , r + 2 D b D , r = r 2 , (174)
D a D , r + ( D 2 + D ) b D , r = r . (175) Da_{D,r}+(D^2+D)b_{D,r}=r. \tag*{(175)} D a D , r + ( D 2 + D ) b D , r = r . (175)
Solving these equations gives
a D , r = r [ r ( D + 1 ) − 2 ] D ( D − 1 ) ( D + 2 ) , (176) a_{D,r}=\frac{r[r(D+1)-2]}{D(D-1)(D+2)}, \tag*{(176)} a D , r = D ( D − 1 ) ( D + 2 ) r [ r ( D + 1 ) − 2 ] , (176)
b D , r = r ( D − r ) D ( D − 1 ) ( D + 2 ) . (177) b_{D,r}=\frac{r(D-r)}{D(D-1)(D+2)}. \tag*{(177)} b D , r = D ( D − 1 ) ( D + 2 ) r ( D − r ) . (177)
Therefore,
E μ [ ( Π μ B Π μ ) i l ] = ∑ j , k ( B ) j k E μ [ ( Π μ ) i j ( Π μ ) k l ] (178) \mathbb{E}_\mu[(\Pi_\mu B\Pi_\mu)_{il}]=\sum_{j,k}(B)_{jk}\mathbb{E}_\mu[(\Pi_\mu)_{ij}(\Pi_\mu)_{kl}] \tag*{(178)} E μ [( Π μ B Π μ ) i l ] = j , k ∑ ( B ) j k E μ [( Π μ ) ij ( Π μ ) k l ] (178)
= a D , r B i l + b D , r B l i + b D , r tr ( B ) δ i l . (179) =a_{D,r}B_{il}+b_{D,r}B_{li}+b_{D,r}\operatorname{tr}(B)\delta_{il}. \tag*{(179)} = a D , r B i l + b D , r B l i + b D , r tr ( B ) δ i l . (179)
Substituting r = L = α D r=L=\alpha D r = L = α D and r = K − 1 r=K-1 r = K − 1 , and expanding the coefficients at their retained large-D D D orders, gives Equation (E.70).
After substituting Equation (E.60), we use concentration of the normalized contractions around their conditional task averages. For μ ≠ ν \mu\ne\nu μ = ν , independence of the two tasks gives
E tr ( P μ P ν ) = tr ( E P μ E P ν ) = tr ( L D I D L D I D ) = L 2 D , (180) \mathbb{E}\operatorname{tr}(P_\mu P_\nu)=\operatorname{tr}(\mathbb{E}P_\mu\mathbb{E}P_\nu)=\operatorname{tr}\left(\frac{L}{D}I_D\frac{L}{D}I_D\right)=\frac{L^2}{D}, \tag*{(180)} E tr ( P μ P ν ) = tr ( E P μ E P ν ) = tr ( D L I D D L I D ) = D L 2 , (180)
E tr ( Q μ Q ν ) = tr ( E Q μ E Q ν ) = tr ( K − 1 D I D K − 1 D I D ) = ( K − 1 ) 2 D . (181) \mathbb{E}\operatorname{tr}(Q_\mu Q_\nu)=\operatorname{tr}(\mathbb{E}Q_\mu\mathbb{E}Q_\nu)=\operatorname{tr}\left(\frac{K-1}{D}I_D\frac{K-1}{D}I_D\right)=\frac{(K-1)^2}{D}. \tag*{(181)} E tr ( Q μ Q ν ) = tr ( E Q μ E Q ν ) = tr ( D K − 1 I D D K − 1 I D ) = D ( K − 1 ) 2 . (181)
We now calculate the two cases separately. For μ = ν \mu=\nu μ = ν , Equation (E.70) gives
{ 1 D 2 tr [ lim ϵ → 0 ϵ R ϵ − μ ] } m F = [ 1 − ( M − 1 ) L ( K − 1 ) D 2 ] m F (182) \left\{\frac{1}{D^2}\operatorname{tr}\left[\lim_{\epsilon\to0}\epsilon R^{-\mu}_\epsilon\right]\right\}m_{\mathrm F}=\left[1-\frac{(M-1)L(K-1)}{D^2}\right]m_{\mathrm F} \tag*{(182)} { D 2 1 tr [ ϵ → 0 lim ϵ R ϵ − μ ] } m F = [ 1 − D 2 ( M − 1 ) L ( K − 1 ) ] m F (182)
→ ( 1 − α φ ) m F . (183) \to(1-\alpha\varphi)m_{\mathrm F}. \tag*{(183)} → ( 1 − α φ ) m F . (183)
For μ ≠ ν \mu\ne\nu μ = ν , independence of the two tasks gives
∑ ν ≠ μ 1 K − 1 E tr ( Q μ Q ν ) 1 D E tr ( P μ P ν ) m T (184) \sum_{\nu\ne\mu}\frac{1}{K-1}\mathbb{E}\operatorname{tr}(Q_\mu Q_\nu)\frac{1}{D}\mathbb{E}\operatorname{tr}(P_\mu P_\nu)m_{\mathrm T} \tag*{(184)} ν = μ ∑ K − 1 1 E tr ( Q μ Q ν ) D 1 E tr ( P μ P ν ) m T (184)
= ( M − 1 ) 1 K − 1 ( K − 1 ) 2 D 1 D L 2 D m T (185) =(M-1)\frac{1}{K-1}\frac{(K-1)^2}{D}\frac{1}{D}\frac{L^2}{D}m_{\mathrm T} \tag*{(185)} = ( M − 1 ) K − 1 1 D ( K − 1 ) 2 D 1 D L 2 m T (185)
= ( M − 1 ) K − 1 D L 2 D 2 m T (186) =(M-1)\frac{K-1}{D}\frac{L^2}{D^2}m_{\mathrm T} \tag*{(186)} = ( M − 1 ) D K − 1 D 2 L 2 m T (186)
→ α 2 φ m T . (187) \to\alpha^2\varphi m_{\mathrm T}. \tag*{(187)} → α 2 φ m T . (187)
Equating the two sides of Equation (E.65) gives
m T = lim D → ∞ [ 1 − ( M − 1 ) L ( K − 1 ) D 2 ] m F + lim D → ∞ ( M − 1 ) K − 1 D L 2 D 2 m T (188) m_{\mathrm T}=\lim_{D\to\infty}\left[1-\frac{(M-1)L(K-1)}{D^2}\right]m_{\mathrm F}+\lim_{D\to\infty}(M-1)\frac{K-1}{D}\frac{L^2}{D^2}m_{\mathrm T} \tag*{(188)} m T = D → ∞ lim [ 1 − D 2 ( M − 1 ) L ( K − 1 ) ] m F + D → ∞ lim ( M − 1 ) D K − 1 D 2 L 2 m T (188)
= ( 1 − α φ ) m F + α 2 φ m T , (189) =(1-\alpha\varphi)m_{\mathrm F}+\alpha^2\varphi m_{\mathrm T}, \tag*{(189)} = ( 1 − α φ ) m F + α 2 φ m T , (189)
which gives
m T η 2 = φ ( 1 − α φ ) 2 [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) . (190) \frac{m_{\mathrm T}}{\eta^2}=\frac{\varphi(1-\alpha\varphi)^2}{[1+(1-\alpha)\varphi]^2(1-\alpha^2\varphi)}. \tag*{(190)} η 2 m T = [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) φ ( 1 − α φ ) 2 . (190)
Since the centered matrix has zero normalized trace,
lim D → ∞ tr ( A ^ 2 ) η 2 D = χ 2 + m T η 2 = φ [ 1 + ( 1 − 2 α ) φ ] [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) . (191) \lim_{D\to\infty}\frac{\operatorname{tr}(\hat{A}^2)}{\eta^2D}=\chi^2+\frac{m_{\mathrm T}}{\eta^2}=\frac{\varphi[1+(1-2\alpha)\varphi]}{[1+(1-\alpha)\varphi]^2(1-\alpha^2\varphi)}. \tag*{(191)} D → ∞ lim η 2 D tr ( A ^ 2 ) = χ 2 + η 2 m T = [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) φ [ 1 + ( 1 − 2 α ) φ ] . (191)
This proves Equation (E.3).
Moment-matched Gaussian effective matrix
Proposition E.1 determines the normalized trace, Frobenius norm, and transpose moment of A ^ \hat{A} A ^ . Directly analyzing the resolvent of A ^ \hat{A} A ^ is difficult, so, following Takanami et al. (2026), we introduce a tractable Gaussian surrogate for A ^ \hat{A} A ^ . This replacement is an assumption, but we expect it to become accurate in the high-dimensional limit. Specifically, the surrogate matrix is chosen to reproduce the normalized trace, Frobenius norm, and transpose moment in Proposition E.1 .
Let
r = rank ( ∑ μ = 1 M Q μ ) = min { D , M ( K − 1 ) } . (192) r=\operatorname{rank}\left(\sum_{\mu=1}^{M}\mathbf{Q}_{\mu}\right)=\min\{D,M(K-1)\}. \tag*{(192)} r = rank ( μ = 1 ∑ M Q μ ) = min { D , M ( K − 1 )} . (192)
Define O ∥ ∈ R D × r \mathbf{O}_{\parallel}\in\mathbb{R}^{D\times r} O ∥ ∈ R D × r as the matrix whose columns are orthonormal eigenvectors of ∑ μ = 1 M Q μ \sum_{\mu=1}^{M}\mathbf{Q}_{\mu} ∑ μ = 1 M Q μ corresponding to its nonzero eigenvalues. Define O ⊥ ∈ R D × ( D − r ) \mathbf{O}_{\perp}\in\mathbb{R}^{D\times(D-r)} O ⊥ ∈ R D × ( D − r ) as an orthonormal basis of the null space of ∑ μ = 1 M Q μ \sum_{\mu=1}^{M}\mathbf{Q}_{\mu} ∑ μ = 1 M Q μ . Then we have
∑ μ = 1 M Q μ = O ∥ diag ( x 1 , … , x r ) O ∥ T , x 1 , … , x r > 0 , ( O ∥ , O ⊥ ) T ( O ∥ , O ⊥ ) = I D . (193) \sum_{\mu=1}^{M}\mathbf{Q}_{\mu}=\mathbf{O}_{\parallel}\operatorname{diag}(x_{1},\ldots,x_{r})\mathbf{O}_{\parallel}^{\mathsf{T}},\qquad x_{1},\ldots,x_{r}>0,\qquad(\mathbf{O}_{\parallel},\mathbf{O}_{\perp})^{\mathsf{T}}(\mathbf{O}_{\parallel},\mathbf{O}_{\perp})=\mathbf{I}_{D}. \tag*{(193)} μ = 1 ∑ M Q μ = O ∥ diag ( x 1 , … , x r ) O ∥ T , x 1 , … , x r > 0 , ( O ∥ , O ⊥ ) T ( O ∥ , O ⊥ ) = I D . (193)
Proposition E.3 (Moment-matched effective expression). Suppose 0 < α < 1 0<\alpha<1 0 < α < 1 , 0 < φ < 1 / α 0<\varphi<1/\alpha 0 < φ < 1/ α , and λ → 0 \lambda\to0 λ → 0 . Define A ^ e f f \hat{\mathbf{A}}_{\mathrm{eff}} A ^ eff by
A ^ e f f O ∥ η = − O ∥ diag j x j u φ + v φ x j O ∥ T + W D diag j c φ x j u φ + v φ x j O ∥ T , (194) \frac{\hat{\mathbf{A}}_{\mathrm{eff}}\mathbf{O}_{\parallel}}{\eta}=-\mathbf{O}_{\parallel}\operatorname{diag}_{j}\frac{x_{j}}{u_{\varphi}+v_{\varphi}x_{j}}\mathbf{O}_{\parallel}^{\mathsf{T}}+\frac{\mathbf{W}}{\sqrt{D}}\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}\mathbf{O}_{\parallel}^{\mathsf{T}}, \tag*{(194)} η A ^ eff O ∥ = − O ∥ diag j u φ + v φ x j x j O ∥ T + D W diag j u φ + v φ x j c φ x j O ∥ T , (194) A ^ e f f O ⊥ = 0 , (195) \hat{\mathbf{A}}_{\mathrm{eff}}\mathbf{O}_{\perp}=0, \tag*{(195)} A ^ eff O ⊥ = 0 , (195) where W ∈ R D × r \mathbf{W}\in\mathbb{R}^{D\times r} W ∈ R D × r has independent N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) entries, and
u φ = ( 1 − α ) ( 1 − α φ ) [ 1 + ( 1 − α ) φ ] , (196) u_{\varphi}=(1-\alpha)(1-\alpha\varphi)[1+(1-\alpha)\varphi], \tag*{(196)} u φ = ( 1 − α ) ( 1 − α φ ) [ 1 + ( 1 − α ) φ ] , (196) v φ = α [ 1 + ( 1 − α ) φ ] , (197) v_{\varphi}=\alpha[1+(1-\alpha)\varphi], \tag*{(197)} v φ = α [ 1 + ( 1 − α ) φ ] , (197) c φ = α ( 1 − α ) φ ( 1 − α φ ) . (198) c_{\varphi}=\alpha(1-\alpha)\varphi(1-\alpha\varphi). \tag*{(198)} c φ = α ( 1 − α ) φ ( 1 − α φ ) . (198) Then
− lim D → ∞ tr A ^ e f f η D = lim D → ∞ ∥ A ^ e f f ∥ F 2 η 2 D = φ 1 + ( 1 − α ) φ , (199) -\lim_{D\to\infty}\frac{\operatorname{tr}\hat{\mathbf{A}}_{\mathrm{eff}}}{\eta D}=\lim_{D\to\infty}\frac{\lVert\hat{\mathbf{A}}_{\mathrm{eff}}\rVert_{\mathrm{F}}^{2}}{\eta^{2}D}=\frac{\varphi}{1+(1-\alpha)\varphi}, \tag*{(199)} − D → ∞ lim η D tr A ^ eff = D → ∞ lim η 2 D ∥ A ^ eff ∥ F 2 = 1 + ( 1 − α ) φ φ , (199) lim D → ∞ tr ( A ^ e f f 2 ) η 2 D = φ [ 1 + ( 1 − 2 α ) φ ] [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) . (200) \lim_{D\to\infty}\frac{\operatorname{tr}(\hat{\mathbf{A}}_{\mathrm{eff}}^{2})}{\eta^{2}D}=\frac{\varphi[1+(1-2\alpha)\varphi]}{[1+(1-\alpha)\varphi]^{2}(1-\alpha^{2}\varphi)}. \tag*{(200)} D → ∞ lim η 2 D tr ( A ^ eff 2 ) = [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) φ [ 1 + ( 1 − 2 α ) φ ] . (200)
Proof. For fixed K K K , the nonzero eigenvalues x j x_{j} x j of ∑ μ Q μ \sum_{\mu} \mathbf{Q}_{\mu} ∑ μ Q μ obey the Marchenko–Pastur law ν 1 / φ \nu_{1/\varphi} ν 1/ φ defined in Equation (21) . Thus, for f ( 0 ) = 0 f(0)=0 f ( 0 ) = 0 ,
1 D ∑ j = 1 r f ( x j ) ⟶ φ ⟨ f ⟩ 1 / φ . (201) \frac{1}{D}\sum_{j=1}^{r}f(x_{j})\longrightarrow\varphi\langle f\rangle_{1/\varphi}. \tag*{(201)} D 1 j = 1 ∑ r f ( x j ) ⟶ φ ⟨ f ⟩ 1/ φ . (201)
For φ > 1 \varphi>1 φ > 1 , ν 1 / φ \nu_{1/\varphi} ν 1/ φ has a zero atom of mass 1 − 1 / φ 1-1/\varphi 1 − 1/ φ .
Since A ^ e f f O ⊥ = 0 \hat{\mathbf{A}}_{\mathrm{eff}}\mathbf{O}_{\perp}=0 A ^ eff O ⊥ = 0 , Equation (E.93) gives
A ^ e f f η = − O ∥ diag j x j u φ + v φ x j O ∥ T + W D diag j c φ x j u φ + v φ x j O ∥ T . (202) \frac{\hat{\mathbf{A}}_{\mathrm{eff}}}{\eta}=-\mathbf{O}_{\parallel}\operatorname{diag}_{j}\frac{x_{j}}{u_{\varphi}+v_{\varphi}x_{j}}\mathbf{O}_{\parallel}^{\mathsf{T}}+\frac{\mathbf{W}}{\sqrt{D}}\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}\mathbf{O}_{\parallel}^{\mathsf{T}}. \tag*{(202)} η A ^ eff = − O ∥ diag j u φ + v φ x j x j O ∥ T + D W diag j u φ + v φ x j c φ x j O ∥ T . (202)
Therefore, the normalized trace satisfies
− tr A ^ e f f η D = 1 D ∑ j = 1 r x j u φ + v φ x j − 1 D D tr [ W diag j c φ x j u φ + v φ x j O ∥ T ] (203) -\frac{\operatorname{tr}\hat{\mathbf{A}}_{\mathrm{eff}}}{\eta D}=\frac{1}{D}\sum_{j=1}^{r}\frac{x_{j}}{u_{\varphi}+v_{\varphi}x_{j}}-\frac{1}{D\sqrt{D}}\operatorname{tr}\left[\mathbf{W}\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}\mathbf{O}_{\parallel}^{\mathsf{T}}\right] \tag*{(203)} − η D tr A ^ eff = D 1 j = 1 ∑ r u φ + v φ x j x j − D D 1 tr [ W diag j u φ + v φ x j c φ x j O ∥ T ] (203)
⟶ φ ⟨ x u φ + v φ x ⟩ 1 / φ . (204) \longrightarrow\varphi\left\langle\frac{x}{u_{\varphi}+v_{\varphi}x}\right\rangle_{1/\varphi}. \tag*{(204)} ⟶ φ ⟨ u φ + v φ x x ⟩ 1/ φ . (204)
Expanding the trace of the square gives
tr ( A ^ e f f 2 ) η 2 D = 1 D tr [ ( − O ∥ diag j x j u φ + v φ x j O ∥ T + W D diag j c φ x j u φ + v φ x j O ∥ T ) 2 ] = 1 D ∑ j = 1 r x j 2 ( u φ + v φ x j ) 2 − 2 D D tr [ O ∥ diag j x j u φ + v φ x j O ∥ T W diag j c φ x j u φ + v φ x j O ∥ T ] (205) \begin{aligned}
\frac{\operatorname{tr}(\widehat{A}_{\mathrm{eff}}^{2})}{\eta^{2}D}
&= \frac{1}{D}\operatorname{tr}\left[\left(-O_{\parallel}\operatorname{diag}_{j}\frac{x_{j}}{u_{\varphi}+v_{\varphi}x_{j}}O_{\parallel}^{\mathsf{T}}+\frac{W}{\sqrt{D}}\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}O_{\parallel}^{\mathsf{T}}\right)^{2}\right] \\
&= \frac{1}{D}\sum_{j=1}^{r}\frac{x_{j}^{2}}{(u_{\varphi}+v_{\varphi}x_{j})^{2}}-\frac{2}{D\sqrt{D}}\operatorname{tr}\left[O_{\parallel}\operatorname{diag}_{j}\frac{x_{j}}{u_{\varphi}+v_{\varphi}x_{j}}O_{\parallel}^{\mathsf{T}}W\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}O_{\parallel}^{\mathsf{T}}\right] \tag*{(205)}
\end{aligned} η 2 D tr ( A eff 2 ) = D 1 tr [ ( − O ∥ diag j u φ + v φ x j x j O ∥ T + D W diag j u φ + v φ x j c φ x j O ∥ T ) 2 ] = D 1 j = 1 ∑ r ( u φ + v φ x j ) 2 x j 2 − D D 2 tr [ O ∥ diag j u φ + v φ x j x j O ∥ T W diag j u φ + v φ x j c φ x j O ∥ T ] (205)
∥ A ^ e f f ∥ F 2 η 2 D = 1 D tr [ ( − O ∥ diag j x j u φ + v φ x j O ∥ T + W D diag j c φ x j u φ + v φ x j O ∥ T ) T × ( − O ∥ diag j x j u φ + v φ x j O ∥ T + W D diag j c φ x j u φ + v φ x j O ∥ T ) ] = 1 D ∑ j = 1 r x j 2 ( u φ + v φ x j ) 2 − 2 D D tr [ diag j x j u φ + v φ x j O ∥ T W diag j c φ x j u φ + v φ x j ] (206) \begin{aligned}
\frac{\lVert\widehat{A}_{\mathrm{eff}}\rVert_{F}^{2}}{\eta^{2}D}
&= \frac{1}{D}\operatorname{tr}\left[\left(-O_{\parallel}\operatorname{diag}_{j}\frac{x_{j}}{u_{\varphi}+v_{\varphi}x_{j}}O_{\parallel}^{\mathsf{T}}+\frac{W}{\sqrt{D}}\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}O_{\parallel}^{\mathsf{T}}\right)^{\mathsf{T}}\right.\\
&\qquad\left.\times\left(-O_{\parallel}\operatorname{diag}_{j}\frac{x_{j}}{u_{\varphi}+v_{\varphi}x_{j}}O_{\parallel}^{\mathsf{T}}+\frac{W}{\sqrt{D}}\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}O_{\parallel}^{\mathsf{T}}\right)\right] \\
&= \frac{1}{D}\sum_{j=1}^{r}\frac{x_{j}^{2}}{(u_{\varphi}+v_{\varphi}x_{j})^{2}}-\frac{2}{D\sqrt{D}}\operatorname{tr}\left[\operatorname{diag}_{j}\frac{x_{j}}{u_{\varphi}+v_{\varphi}x_{j}}O_{\parallel}^{\mathsf{T}}W\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}\right] \tag*{(206)}
\end{aligned} η 2 D ∥ A eff ∥ F 2 = D 1 tr [ ( − O ∥ diag j u φ + v φ x j x j O ∥ T + D W diag j u φ + v φ x j c φ x j O ∥ T ) T × ( − O ∥ diag j u φ + v φ x j x j O ∥ T + D W diag j u φ + v φ x j c φ x j O ∥ T ) ] = D 1 j = 1 ∑ r ( u φ + v φ x j ) 2 x j 2 − D D 2 tr [ diag j u φ + v φ x j x j O ∥ T W diag j u φ + v φ x j c φ x j ] (206)
+ 1 D 2 tr [ diag j c φ x j u φ + v φ x j W T W diag j c φ x j u φ + v φ x j ] (207) +\frac{1}{D^{2}}\operatorname{tr}\left[\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}W^{\mathsf{T}}W\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}\right] \tag*{(207)} + D 2 1 tr [ diag j u φ + v φ x j c φ x j W T W diag j u φ + v φ x j c φ x j ] (207)
= 1 D ∑ j = 1 r x j 2 ( u φ + v φ x j ) 2 + 1 D ∑ j = 1 r c φ x j ( u φ + v φ x j ) 2 + o P ( 1 ) = 1 D ∑ j = 1 r x j 2 + c φ x j ( u φ + v φ x j ) 2 + o P ( 1 ) → φ ⟨ x 2 + c φ x ( u φ + v φ x ) 2 ⟩ 1 / φ . (208) \begin{aligned}
&= \frac{1}{D}\sum_{j=1}^{r}\frac{x_{j}^{2}}{(u_{\varphi}+v_{\varphi}x_{j})^{2}}+\frac{1}{D}\sum_{j=1}^{r}\frac{c_{\varphi}x_{j}}{(u_{\varphi}+v_{\varphi}x_{j})^{2}}+o_{P}(1) \\
&= \frac{1}{D}\sum_{j=1}^{r}\frac{x_{j}^{2}+c_{\varphi}x_{j}}{(u_{\varphi}+v_{\varphi}x_{j})^{2}}+o_{P}(1) \\
&\xrightarrow{\varphi}\left\langle\frac{x^{2}+c_{\varphi}x}{(u_{\varphi}+v_{\varphi}x)^{2}}\right\rangle_{1/\varphi}. \tag*{(208)}
\end{aligned} = D 1 j = 1 ∑ r ( u φ + v φ x j ) 2 x j 2 + D 1 j = 1 ∑ r ( u φ + v φ x j ) 2 c φ x j + o P ( 1 ) = D 1 j = 1 ∑ r ( u φ + v φ x j ) 2 x j 2 + c φ x j + o P ( 1 ) φ ⟨ ( u φ + v φ x ) 2 x 2 + c φ x ⟩ 1/ φ . (208)
Here we used O ∥ T O ∥ = I r O_{\parallel}^{\mathsf{T}}O_{\parallel}=I_{r} O ∥ T O ∥ = I r and the cyclicity of the trace to combine the two cross terms. Conditional on ( x j , O ∥ ) (x_{j},O_{\parallel}) ( x j , O ∥ ) , the entries of O ∥ T W O_{\parallel}^{\mathsf{T}}W O ∥ T W are independent standard Gaussians. Consequently, the cross terms in both displays and the final Gaussian term in the trace-of-the-square display are o P ( 1 ) o_{P}(1) o P ( 1 ) . In the Frobenius display, D − 1 W T W D^{-1}W^{\mathsf{T}}W D − 1 W T W instead contributes I r I_{r} I r inside the normalized trace. Equation (E.99) then gives the two displayed limits.
The Marchenko–Pastur equation gives
⟨ 1 ( 1 − α ) ( 1 − α φ ) + α x ⟩ 1 / φ = 1 1 − α φ . (209) \left\langle\frac{1}{(1-\alpha)(1-\alpha\varphi)+\alpha x}\right\rangle_{1/\varphi}=\frac{1}{1-\alpha\varphi}. \tag*{(209)} ⟨ ( 1 − α ) ( 1 − α φ ) + α x 1 ⟩ 1/ φ = 1 − α φ 1 . (209)
Consequently,
⟨ x u φ + v φ x ⟩ 1 / φ = 1 v φ [ 1 − u φ v φ ⟨ 1 u φ / v φ + x ⟩ 1 / φ ] (210) \left\langle\frac{x}{u_{\varphi}+v_{\varphi}x}\right\rangle_{1/\varphi}
=\frac{1}{v_{\varphi}}\left[1-\frac{u_{\varphi}}{v_{\varphi}}\left\langle\frac{1}{u_{\varphi}/v_{\varphi}+x}\right\rangle_{1/\varphi}\right] \tag*{(210)} ⟨ u φ + v φ x x ⟩ 1/ φ = v φ 1 [ 1 − v φ u φ ⟨ u φ / v φ + x 1 ⟩ 1/ φ ] (210)
= 1 v φ [ 1 − ( 1 − α ) ] (211) =\frac{1}{v_{\varphi}}\left[1-(1-\alpha)\right] \tag*{(211)} = v φ 1 [ 1 − ( 1 − α ) ] (211)
= α v φ (212) =\frac{\alpha}{v_{\varphi}} \tag*{(212)} = v φ α (212)
= 1 1 + ( 1 − α ) φ . (213) =\frac{1}{1+(1-\alpha)\varphi}. \tag*{(213)} = 1 + ( 1 − α ) φ 1 . (213)
The MP equation and its derivative then give
⟨ x 2 ( u φ + v φ x ) 2 ⟩ 1 / φ = 1 + ( 1 − 2 α ) φ [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) , (214) \left\langle\frac{x^2}{(u_{\varphi}+v_{\varphi}x)^2}\right\rangle_{1/\varphi}
=\frac{1+(1-2\alpha)\varphi}{[1+(1-\alpha)\varphi]^2(1-\alpha^2\varphi)}, \tag*{(214)} ⟨ ( u φ + v φ x ) 2 x 2 ⟩ 1/ φ = [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) 1 + ( 1 − 2 α ) φ , (214)
⟨ x ( u φ + v φ x ) 2 ⟩ 1 / φ = 1 [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) . (215) \left\langle\frac{x}{(u_{\varphi}+v_{\varphi}x)^2}\right\rangle_{1/\varphi}
=\frac{1}{[1+(1-\alpha)\varphi]^2(1-\alpha^2\varphi)}. \tag*{(215)} ⟨ ( u φ + v φ x ) 2 x ⟩ 1/ φ = [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) 1 . (215)
Substitution into Equation (E.102) gives
− lim D → ∞ tr A ^ e f f η D = φ 1 + ( 1 − α ) φ . (216) -\lim_{D\to\infty}\frac{\operatorname{tr}\widehat{A}_{\mathrm{eff}}}{\eta D}
=\frac{\varphi}{1+(1-\alpha)\varphi}. \tag*{(216)} − D → ∞ lim η D tr A eff = 1 + ( 1 − α ) φ φ . (216)
Substitution into Equation (E.105) gives
lim D → ∞ tr ( A ^ e f f 2 ) η 2 D = φ [ 1 + ( 1 − 2 α ) φ ] [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) . (217) \lim_{D\to\infty}\frac{\operatorname{tr}(\widehat{A}_{\mathrm{eff}}^2)}{\eta^2D}
=\frac{\varphi[1+(1-2\alpha)\varphi]}{[1+(1-\alpha)\varphi]^2(1-\alpha^2\varphi)}. \tag*{(217)} D → ∞ lim η 2 D tr ( A eff 2 ) = [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) φ [ 1 + ( 1 − 2 α ) φ ] . (217)
Finally, substitution into Equation (E.108) gives
lim D → ∞ ∥ A ^ e f f ∥ F 2 η 2 D = φ [ 1 + ( 1 − 2 α ) φ + c φ φ ] [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) (218) \lim_{D\to\infty}\frac{\lVert\widehat{A}_{\mathrm{eff}}\rVert_F^2}{\eta^2D}
=\frac{\varphi[1+(1-2\alpha)\varphi+c_{\varphi}\varphi]}{[1+(1-\alpha)\varphi]^2(1-\alpha^2\varphi)} \tag*{(218)} D → ∞ lim η 2 D ∥ A eff ∥ F 2 = [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) φ [ 1 + ( 1 − 2 α ) φ + c φ φ ] (218)
= φ [ 1 + ( 1 − α ) φ ] ( 1 − α 2 φ ) [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) (219) =\frac{\varphi[1+(1-\alpha)\varphi](1-\alpha^2\varphi)}{[1+(1-\alpha)\varphi]^2(1-\alpha^2\varphi)} \tag*{(219)} = [ 1 + ( 1 − α ) φ ] 2 ( 1 − α 2 φ ) φ [ 1 + ( 1 − α ) φ ] ( 1 − α 2 φ ) (219)
= φ 1 + ( 1 − α ) φ . (220) =\frac{\varphi}{1+(1-\alpha)\varphi}. \tag*{(220)} = 1 + ( 1 − α ) φ φ . (220)
Hence the three moments agree with Proposition E.1.
Proposition E.4 (GD recovery for rank-deficient contexts). Suppose 0 < α < 1 0<\alpha<1 0 < α < 1 , α φ > 1 \alpha\varphi>1 α φ > 1 , and λ → 0 \lambda\to0 λ → 0 . Under the same cavity approximation as in Proposition E.1, the effective learned matrix satisfies
A ^ e f f = − η I D . (221) \widehat{A}_{\mathrm{eff}}=-\eta I_D. \tag*{(221)} A eff = − η I D . (221) Consequently,
E ( t ) = E G D ( t ) . (222) \mathcal{E}(t)=\mathcal{E}_{\mathrm{GD}}(t). \tag*{(222)} E ( t ) = E GD ( t ) . (222) Proof. Let
Z 0 : = lim ϵ → 0 ϵ R ϵ , (223) Z_0:=\lim_{\epsilon\to0}\epsilon R_{\epsilon}, \tag*{(223)} Z 0 := ϵ → 0 lim ϵ R ϵ , (223) where R ϵ R_{\epsilon} R ϵ is defined in Equation (E.9). Equation (E.11) gives
vec ( A ^ e f f + η I D ) = η Z 0 vec I D . (224) \operatorname{vec}(\widehat{A}_{\mathrm{eff}}+\eta I_D)=\eta Z_0\operatorname{vec} I_D. \tag*{(224)} vec ( A eff + η I D ) = η Z 0 vec I D . (224) Applying the standard Wishart resolvent calculation gives the leading small-ϵ \epsilon ϵ equation for ρ ϵ : = D − 2 tr R ϵ \rho_{\epsilon}:=D^{-2}\operatorname{tr}R_{\epsilon} ρ ϵ := D − 2 tr R ϵ :
ϵ ρ ϵ 2 − ( 1 − α φ ) ρ ϵ − a K , α = o ( 1 ) , a K , α > 0. (225) \epsilon\rho_{\epsilon}^2-(1-\alpha\varphi)\rho_{\epsilon}-a_{K,\alpha}=o(1),\qquad a_{K,\alpha}>0. \tag*{(225)} ϵ ρ ϵ 2 − ( 1 − α φ ) ρ ϵ − a K , α = o ( 1 ) , a K , α > 0. (225) Its positive solution is
ρ ϵ = 1 − α φ + ( 1 − α φ ) 2 + 4 ϵ a K , α 2 ϵ + o ( 1 ) . (226) \rho_{\epsilon}=\frac{1-\alpha\varphi+\sqrt{(1-\alpha\varphi)^2+4\epsilon a_{K,\alpha}}}{2\epsilon}+o(1). \tag*{(226)} ρ ϵ = 2 ϵ 1 − α φ + ( 1 − α φ ) 2 + 4 ϵ a K , α + o ( 1 ) . (226)
When α φ > 1 \alpha\varphi> 1 α φ > 1 , the two terms in the numerator cancel at leading order and ρ ϵ → a K , α / ( α φ − 1 ) \rho_{\epsilon} \to a_{K,\alpha}/(\alpha\varphi- 1) ρ ϵ → a K , α / ( α φ − 1 ) . Therefore
lim D → ∞ 1 D 2 tr Z 0 = lim ϵ → 0 ϵ ρ ϵ = 0. (227) \lim_{D\to\infty} \frac{1}{D^2}\operatorname{tr} Z_0 = \lim_{\epsilon\to0} \epsilon\rho_{\epsilon} = 0. \tag*{(227)} D → ∞ lim D 2 1 tr Z 0 = ϵ → 0 lim ϵ ρ ϵ = 0. (227)
Since Z 0 Z_0 Z 0 is the orthogonal projector onto the kernel of ∑ μ Q μ ⊗ P μ \sum_{\mu} Q_{\mu}\otimes P_{\mu} ∑ μ Q μ ⊗ P μ , this gives Z 0 = 0 Z_0=0 Z 0 = 0 in the effective large-D D D description. Equation (E.124) then gives Equation (E.121). Proposition C.3 completes the proof.
For the remainder of the cavity calculation, we therefore use the replacement
A ^ ⟶ A ^ e f f . (228) \widehat{A} \longrightarrow\widehat{A}_{\mathrm{eff}}. \tag*{(228)} A ⟶ A eff . (228)
To avoid additional notation, we write A ^ \widehat{A} A for A ^ e f f \widehat{A}_{\mathrm{eff}} A eff after Equation (E.128).
Resolvent calculation
We now use Equation (E.93) to calculate the two resolvents needed to determine φ − \varphi_{-} φ − and φ + \varphi_{+} φ + . As a preparation, we calculate two scalar functions below:
r φ ( y ) : = lim D → ∞ 1 D tr ( I D − y A ^ / η ) − 1 , (229) r_{\varphi}(y) := \lim_{D\to\infty} \frac{1}{D}\operatorname{tr}\left(I_D-y\widehat{A}/\eta\right)^{-1}, \tag*{(229)} r φ ( y ) := D → ∞ lim D 1 tr ( I D − y A / η ) − 1 , (229)
G φ ( y ) : = lim D → ∞ 1 D ∥ ( I D − y A ^ / η ) − 1 ∥ F 2 . (230) G_{\varphi}(y) := \lim_{D\to\infty} \frac{1}{D}\left\|\left(I_D-y\widehat{A}/\eta\right)^{-1}\right\|_{\mathrm{F}}^2. \tag*{(230)} G φ ( y ) := D → ∞ lim D 1 ( I D − y A / η ) − 1 F 2 . (230)
These resolvent quantities are given by the following proposition.
Proposition E.5 (Resolvents of the effective matrix). For sufficiently small y y y ,
r φ ( y ) = 1 − φ + φ ⟨ u φ + v φ x u φ + ( v φ + y ) x ⟩ 1 / φ , (231) r_{\varphi}(y)=1-\varphi+\varphi\left\langle\frac{u_{\varphi}+v_{\varphi}x}{u_{\varphi}+(v_{\varphi}+y)x}\right\rangle_{1/\varphi}, \tag*{(231)} r φ ( y ) = 1 − φ + φ ⟨ u φ + ( v φ + y ) x u φ + v φ x ⟩ 1/ φ , (231) G φ ( y ) = 1 − φ + φ ⟨ ( u φ + v φ x ) 2 / [ u φ + ( v φ + y ) x ] 2 ⟩ 1 / φ 1 − φ y 2 c φ ⟨ x / [ u φ + ( v φ + y ) x ] 2 ⟩ 1 / φ . (232) G_{\varphi}(y)=\frac{1-\varphi+\varphi\left\langle(u_{\varphi}+v_{\varphi}x)^2/[u_{\varphi}+(v_{\varphi}+y)x]^2\right\rangle_{1/\varphi}}{1-\varphi y^2 c_{\varphi}\left\langle x/[u_{\varphi}+(v_{\varphi}+y)x]^2\right\rangle_{1/\varphi}}. \tag*{(232)} G φ ( y ) = 1 − φ y 2 c φ ⟨ x / [ u φ + ( v φ + y ) x ] 2 ⟩ 1/ φ 1 − φ + φ ⟨ ( u φ + v φ x ) 2 / [ u φ + ( v φ + y ) x ] 2 ⟩ 1/ φ . (232)
Proof.
Calculation of r φ ( y ) r_{\varphi}(y) r φ ( y ) . The effective matrix vanishes on the subspace spanned by O ⊥ O_{\perp} O ⊥ , so the inverse is the identity on this subspace. It remains to calculate the inverse on the subspace spanned by O ∥ O_{\parallel} O ∥ . For sufficiently small y y y , factoring the deterministic diagonal matrix in Equation (E.93) gives the convergent expansion
O ∥ T ( I D − y A ^ / η ) − 1 O ∥ = diag j ( u φ + v φ x j u φ + ( v φ + y ) x j ) ∑ n = 0 ∞ [ y D O ∥ T W diag j ( c φ x j u φ + ( v φ + y ) x j ) ] n . (233) O_{\parallel}^{\mathsf{T}}\left(I_D-y\widehat{A}/\eta\right)^{-1}O_{\parallel}
=
\operatorname{diag}_{j}\left(\frac{u_{\varphi}+v_{\varphi}x_j}{u_{\varphi}+(v_{\varphi}+y)x_j}\right)
\sum_{n=0}^{\infty}
\left[
\frac{y}{\sqrt{D}}O_{\parallel}^{\mathsf{T}}W\operatorname{diag}_{j}\left(\frac{\sqrt{c_{\varphi}x_j}}{u_{\varphi}+(v_{\varphi}+y)x_j}\right)
\right]^n. \tag*{(233)} O ∥ T ( I D − y A / η ) − 1 O ∥ = diag j ( u φ + ( v φ + y ) x j u φ + v φ x j ) n = 0 ∑ ∞ [ D y O ∥ T W diag j ( u φ + ( v φ + y ) x j c φ x j ) ] n . (233)
Conditional on O ∥ O_{\parallel} O ∥ and x 1 , … , x r x_1,\ldots,x_r x 1 , … , x r , the entries of O ∥ T W O_{\parallel}^{\mathsf{T}}W O ∥ T W are independent standard Gaussians. Writing i n + 1 = i 1 i_{n+1}=i_1 i n + 1 = i 1 , the normalized trace of the n n n -th term in Equation (E.133) is
y n D 1 + n / 2 ∑ i 1 , … , i n = 1 r u φ + v φ x i 1 u φ + ( v φ + y ) x i 1 ∏ k = 1 n c φ x i k + 1 u φ + ( v φ + y ) x i k + 1 ∏ k = 1 n ( O ∥ T W ) i k i k + 1 . (234) \frac{y^n}{D^{1+n/2}}\sum_{i_1,\ldots,i_n=1}^{r}
\frac{u_{\varphi}+v_{\varphi}x_{i_1}}{u_{\varphi}+(v_{\varphi}+y)x_{i_1}}
\prod_{k=1}^{n}\frac{\sqrt{c_{\varphi}x_{i_{k+1}}}}{u_{\varphi}+(v_{\varphi}+y)x_{i_{k+1}}}
\prod_{k=1}^{n}(O_{\parallel}^{\mathsf{T}}W)_{i_k i_{k+1}}. \tag*{(234)} D 1 + n /2 y n i 1 , … , i n = 1 ∑ r u φ + ( v φ + y ) x i 1 u φ + v φ x i 1 k = 1 ∏ n u φ + ( v φ + y ) x i k + 1 c φ x i k + 1 k = 1 ∏ n ( O ∥ T W ) i k i k + 1 . (234)
For odd n n n , its conditional Gaussian expectation is zero. For even n n n , Wick’s rule pairs the factors according to
E [ ( O ∥ T W ) i j ( O ∥ T W ) k l ] = δ i k δ j l . (235) \mathbb{E}\left[(O_{\parallel}^{\mathsf{T}}W)_{ij}(O_{\parallel}^{\mathsf{T}}W)_{kl}\right]=\delta_{ik}\delta_{jl}. \tag*{(235)} E [ ( O ∥ T W ) ij ( O ∥ T W ) k l ] = δ ik δ j l . (235)
Each pairing leaves at most n / 2 n/2 n /2 free indices in the cyclic product, so for fixed n ≥ 2 n\geq2 n ≥ 2 the normalized expected trace is
O ( D n / 2 D 1 + n / 2 ) = O ( D − 1 ) ⟶ 0. (236) O\left(\frac{D^{n/2}}{D^{1+n/2}}\right)=O(D^{-1})\longrightarrow0. \tag*{(236)} O ( D 1 + n /2 D n /2 ) = O ( D − 1 ) ⟶ 0. (236)
Consequently,
lim D → ∞ 1 D E tr { diag j ( u φ + v φ x j u φ + ( v φ + y ) x j ) [ y D O ∥ T W diag j ( c φ x j u φ + ( v φ + y ) x j ) ] n } = 0 , n ≥ 1. (237) \lim_{D\to\infty}\frac{1}{D}\mathbb{E}\operatorname{tr}\left\{\operatorname{diag}_j\left(\frac{u_\varphi+v_\varphi x_j}{u_\varphi+(v_\varphi+y)x_j}\right)\left[\frac{y}{\sqrt{D}}\mathbf{O}_{\parallel}^{\mathsf{T}}\mathbf{W}\operatorname{diag}_j\left(\frac{\sqrt{c_\varphi x_j}}{u_\varphi+(v_\varphi+y)x_j}\right)\right]^n\right\}=0,\qquad n\geq1. \tag*{(237)} D → ∞ lim D 1 E tr { diag j ( u φ + ( v φ + y ) x j u φ + v φ x j ) [ D y O ∥ T W diag j ( u φ + ( v φ + y ) x j c φ x j ) ] n } = 0 , n ≥ 1. (237)
Thus only the n = 0 n=0 n = 0 term remains in the normalized trace. The inactive state directions contribute an identity block, so
r φ ( y ) = ( 1 − φ ) + + lim D → ∞ 1 D ∑ j = 1 r u φ + v φ x j u φ + ( v φ + y ) x j (238) r_\varphi(y)=(1-\varphi)_+ + \lim_{D\to\infty}\frac{1}{D}\sum_{j=1}^{r}\frac{u_\varphi+v_\varphi x_j}{u_\varphi+(v_\varphi+y)x_j} \tag*{(238)} r φ ( y ) = ( 1 − φ ) + + D → ∞ lim D 1 j = 1 ∑ r u φ + ( v φ + y ) x j u φ + v φ x j (238)
= 1 − φ + φ ⟨ u φ + v φ x u φ + ( v φ + y ) x ⟩ 1 / φ . (239) =1-\varphi+\varphi\left\langle\frac{u_\varphi+v_\varphi x}{u_\varphi+(v_\varphi+y)x}\right\rangle_{1/\varphi}. \tag*{(239)} = 1 − φ + φ ⟨ u φ + ( v φ + y ) x u φ + v φ x ⟩ 1/ φ . (239)
For φ > 1 \varphi>1 φ > 1 , the zero atom contributes φ − 1 \varphi-1 φ − 1 , cancelling the negative term 1 − φ 1-\varphi 1 − φ . Thus the same formula also holds for φ > 1 \varphi>1 φ > 1 .
Calculation of G φ ( y ) G_\varphi(y) G φ ( y ) . The squared Frobenius norm contains products of two Gaussian factors, so these terms do not vanish. We calculate them by the cavity method. Define
R y : = ( I D − y A ^ / η ) − 1 . (240) \mathbf{R}_y:=\left(\mathbf{I}_D-y\widehat{\mathbf{A}}/\eta\right)^{-1}. \tag*{(240)} R y := ( I D − y A / η ) − 1 . (240)
Let w j w_j w j and o j o_j o j be the j j j -th columns of W \mathbf{W} W and O ∥ \mathbf{O}_{\parallel} O ∥ , respectively. The cavity step removes w j w_j w j from W \mathbf{W} W and defines R y ( j ) \mathbf{R}_y^{(j)} R y ( j ) as the resulting inverse. Then R y ( j ) \mathbf{R}_y^{(j)} R y ( j ) is independent of w j w_j w j , and
R y − 1 = ( R y ( j ) ) − 1 − y D c φ x j u φ + v φ x j w j o j T . (241) \mathbf{R}_y^{-1}=\left(\mathbf{R}_y^{(j)}\right)^{-1}-\frac{y}{\sqrt{D}}\frac{\sqrt{c_\varphi x_j}}{u_\varphi+v_\varphi x_j}w_j o_j^{\mathsf{T}}. \tag*{(241)} R y − 1 = ( R y ( j ) ) − 1 − D y u φ + v φ x j c φ x j w j o j T . (241)
Restoring the removed column with the Woodbury formula gives
R y = R y ( j ) + y D c φ x j u φ + v φ x j R y ( j ) w j o j T R y ( j ) 1 − y D c φ x j u φ + v φ x j o j T R y ( j ) w j . (242) \mathbf{R}_y=\mathbf{R}_y^{(j)}+\frac{\frac{y}{\sqrt{D}}\frac{\sqrt{c_\varphi x_j}}{u_\varphi+v_\varphi x_j}\mathbf{R}_y^{(j)}w_j o_j^{\mathsf{T}}\mathbf{R}_y^{(j)}}{1-\frac{y}{\sqrt{D}}\frac{\sqrt{c_\varphi x_j}}{u_\varphi+v_\varphi x_j}o_j^{\mathsf{T}}\mathbf{R}_y^{(j)}w_j}. \tag*{(242)} R y = R y ( j ) + 1 − D y u φ + v φ x j c φ x j o j T R y ( j ) w j D y u φ + v φ x j c φ x j R y ( j ) w j o j T R y ( j ) . (242)
For sufficiently small y y y , the norm of R y ( j ) \mathbf{R}_y^{(j)} R y ( j ) is bounded, so o j T R y ( j ) w j = O P ( 1 ) o_j^{\mathsf{T}}\mathbf{R}_y^{(j)}w_j=O_{\mathbb{P}}(1) o j T R y ( j ) w j = O P ( 1 ) . Therefore the denominator is 1 + O P ( D − 1 / 2 ) 1+O_{\mathbb{P}}(D^{-1/2}) 1 + O P ( D − 1/2 ) and converges to one. Because the cavity matrix is independent of w j w_j w j , its conditional average satisfies
1 D E [ w j T R y ( j ) R y ( j ) T w j ∣ R y ( j ) ] = 1 D tr ( R y ( j ) R y ( j ) T ) ⟶ G φ ( y ) . (243) \frac{1}{D}\mathbb{E}\left[w_j^{\mathsf{T}}\mathbf{R}_y^{(j)}\mathbf{R}_y^{(j)\mathsf{T}}w_j\mid\mathbf{R}_y^{(j)}\right]=\frac{1}{D}\operatorname{tr}\left(\mathbf{R}_y^{(j)}\mathbf{R}_y^{(j)\mathsf{T}}\right)\longrightarrow G_\varphi(y). \tag*{(243)} D 1 E [ w j T R y ( j ) R y ( j ) T w j ∣ R y ( j ) ] = D 1 tr ( R y ( j ) R y ( j ) T ) ⟶ G φ ( y ) . (243)
The resolvent identity and Equation (E.142) give, at the retained leading order,
R y o j = u φ + v φ x j u φ + ( v φ + y ) x j o j + y D c φ x j u φ + ( v φ + y ) x j R y w j (244) \mathbf{R}_y o_j=\frac{u_\varphi+v_\varphi x_j}{u_\varphi+(v_\varphi+y)x_j}o_j+\frac{y}{\sqrt{D}}\frac{\sqrt{c_\varphi x_j}}{u_\varphi+(v_\varphi+y)x_j}\mathbf{R}_y w_j \tag*{(244)} R y o j = u φ + ( v φ + y ) x j u φ + v φ x j o j + D y u φ + ( v φ + y ) x j c φ x j R y w j (244)
≃ u φ + v φ x j u φ + ( v φ + y ) x j o j + y D c φ x j u φ + ( v φ + y ) x j R y ( j ) w j . (245) \simeq\frac{u_\varphi+v_\varphi x_j}{u_\varphi+(v_\varphi+y)x_j}o_j+\frac{y}{\sqrt{D}}\frac{\sqrt{c_\varphi x_j}}{u_\varphi+(v_\varphi+y)x_j}\mathbf{R}_y^{(j)}w_j. \tag*{(245)} ≃ u φ + ( v φ + y ) x j u φ + v φ x j o j + D y u φ + ( v φ + y ) x j c φ x j R y ( j ) w j . (245)
The mixed term has zero conditional mean because R y ( j ) \mathbf{R}_y^{(j)} R y ( j ) is independent of w j w_j w j . Consequently,
E w j ∥ R y o j ∥ 2 ≃ ( u φ + v φ x j ) 2 [ u φ + ( v φ + y ) x j ] 2 + y 2 c φ x j D [ u φ + ( v φ + y ) x j ] 2 tr ( R y ( j ) R y ( j ) T ) . (246) \mathbb{E}_{w_j}\left\|\mathbf{R}_y o_j\right\|^2\simeq\frac{(u_\varphi+v_\varphi x_j)^2}{[u_\varphi+(v_\varphi+y)x_j]^2}+\frac{y^2c_\varphi x_j}{D[u_\varphi+(v_\varphi+y)x_j]^2}\operatorname{tr}\left(\mathbf{R}_y^{(j)}\mathbf{R}_y^{(j)\mathsf{T}}\right). \tag*{(246)} E w j ∥ R y o j ∥ 2 ≃ [ u φ + ( v φ + y ) x j ] 2 ( u φ + v φ x j ) 2 + D [ u φ + ( v φ + y ) x j ] 2 y 2 c φ x j tr ( R y ( j ) R y ( j ) T ) . (246)
Since R y O ⊥ = O ⊥ \mathbf{R}_y\mathbf{O}_{\perp}=\mathbf{O}_{\perp} R y O ⊥ = O ⊥ , summing over j j j and dividing by D D D gives
G φ ( y ) = lim D → ∞ { D − r D + 1 D ∑ j = 1 r ( u φ + v φ x j ) 2 [ u φ + ( v φ + y ) x j ] 2 + y 2 c φ D 2 ∑ j = 1 r x j tr ( R y ( j ) R y ( j ) T ) [ u φ + ( v φ + y ) x j ] 2 } . (247) G_\varphi(y)=\lim_{D\to\infty}\left\{\frac{D-r}{D}+\frac{1}{D}\sum_{j=1}^{r}\frac{(u_\varphi+v_\varphi x_j)^2}{[u_\varphi+(v_\varphi+y)x_j]^2}+\frac{y^2c_\varphi}{D^2}\sum_{j=1}^{r}\frac{x_j\operatorname{tr}\left(\mathbf{R}_y^{(j)}\mathbf{R}_y^{(j)\mathsf{T}}\right)}{[u_\varphi+(v_\varphi+y)x_j]^2}\right\}. \tag*{(247)} G φ ( y ) = D → ∞ lim ⎩ ⎨ ⎧ D D − r + D 1 j = 1 ∑ r [ u φ + ( v φ + y ) x j ] 2 ( u φ + v φ x j ) 2 + D 2 y 2 c φ j = 1 ∑ r [ u φ + ( v φ + y ) x j ] 2 x j tr ( R y ( j ) R y ( j ) T ) ⎭ ⎬ ⎫ . (247)
Using D − 1 tr ( R y ( j ) R y ( j ) T ) → G φ ( y ) D^{-1}\operatorname{tr}(\mathbf{R}^{(j)}_y\mathbf{R}^{(j)\mathsf{T}}_y) \to G_\varphi(y) D − 1 tr ( R y ( j ) R y ( j ) T ) → G φ ( y ) and Equation (E.99) gives the self-consistent equation
G φ ( y ) = 1 − φ + φ ⟨ ( u φ + v φ x ) 2 [ u φ + ( v φ + y ) x ] 2 ⟩ 1 / φ + φ y 2 c φ ⟨ x [ u φ + ( v φ + y ) x ] 2 ⟩ 1 / φ G φ ( y ) (248) G_\varphi(y)=1-\varphi+\varphi\left\langle\frac{(u_\varphi+v_\varphi x)^2}{[u_\varphi+(v_\varphi+y)x]^2}\right\rangle_{1/\varphi}+\varphi y^2 c_\varphi\left\langle\frac{x}{[u_\varphi+(v_\varphi+y)x]^2}\right\rangle_{1/\varphi}G_\varphi(y) \tag*{(248)} G φ ( y ) = 1 − φ + φ ⟨ [ u φ + ( v φ + y ) x ] 2 ( u φ + v φ x ) 2 ⟩ 1/ φ + φ y 2 c φ ⟨ [ u φ + ( v φ + y ) x ] 2 x ⟩ 1/ φ G φ ( y ) (248)
= 1 − φ + φ ⟨ ( u φ + v φ x ) 2 / [ u φ + ( v φ + y ) x ] 2 ⟩ 1 / φ 1 − φ y 2 c φ ⟨ x / [ u φ + ( v φ + y ) x ] 2 ⟩ 1 / φ . (249) =\frac{1-\varphi+\varphi\left\langle(u_\varphi+v_\varphi x)^2/[u_\varphi+(v_\varphi+y)x]^2\right\rangle_{1/\varphi}}{1-\varphi y^2c_\varphi\left\langle x/[u_\varphi+(v_\varphi+y)x]^2\right\rangle_{1/\varphi}}. \tag*{(249)} = 1 − φ y 2 c φ ⟨ x / [ u φ + ( v φ + y ) x ] 2 ⟩ 1/ φ 1 − φ + φ ⟨ ( u φ + v φ x ) 2 / [ u φ + ( v φ + y ) x ] 2 ⟩ 1/ φ . (249)
The first equality is the self-consistent equation for G φ ( y ) G_\varphi(y) G φ ( y ) , and the second equality solves it. This proves the second formula in Proposition E.5 . □
The spectrum conditions
In this subsection, we first express the long-time behavior in terms of the spectral radius of the inference matrix. Define e t : = w ^ t − w i n e_t:=\hat{w}_t-w^{\mathrm{in}} e t := w ^ t − w in . For a fixed test context, Equation (13) gives the inference recursion
e t + 1 = J e t + H i n ( A ^ + η I D ) w i n + η L X i n ε t i n , (250) e_{t+1}=\mathbf{J}e_t+\mathbf{H}^{\mathrm{in}}(\hat{\mathbf{A}}+\eta\mathbf{I}_D)w^{\mathrm{in}}+\frac{\eta}{L}\mathbf{X}^{\mathrm{in}}\varepsilon^{\mathrm{in}}_t, \tag*{(250)} e t + 1 = J e t + H in ( A ^ + η I D ) w in + L η X in ε t in , (250)
where
J : = I D + H i n A ^ . (251) \mathbf{J}:=\mathbf{I}_D+\mathbf{H}^{\mathrm{in}}\hat{\mathbf{A}}. \tag*{(251)} J := I D + H in A ^ . (251)
Therefore,
e t = J t e 0 + ∑ s = 0 t − 1 J s [ H i n ( A ^ + η I D ) w i n + η L X i n ε s i n ] . (252) e_t=\mathbf{J}^t e_0+\sum_{s=0}^{t-1}\mathbf{J}^s\left[\mathbf{H}^{\mathrm{in}}(\hat{\mathbf{A}}+\eta\mathbf{I}_D)w^{\mathrm{in}}+\frac{\eta}{L}\mathbf{X}^{\mathrm{in}}\varepsilon^{\mathrm{in}}_s\right]. \tag*{(252)} e t = J t e 0 + s = 0 ∑ t − 1 J s [ H in ( A ^ + η I D ) w in + L η X in ε s in ] . (252)
The long-time behavior is consequently determined by
ρ ( J ) : = max λ ∈ spec ( J ) ∣ λ ∣ . (253) \rho(\mathbf{J}):=\max_{\lambda\in\operatorname{spec}(\mathbf{J})}|\lambda|. \tag*{(253)} ρ ( J ) := λ ∈ spec ( J ) max ∣ λ ∣. (253)
More precisely,
{ ρ ( J ) < 1 ⟹ J t → 0 and the error remains bounded , ρ ( J ) > 1 ⟹ J t and the error grow exponentially , ρ ( J ) = 1 ⟹ the limiting case . (254) \begin{cases}
\rho(\mathbf{J})<1 \quad\Longrightarrow\quad\mathbf{J}^t\to0\text{ and the error remains bounded},\\
\rho(\mathbf{J})>1 \quad\Longrightarrow\quad\mathbf{J}^t\text{ and the error grow exponentially},\\
\rho(\mathbf{J})=1 \quad\Longrightarrow\quad\text{the limiting case}. \tag*{(254)}
\end{cases} ⎩ ⎨ ⎧ ρ ( J ) < 1 ⟹ J t → 0 and the error remains bounded , ρ ( J ) > 1 ⟹ J t and the error grow exponentially , ρ ( J ) = 1 ⟹ the limiting case . (254)
When ρ ( J ) = 1 \rho(\mathbf{J})=1 ρ ( J ) = 1 , this gives
∑ s = 0 t − 1 J s [ H i n ( A ^ + η I D ) w i n + η L X i n ε s i n ] = O ( t ) , (255) \sum_{s=0}^{t-1}\mathbf{J}^s\left[\mathbf{H}^{\mathrm{in}}(\hat{\mathbf{A}}+\eta\mathbf{I}_D)w^{\mathrm{in}}+\frac{\eta}{L}\mathbf{X}^{\mathrm{in}}\varepsilon^{\mathrm{in}}_s\right]=O(t), \tag*{(255)} s = 0 ∑ t − 1 J s [ H in ( A ^ + η I D ) w in + L η X in ε s in ] = O ( t ) , (255)
so the state grows linearly and its squared error grows as Θ ( t 2 ) \Theta(t^2) Θ ( t 2 ) .
We next rewrite the conditions under which an eigenvalue of J \mathbf{J} J reaches 1 1 1 as conditions on A c \mathbf{A}_c A c . Define U \mathbf{U} U and A c \mathbf{A}_c A c by
U : = X i n [ ( X i n ) T X i n ] − 1 / 2 , A c : = U T A ^ U . (256) \mathbf{U}:=\mathbf{X}^{\mathrm{in}}[(\mathbf{X}^{\mathrm{in}})^{\mathsf{T}}\mathbf{X}^{\mathrm{in}}]^{-1/2},\qquad\mathbf{A}_c:=\mathbf{U}^{\mathsf{T}}\hat{\mathbf{A}}\mathbf{U}. \tag*{(256)} U := X in [( X in ) T X in ] − 1/2 , A c := U T A ^ U . (256)
The top row of Figure 3 shows the corresponding changes of the spectrum of J \mathbf{J} J . In Figure 3 A and B, ρ ( J ) = 1 \rho(\mathbf{J})=1 ρ ( J ) = 1 . In Figure 3 C and D, an eigenvalue lies beyond 1 1 1 , and hence ρ ( J ) > 1 \rho(\mathbf{J})>1 ρ ( J ) > 1 . In Figure 3 E, the edge returns to 1 1 1 , while Figure 3 F has ρ ( J ) < 1 \rho(\mathbf{J})<1 ρ ( J ) < 1 . The bottom row of Figure 3 shows the eigenvalues of A c / η \mathbf{A}_c/\eta A c / η . Since U T U = I L \mathbf{U}^{\mathsf{T}}\mathbf{U}=\mathbf{I}_L U T U = I L and H i n = X i n ( X i n ) T / L \mathbf{H}^{\mathrm{in}}=\mathbf{X}^{\mathrm{in}}(\mathbf{X}^{\mathrm{in}})^{\mathsf{T}}/L H in = X in ( X in ) T / L , we have
Figure 3. Schematic spectral evolution across the long-time phases. (A–F) Densities of the real parts of the eigenvalues of I D + H i n A ^ \mathbf{I}_{D}+\mathbf{H}^{\mathrm{in}}\hat{\mathbf{A}} I D + H in A ^ . (G–L) Densities of the real parts of the eigenvalues of A c / η \mathbf{A}_{c}/\eta A c / η . Red arrows in (A–C) and (G–I) mark the rank-deficient atoms at eigenvalues 1 and 0, respectively.
H i n = U ( X i n ) T X i n L U T , (257) \mathbf{H}^{\mathrm{in}}=\mathbf{U}\frac{(\mathbf{X}^{\mathrm{in}})^{\mathsf{T}}\mathbf{X}^{\mathrm{in}}}{L}\mathbf{U}^{\mathsf{T}}, \tag*{(257)} H in = U L ( X in ) T X in U T , (257)
spec ( H i n A ^ ) ∖ { 0 } = spec ( ( X i n ) T X i n L A c ) ∖ { 0 } . (258) \operatorname{spec}(\mathbf{H}^{\mathrm{in}}\hat{\mathbf{A}})\setminus\{0\}=\operatorname{spec}\left(\frac{(\mathbf{X}^{\mathrm{in}})^{\mathsf{T}}\mathbf{X}^{\mathrm{in}}}{L}\mathbf{A}_c\right)\setminus\{0\}. \tag*{(258)} spec ( H in A ^ ) ∖ { 0 } = spec ( L ( X in ) T X in A c ) ∖ { 0 } . (258)
The matrix ( X i n ) ⊤ X i n / L (\mathbf{X}^{\mathrm{in}})^{\top}\mathbf{X}^{\mathrm{in}}/L ( X in ) ⊤ X in / L is positive definite for 0 < α < 1 0<\alpha<1 0 < α < 1 . Consequently,
an additional eigenvalue of A c reaches 0 ⟺ an additional eigenvalue of H i n A ^ reaches 0 ⟺ an additional eigenvalue of I D + H i n A ^ reaches 1. (259) \begin{aligned}
&\text{an additional eigenvalue of }\mathbf{A}_{c}\text{ reaches }0\\
&\Longleftrightarrow\ \text{an additional eigenvalue of }\mathbf{H}^{\mathrm{in}}\hat{\mathbf{A}}\text{ reaches }0\\
&\Longleftrightarrow\ \text{an additional eigenvalue of }\mathbf{I}_{D}+\mathbf{H}^{\mathrm{in}}\hat{\mathbf{A}}\text{ reaches }1. \tag*{(259)}
\end{aligned} an additional eigenvalue of A c reaches 0 ⟺ an additional eigenvalue of H in A ^ reaches 0 ⟺ an additional eigenvalue of I D + H in A ^ reaches 1. (259)
Let
r D : = rank ( A ^ ) = min { D , M ( K − 1 ) } . (260) r_{D}:=\operatorname{rank}(\hat{\mathbf{A}})=\min\{D,M(K-1)\}. \tag*{(260)} r D := rank ( A ^ ) = min { D , M ( K − 1 )} . (260)
If the singular values are ordered as
σ 1 ( A c ) ≥ ⋯ ≥ σ L ( A c ) ≥ 0 , (261) \sigma_{1}(\mathbf{A}_{c})\ge\cdots\ge\sigma_{L}(\mathbf{A}_{c})\ge0, \tag*{(261)} σ 1 ( A c ) ≥ ⋯ ≥ σ L ( A c ) ≥ 0 , (261)
we write
σ min n o n z e r o ( A c ) : = σ min { L , r D } ( A c ) . (262) \sigma_{\min}^{\mathrm{nonzero}}(\mathbf{A}_{c}):=\sigma_{\min\{L,r_{D}\}}(\mathbf{A}_{c}). \tag*{(262)} σ m i n nonzero ( A c ) := σ m i n { L , r D } ( A c ) . (262)
For 0 < φ < α 0<\varphi<\alpha 0 < φ < α , the red arrows in Figure 3 A–C and G–I show the ( α − φ ) D + o ( D ) (\alpha-\varphi)D+o(D) ( α − φ ) D + o ( D ) eigenvalues fixed at 1 and 0, respectively. These fixed eigenvalues do not define the lower boundary. After excluding them, the lower-boundary condition is
lim D → ∞ σ min n o n z e r o ( A c ) = 0. (263) \lim_{D\to\infty}\sigma_{\min}^{\mathrm{nonzero}}(\mathbf{A}_{c})=0. \tag*{(263)} D → ∞ lim σ m i n nonzero ( A c ) = 0. (263)
This is shown in Figure 3 B and H, where the edge of the remaining eigenvalues reaches 1 in the top row and 0 in the bottom row. For α < φ < 1 / α \alpha<\varphi<1/\alpha α < φ < 1/ α , there are no fixed zero eigenvalues. The upper-boundary condition is therefore
lim D → ∞ σ L ( A c ) = 0. (264) \lim_{D\to\infty}\sigma_{L}(\mathbf{A}_{c})=0. \tag*{(264)} D → ∞ lim σ L ( A c ) = 0. (264)
This is shown in Figure 3 E and K, where the edge reaches 1 in the top row and 0 in the bottom row.
Lower boundary
In this subsection, we determine the lower boundary φ − ( α ) \varphi_{-}(\alpha) φ − ( α ) . In this regime, A c \mathbf{A}_{c} A c already has ( α − φ ) D + o ( D ) (\alpha-\varphi)D+o(D) ( α − φ ) D + o ( D ) zero eigenvalues because of its rank deficit. Therefore, φ − ( α ) \varphi_{-}(\alpha) φ − ( α ) is the value at which an additional eigenvalue reaches zero.
Equation (E.93) gives the effective matrix, and Equations (E.131 and E.132) give the two resolvents. Next, we determine the lower boundary while retaining the Gaussian test covariance.
Proposition E.6 (Lower boundary). Suppose 0 < α < 1 0<\alpha<1 0 < α < 1 . There is a unique φ − ( α ) ∈ ( 0 , α ) \varphi_{-}(\alpha)\in(0,\alpha) φ − ( α ) ∈ ( 0 , α ) such that
lim D → ∞ σ min n o n z e r o ( A c ) = 0 ⟺ φ = φ − ( α ) , 0 < φ < α . (265) \lim_{D\to\infty}\sigma_{\min}^{\mathrm{nonzero}}(\mathbf{A}_{c})=0\quad\Longleftrightarrow\quad\varphi=\varphi_{-}(\alpha),\qquad0<\varphi<\alpha. \tag*{(265)} D → ∞ lim σ m i n nonzero ( A c ) = 0 ⟺ φ = φ − ( α ) , 0 < φ < α . (265) It satisfies
( α − φ − ) ( 1 − φ − ) = α ( 1 − α ) φ − 2 ( 1 − α φ − ) ( α + 1 − 2 φ − ) , (266) (\alpha-\varphi_{-})(1-\varphi_{-})=\alpha(1-\alpha)\varphi_{-}^{2}(1-\alpha\varphi_{-})(\alpha+1-2\varphi_{-}), \tag*{(266)} ( α − φ − ) ( 1 − φ − ) = α ( 1 − α ) φ − 2 ( 1 − α φ − ) ( α + 1 − 2 φ − ) , (266)
Proof. We derive Equation (E.166) for 0 < φ < α 0 < \varphi< \alpha 0 < φ < α and then show that it has a unique solution. The matrix H i n A ^ \mathbf{H}^{\mathrm{in}}\hat{\mathbf{A}} H in A ^ has ( α − φ ) D + o ( D ) (\alpha-\varphi)D+o(D) ( α − φ ) D + o ( D ) zero eigenvalues in this regime, so replacing H i n \mathbf{H}^{\mathrm{in}} H in by an orthogonal projector would change its remaining eigenvalues. In the orthogonal basis ( O ∥ , O ⊥ ) (\mathbf{O}_{\parallel},\mathbf{O}_{\perp}) ( O ∥ , O ⊥ ) defined above, define X 1 \mathbf{X}_{1} X 1 and X 2 \mathbf{X}_{2} X 2 by
\begin{pmatrix}
\mathbf{O}_{\parallel}^{\mathsf{T}}\\
\mathbf{O}_{\perp}^{\mathsf{T}}
\end{pmatrix}
\mathbf{X}^{\mathrm{in}}
=
\begin{pmatrix}
\mathbf{X}_{1}\\
\mathbf{X}_{2}
\end{pmatrix}. \tag*{(267)}\end{pmatrix}
Equation (E.93) gives
1 η ( O ∥ T O ⊥ T ) A ^ ( O ∥ O ⊥ ) = ( C 0 Z 0 ) . (268) \frac{1}{\eta}
\begin{pmatrix}
\mathbf{O}_{\parallel}^{\mathsf{T}}\\
\mathbf{O}_{\perp}^{\mathsf{T}}
\end{pmatrix}
\hat{\mathbf{A}}
\begin{pmatrix}
\mathbf{O}_{\parallel} & \mathbf{O}_{\perp}
\end{pmatrix}
=
\begin{pmatrix}
\mathbf{C} & 0\\
\mathbf{Z} & 0
\end{pmatrix}. \tag*{(268)} η 1 ( O ∥ T O ⊥ T ) A ^ ( O ∥ O ⊥ ) = ( C Z 0 0 ) . (268)
Here X 1 ∈ R r × L \mathbf{X}_{1} \in\mathbb{R}^{r \times L} X 1 ∈ R r × L , X 2 ∈ R ( D − r ) × L \mathbf{X}_{2} \in\mathbb{R}^{(D-r) \times L} X 2 ∈ R ( D − r ) × L , C ∈ R r × r \mathbf{C} \in\mathbb{R}^{r \times r} C ∈ R r × r , and Z ∈ R ( D − r ) × r \mathbf{Z} \in\mathbb{R}^{(D-r) \times r} Z ∈ R ( D − r ) × r , where r / D → φ < α r/D \to\varphi< \alpha r / D → φ < α . The matrix C \mathbf{C} C is invertible almost surely, so define
R : = Z C − 1 . (269) \mathbf{R} := \mathbf{Z}\mathbf{C}^{-1}. \tag*{(269)} R := Z C − 1 . (269)
Since r < L r < L r < L , the matrix
B : = X 1 X 1 T L (270) \mathbf{B} := \frac{\mathbf{X}_{1}\mathbf{X}_{1}^{\mathsf{T}}}{L} \tag*{(270)} B := L X 1 X 1 T (270)
is also invertible almost surely. Direct multiplication gives
1 η ( O ∥ T O ⊥ T ) H i n A ^ ( O ∥ O ⊥ ) = 1 L ( X 1 X 1 T X 1 X 2 T X 2 X 1 T X 2 X 2 T ) ( C 0 Z 0 ) (271) \frac{1}{\eta}
\begin{pmatrix}
\mathbf{O}_{\parallel}^{\mathsf{T}}\\
\mathbf{O}_{\perp}^{\mathsf{T}}
\end{pmatrix}
\mathbf{H}^{\mathrm{in}}\hat{\mathbf{A}}
\begin{pmatrix}
\mathbf{O}_{\parallel} & \mathbf{O}_{\perp}
\end{pmatrix}
=
\frac{1}{L}
\begin{pmatrix}
\mathbf{X}_{1}\mathbf{X}_{1}^{\mathsf{T}} & \mathbf{X}_{1}\mathbf{X}_{2}^{\mathsf{T}}\\
\mathbf{X}_{2}\mathbf{X}_{1}^{\mathsf{T}} & \mathbf{X}_{2}\mathbf{X}_{2}^{\mathsf{T}}
\end{pmatrix}
\begin{pmatrix}
\mathbf{C} & 0\\
\mathbf{Z} & 0
\end{pmatrix} \tag*{(271)} η 1 ( O ∥ T O ⊥ T ) H in A ^ ( O ∥ O ⊥ ) = L 1 ( X 1 X 1 T X 2 X 1 T X 1 X 2 T X 2 X 2 T ) ( C Z 0 0 ) (271)
= 1 L ( X 1 X 1 T C + X 1 X 2 T Z 0 X 2 X 1 T C + X 2 X 2 T Z 0 ) . (272) =
\frac{1}{L}
\begin{pmatrix}
\mathbf{X}_{1}\mathbf{X}_{1}^{\mathsf{T}}\mathbf{C}+\mathbf{X}_{1}\mathbf{X}_{2}^{\mathsf{T}}\mathbf{Z} & 0\\
\mathbf{X}_{2}\mathbf{X}_{1}^{\mathsf{T}}\mathbf{C}+\mathbf{X}_{2}\mathbf{X}_{2}^{\mathsf{T}}\mathbf{Z} & 0
\end{pmatrix}. \tag*{(272)} = L 1 ( X 1 X 1 T C + X 1 X 2 T Z X 2 X 1 T C + X 2 X 2 T Z 0 0 ) . (272)
Therefore,
det ( λ I D − H i n A ^ η ) = λ D − r det [ λ I r − 1 L ( X 1 X 1 T C + X 1 X 2 T Z ) ] . (273) \det\left(\lambda I_{D}-\frac{\mathbf{H}^{\mathrm{in}}\hat{\mathbf{A}}}{\eta}\right)
=
\lambda^{D-r}
\det\left[\lambda I_{r}-\frac{1}{L}\left(\mathbf{X}_{1}\mathbf{X}_{1}^{\mathsf{T}}\mathbf{C}+\mathbf{X}_{1}\mathbf{X}_{2}^{\mathsf{T}}\mathbf{Z}\right)\right]. \tag*{(273)} det ( λ I D − η H in A ^ ) = λ D − r det [ λ I r − L 1 ( X 1 X 1 T C + X 1 X 2 T Z ) ] . (273)
Hence the nonzero eigenvalues of H i n A ^ / η \mathbf{H}^{\mathrm{in}}\hat{\mathbf{A}}/\eta H in A ^ / η are those of the following r × r r \times r r × r matrix:
1 L ( X 1 X 1 T C + X 1 X 2 T Z ) = B C + X 1 X 2 T L Z (274) \frac{1}{L}\left(\mathbf{X}_{1}\mathbf{X}_{1}^{\mathsf{T}}\mathbf{C}+\mathbf{X}_{1}\mathbf{X}_{2}^{\mathsf{T}}\mathbf{Z}\right)
=
\mathbf{B}\mathbf{C}+\frac{\mathbf{X}_{1}\mathbf{X}_{2}^{\mathsf{T}}}{L}\mathbf{Z} \tag*{(274)} L 1 ( X 1 X 1 T C + X 1 X 2 T Z ) = BC + L X 1 X 2 T Z (274)
= B C + X 1 X 2 T L R C (275) =
\mathbf{B}\mathbf{C}+\frac{\mathbf{X}_{1}\mathbf{X}_{2}^{\mathsf{T}}}{L}\mathbf{R}\mathbf{C} \tag*{(275)} = BC + L X 1 X 2 T RC (275)
= ( B + X 1 X 2 T L R ) C (276) =
\left(\mathbf{B}+\frac{\mathbf{X}_{1}\mathbf{X}_{2}^{\mathsf{T}}}{L}\mathbf{R}\right)\mathbf{C} \tag*{(276)} = ( B + L X 1 X 2 T R ) C (276)
= B ( I r + B − 1 X 1 X 2 T L R ) C . (277) =
\mathbf{B}\left(I_{r}+\mathbf{B}^{-1}\frac{\mathbf{X}_{1}\mathbf{X}_{2}^{\mathsf{T}}}{L}\mathbf{R}\right)\mathbf{C}. \tag*{(277)} = B ( I r + B − 1 L X 1 X 2 T R ) C . (277)
Equation (E.93) gives
R = Z C − 1 (278) \mathbf{R}=\mathbf{Z}\mathbf{C}^{-1} \tag*{(278)} R = Z C − 1 (278)
= O ⊥ T W D diag j c φ x j u φ + v φ x j [ − diag j x j u φ + v φ x j + O ∥ T W D diag j c φ x j u φ + v φ x j ] − 1 (279) =
\frac{\mathbf{O}_{\perp}^{\mathsf{T}}\mathbf{W}}{\sqrt{D}}\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}
\left[
-\operatorname{diag}_{j}\frac{x_{j}}{u_{\varphi}+v_{\varphi}x_{j}}
+
\frac{\mathbf{O}_{\parallel}^{\mathsf{T}}\mathbf{W}}{\sqrt{D}}\operatorname{diag}_{j}\frac{\sqrt{c_{\varphi}x_{j}}}{u_{\varphi}+v_{\varphi}x_{j}}
\right]^{-1} \tag*{(279)} = D O ⊥ T W diag j u φ + v φ x j c φ x j [ − diag j u φ + v φ x j x j + D O ∥ T W diag j u φ + v φ x j c φ x j ] − 1 (279)
= − c φ D O ⊥ T W [ diag j x j − c φ D O ∥ T W ] − 1 (280) =
-\sqrt{\frac{c_{\varphi}}{D}}\mathbf{O}_{\perp}^{\mathsf{T}}\mathbf{W}
\left[
\operatorname{diag}_{j}\sqrt{x_{j}}-\sqrt{\frac{c_{\varphi}}{D}}\mathbf{O}_{\parallel}^{\mathsf{T}}\mathbf{W}
\right]^{-1} \tag*{(280)} = − D c φ O ⊥ T W [ diag j x j − D c φ O ∥ T W ] − 1 (280)
= − c φ D O ⊥ T W ∑ k = 0 ∞ [ c φ D diag j ( x j − 1 / 2 ) O ∥ T W ] k diag j ( x j − 1 / 2 ) . (281) =
-\sqrt{\frac{c_{\varphi}}{D}}\mathbf{O}_{\perp}^{\mathsf{T}}\mathbf{W}
\sum_{k=0}^{\infty}
\left[
\sqrt{\frac{c_{\varphi}}{D}}\operatorname{diag}_{j}\left(x_{j}^{-1/2}\right)\mathbf{O}_{\parallel}^{\mathsf{T}}\mathbf{W}
\right]^{k}
\operatorname{diag}_{j}\left(x_{j}^{-1/2}\right). \tag*{(281)} = − D c φ O ⊥ T W k = 0 ∑ ∞ [ D c φ diag j ( x j − 1/2 ) O ∥ T W ] k diag j ( x j − 1/2 ) . (281)
The average of terms containing an odd total number of centered Gaussian factors is zero. At the retained leading order, each additional Gaussian pair multiplies the preceding contribution by φ c φ ⟨ x − 1 ⟩ 1 / φ \varphi_c\varphi\langle x^{-1}\rangle_{1/\varphi} φ c φ ⟨ x − 1 ⟩ 1/ φ . Therefore,
lim D → ∞ ∥ R ∥ F 2 D = ( 1 − φ ) φ c φ ⟨ x − 1 ⟩ 1 / φ [ 1 + φ c φ ⟨ x − 1 ⟩ 1 / φ + ( φ c φ ⟨ x − 1 ⟩ 1 / φ ) 2 + ⋯ ] (282) \lim_{D\to\infty}\frac{\lVert\mathbf{R}\rVert_F^2}{D}=(1-\varphi)\varphi_c\varphi\langle x^{-1}\rangle_{1/\varphi}\left[1+\varphi_c\varphi\langle x^{-1}\rangle_{1/\varphi}+\left(\varphi_c\varphi\langle x^{-1}\rangle_{1/\varphi}\right)^2+\cdots\right] \tag*{(282)} D → ∞ lim D ∥ R ∥ F 2 = ( 1 − φ ) φ c φ ⟨ x − 1 ⟩ 1/ φ [ 1 + φ c φ ⟨ x − 1 ⟩ 1/ φ + ( φ c φ ⟨ x − 1 ⟩ 1/ φ ) 2 + ⋯ ] (282)
= ( 1 − φ ) φ c φ ⟨ x − 1 ⟩ 1 / φ ∑ j = 0 ∞ [ φ c φ ⟨ x − 1 ⟩ 1 / φ ] j (283) =(1-\varphi)\varphi_c\varphi\langle x^{-1}\rangle_{1/\varphi}\sum_{j=0}^{\infty}\left[\varphi_c\varphi\langle x^{-1}\rangle_{1/\varphi}\right]^j \tag*{(283)} = ( 1 − φ ) φ c φ ⟨ x − 1 ⟩ 1/ φ j = 0 ∑ ∞ [ φ c φ ⟨ x − 1 ⟩ 1/ φ ] j (283)
= ( 1 − φ ) φ c 1 1 − φ ∑ j = 0 ∞ ( φ c φ 1 − φ ) j (284) =(1-\varphi)\varphi_c\frac{1}{1-\varphi}\sum_{j=0}^{\infty}\left(\frac{\varphi_c\varphi}{1-\varphi}\right)^j \tag*{(284)} = ( 1 − φ ) φ c 1 − φ 1 j = 0 ∑ ∞ ( 1 − φ φ c φ ) j (284)
= φ c φ ∑ j = 0 ∞ ( φ c φ 1 − φ ) j (285) =\varphi_c\varphi\sum_{j=0}^{\infty}\left(\frac{\varphi_c\varphi}{1-\varphi}\right)^j \tag*{(285)} = φ c φ j = 0 ∑ ∞ ( 1 − φ φ c φ ) j (285)
= φ c φ ( 1 − φ ) 1 − φ − φ c φ . (286) =\frac{\varphi_c\varphi(1-\varphi)}{1-\varphi-\varphi_c\varphi}. \tag*{(286)} = 1 − φ − φ c φ φ c φ ( 1 − φ ) . (286)
The denominator is positive for 0 < φ ≤ α 0<\varphi\le\alpha 0 < φ ≤ α . Indeed, φ + φ c φ \varphi+\varphi_c\varphi φ + φ c φ is increasing there and
1 − α − α c α = ( 1 − α ) [ 1 − α 3 ( 1 − α 2 ) ] > 0. (287) 1-\alpha-\alpha_c\alpha=(1-\alpha)\left[1-\alpha^3(1-\alpha^2)\right]>0. \tag*{(287)} 1 − α − α c α = ( 1 − α ) [ 1 − α 3 ( 1 − α 2 ) ] > 0. (287)
Conditional on X 1 \mathbf{X}_1 X 1 and the learned matrix, B − 1 X 1 X 2 T R / L \mathbf{B}^{-1}\mathbf{X}_1\mathbf{X}_2^{\mathsf{T}}\mathbf{R}/L B − 1 X 1 X 2 T R / L is centered Gaussian. For any matrix F \mathbf{F} F independent of X 2 \mathbf{X}_2 X 2 , direct averaging over X 2 \mathbf{X}_2 X 2 gives
E X 2 [ B − 1 X 1 X 2 T L R F R T X 2 X 1 T L B − 1 ] = B − 1 L tr ( R T R F ) . (288) \mathbb{E}_{\mathbf{X}_2}\left[\mathbf{B}^{-1}\frac{\mathbf{X}_1\mathbf{X}_2^{\mathsf{T}}}{L}\mathbf{RFR}^{\mathsf{T}}\frac{\mathbf{X}_2\mathbf{X}_1^{\mathsf{T}}}{L}\mathbf{B}^{-1}\right]=\frac{\mathbf{B}^{-1}}{L}\operatorname{tr}(\mathbf{R}^{\mathsf{T}}\mathbf{RF}). \tag*{(288)} E X 2 [ B − 1 L X 1 X 2 T RFR T L X 2 X 1 T B − 1 ] = L B − 1 tr ( R T RF ) . (288)
The right-hand side is proportional to B − 1 \mathbf{B}^{-1} B − 1 . Substituting F = B − 1 \mathbf{F}=\mathbf{B}^{-1} F = B − 1 into the same equality gives
B − 1 L tr ( R T R B − 1 ) = { 1 L tr ( B − 1 R T R ) } B − 1 . (289) \frac{\mathbf{B}^{-1}}{L}\operatorname{tr}(\mathbf{R}^{\mathsf{T}}\mathbf{R}\mathbf{B}^{-1})=\left\{\frac{1}{L}\operatorname{tr}(\mathbf{B}^{-1}\mathbf{R}^{\mathsf{T}}\mathbf{R})\right\}\mathbf{B}^{-1}. \tag*{(289)} L B − 1 tr ( R T R B − 1 ) = { L 1 tr ( B − 1 R T R ) } B − 1 . (289)
Thus each additional pair of centered Gaussian factors multiplies the preceding term by L − 1 tr ( B − 1 R T R ) L^{-1}\operatorname{tr}(\mathbf{B}^{-1}\mathbf{R}^{\mathsf{T}}\mathbf{R}) L − 1 tr ( B − 1 R T R ) . Rotational independence and the Wishart inverse moment give
1 L tr ( B − 1 R T R ) ⟶ D L ( 1 r tr B − 1 ) ( 1 D tr R T R ) (290) \frac{1}{L}\operatorname{tr}(\mathbf{B}^{-1}\mathbf{R}^{\mathsf{T}}\mathbf{R})\longrightarrow\frac{D}{L}\left(\frac{1}{r}\operatorname{tr}\mathbf{B}^{-1}\right)\left(\frac{1}{D}\operatorname{tr}\mathbf{R}^{\mathsf{T}}\mathbf{R}\right) \tag*{(290)} L 1 tr ( B − 1 R T R ) ⟶ L D ( r 1 tr B − 1 ) ( D 1 tr R T R ) (290)
= 1 α α α − φ φ c φ ( 1 − φ ) 1 − φ − φ c φ (291) =\frac{1}{\alpha}\frac{\alpha}{\alpha-\varphi}\frac{\varphi_c\varphi(1-\varphi)}{1-\varphi-\varphi_c\varphi} \tag*{(291)} = α 1 α − φ α 1 − φ − φ c φ φ c φ ( 1 − φ ) (291)
= φ c φ ( 1 − φ ) ( α − φ ) ( 1 − φ − φ c φ ) . (292) =\frac{\varphi_c\varphi(1-\varphi)}{(\alpha-\varphi)(1-\varphi-\varphi_c\varphi)}. \tag*{(292)} = ( α − φ ) ( 1 − φ − φ c φ ) φ c φ ( 1 − φ ) . (292)
Since B \mathbf{B} B and C \mathbf{C} C are invertible almost surely. Its inverse has the expansion
( I r + B − 1 X 1 X 2 T L R ) − 1 = I r − B − 1 X 1 X 2 T L R + ( B − 1 X 1 X 2 T L R ) 2 − ⋯ . (293) \left(\mathbf{I}_r+\mathbf{B}^{-1}\frac{\mathbf{X}_1\mathbf{X}_2^{\mathsf{T}}}{L}\mathbf{R}\right)^{-1}
=\mathbf{I}_r-\mathbf{B}^{-1}\frac{\mathbf{X}_1\mathbf{X}_2^{\mathsf{T}}}{L}\mathbf{R}
+\left(\mathbf{B}^{-1}\frac{\mathbf{X}_1\mathbf{X}_2^{\mathsf{T}}}{L}\mathbf{R}\right)^2-\cdots. \tag*{(293)} ( I r + B − 1 L X 1 X 2 T R ) − 1 = I r − B − 1 L X 1 X 2 T R + ( B − 1 L X 1 X 2 T R ) 2 − ⋯ . (293)
At the retained leading order, the Frobenius norm of this expansion is a geometric series whose ratio is given by Equation (E.192). In the effective random-matrix calculation, the lower boundary is therefore identified by the divergence of this inverse norm, namely
1 = 1 L tr ( B − 1 R T R ) (294) 1=\frac{1}{L}\operatorname{tr}(\mathbf{B}^{-1}\mathbf{R}^{\mathsf{T}}\mathbf{R}) \tag*{(294)} 1 = L 1 tr ( B − 1 R T R ) (294)
= φ c φ ( 1 − φ ) ( α − φ ) ( 1 − φ − φ c φ ) , (295) =\frac{\varphi_c\varphi(1-\varphi)}{(\alpha-\varphi)(1-\varphi-\varphi_c\varphi)}, \tag*{(295)} = ( α − φ ) ( 1 − φ − φ c φ ) φ c φ ( 1 − φ ) , (295)
which gives
( α − φ ) ( 1 − φ ) = α ( 1 − α ) φ 2 ( 1 − α φ ) ( α + 1 − 2 φ ) . (296) (\alpha-\varphi)(1-\varphi)=\alpha(1-\alpha)\varphi^2(1-\alpha\varphi)(\alpha+1-2\varphi). \tag*{(296)} ( α − φ ) ( 1 − φ ) = α ( 1 − α ) φ 2 ( 1 − α φ ) ( α + 1 − 2 φ ) . (296)
Thus the boundary equation is Equation (E.166).
It remains to show that Equation (E.196) has a unique solution in ( 0 < φ < α ) (0 < \varphi< \alpha) ( 0 < φ < α ) . To check uniqueness directly, set φ = α z / ( 1 + z ) \varphi= \alpha z/(1+z) φ = α z / ( 1 + z ) . Multiplying the left side minus the right side of Equation (E.166) by ( 1 + z ) 4 (1+z)^4 ( 1 + z ) 4 gives
0 = α + α ( 3 − α ) z + α [ ( 1 − α ) ( 3 + α ) + α 4 ] z 2 + α ( 1 − α ) [ ( 1 − α 2 ) 2 + α 5 ] z 3 − α 3 ( 1 − α ) 3 ( 1 + α ) z 4 . (297) 0 = \alpha+ \alpha(3-\alpha)z + \alpha[(1-\alpha)(3+\alpha)+\alpha^4]z^2
+ \alpha(1-\alpha)[(1-\alpha^2)^2+\alpha^5]z^3-\alpha^3(1-\alpha)^3(1+\alpha)z^4. \tag*{(297)} 0 = α + α ( 3 − α ) z + α [( 1 − α ) ( 3 + α ) + α 4 ] z 2 + α ( 1 − α ) [( 1 − α 2 ) 2 + α 5 ] z 3 − α 3 ( 1 − α ) 3 ( 1 + α ) z 4 . (297)
There is exactly one sign change, so Descartes’ rule gives one positive root. Since z > 0 z>0 z > 0 parametrizes 0 < φ < α 0<\varphi<\alpha 0 < φ < α , the lower boundary is unique in that interval.
Upper boundary
In this subsection, we determine the upper boundary φ + ( α ) \varphi_+(\alpha) φ + ( α ) . In this regime, A c A_c A c is generically full rank. Therefore, φ + ( α ) \varphi_+(\alpha) φ + ( α ) is the value at which its smallest singular value reaches zero, which in our effective random-matrix description is expected to coincide with the limiting eigenvalue support reaching zero.
The preceding calculation gives the value at which another zero eigenvalue appears for 0 < φ < α 0<\varphi<\alpha 0 < φ < α . We next calculate the corresponding value for α < φ < 1 / α \alpha<\varphi<1/\alpha α < φ < 1/ α by reducing the two resolvent conditions to one scalar MP equation.
Proposition E.7 (Upper boundary). Suppose 0 < α < 1 0<\alpha<1 0 < α < 1 . Let z + z_+ z + be the unique positive solution of
0 = ( 1 − α ) 2 z + 4 + ( 1 − α ) [ 3 ( 1 − α 2 ) + α 3 ] z + 3 + ( 1 − α ) [ 3 + 3 α ( 1 − α ) + α 4 ] z + 2 + [ ( 1 − α ) ( 1 + 2 α ) + α 5 ] z + − α 4 ( 1 − α 2 ) . (298) 0=(1-\alpha)^2z_+^4+(1-\alpha)[3(1-\alpha^2)+\alpha^3]z_+^3
+(1-\alpha)[3+3\alpha(1-\alpha)+\alpha^4]z_+^2
+[(1-\alpha)(1+2\alpha)+\alpha^5]z_+-\alpha^4(1-\alpha^2). \tag*{(298)} 0 = ( 1 − α ) 2 z + 4 + ( 1 − α ) [ 3 ( 1 − α 2 ) + α 3 ] z + 3 + ( 1 − α ) [ 3 + 3 α ( 1 − α ) + α 4 ] z + 2 + [( 1 − α ) ( 1 + 2 α ) + α 5 ] z + − α 4 ( 1 − α 2 ) . (298) Then
φ + ( α ) : = α 2 + z + + ( 1 − α ) z + 2 α ( 1 + z + ) [ 1 + ( 1 − α ) z + ] . (299) \varphi_+(\alpha):=\frac{\alpha^2+z_++(1-\alpha)z_+^2}{\alpha(1+z_+)[1+(1-\alpha)z_+]}. \tag*{(299)} φ + ( α ) := α ( 1 + z + ) [ 1 + ( 1 − α ) z + ] α 2 + z + + ( 1 − α ) z + 2 . (299) is the unique value in ( α , 1 / α ) (\alpha,1/\alpha) ( α , 1/ α ) such that
lim D → ∞ σ L ( A c ) = 0 ⟺ φ = φ + ( α ) , α < φ < 1 / α . (300) \lim_{D\to\infty}\sigma_L(A_c)=0 \quad\Longleftrightarrow\quad\varphi=\varphi_+(\alpha),\qquad\alpha<\varphi<1/\alpha. \tag*{(300)} D → ∞ lim σ L ( A c ) = 0 ⟺ φ = φ + ( α ) , α < φ < 1/ α . (300) Moreover, α < φ + ( α ) < 1 \alpha<\varphi_+(\alpha)<1 α < φ + ( α ) < 1 .
Proof. For α < φ < 1 / α \alpha<\varphi<1/\alpha α < φ < 1/ α , we use that A c A_c A c has full rank except at the boundary calculated below. The positive-definite matrix ( X i n ) ⊤ X i n / L (X^{\mathrm{in}})^\top X^{\mathrm{in}}/L ( X in ) ⊤ X in / L is boundedly invertible. Therefore ( ( X i n ) ⊤ X i n / L ) A c ((X^{\mathrm{in}})^\top X^{\mathrm{in}}/L)A_c (( X in ) ⊤ X in / L ) A c has a zero eigenvalue exactly when A c A_c A c has a zero eigenvalue. We now obtain the two scalar boundary equations by a leave-one-column cavity calculation. Let U − ℓ U^{-\ell} U − ℓ be U U U with column u ℓ u_\ell u ℓ removed, and define
G ζ : = [ ζ I L − U ⊤ A ^ η U ] − 1 , (301) G_\zeta:=\left[\zeta I_L-U^\top\frac{\widehat{A}}{\eta}U\right]^{-1}, \tag*{(301)} G ζ := [ ζ I L − U ⊤ η A U ] − 1 , (301)
G ζ − ℓ : = [ ζ I L − 1 − ( U − ℓ ) ⊤ A ^ η U − ℓ ] − 1 . (302) G_\zeta^{-\ell}:=\left[\zeta I_{L-1}-(U^{-\ell})^\top\frac{\widehat{A}}{\eta}U^{-\ell}\right]^{-1}. \tag*{(302)} G ζ − ℓ := [ ζ I L − 1 − ( U − ℓ ) ⊤ η A U − ℓ ] − 1 . (302)
Ordering u ℓ u_\ell u ℓ last gives
G ζ − 1 = ( ( G ζ − ℓ ) − 1 − ( U − ℓ ) ⊤ ( A ^ / η ) u ℓ − u ℓ ⊤ ( A ^ / η ) U − ℓ ζ − u ℓ ⊤ ( A ^ / η ) u ℓ ) . (303) G_\zeta^{-1}=
\begin{pmatrix}
(G_\zeta^{-\ell})^{-1} & -(U^{-\ell})^\top(\widehat{A}/\eta)u_\ell\\
-u_\ell^\top(\widehat{A}/\eta)U^{-\ell} & \zeta-u_\ell^\top(\widehat{A}/\eta)u_\ell
\end{pmatrix}. \tag*{(303)} G ζ − 1 = ( ( G ζ − ℓ ) − 1 − u ℓ ⊤ ( A / η ) U − ℓ − ( U − ℓ ) ⊤ ( A / η ) u ℓ ζ − u ℓ ⊤ ( A / η ) u ℓ ) . (303)
Restoring the deleted column with the Woodbury formula gives
[ G ζ ] ℓ ℓ = [ ζ − u ℓ ⊤ A ^ η u ℓ − u ℓ ⊤ A ^ η U − ℓ G ζ − ℓ ( U − ℓ ) ⊤ A ^ η u ℓ ] − 1 . (304) [G_\zeta]_{\ell\ell}=
\left[\zeta-u_\ell^\top\frac{\widehat{A}}{\eta}u_\ell-u_\ell^\top\frac{\widehat{A}}{\eta}U^{-\ell}G_\zeta^{-\ell}(U^{-\ell})^\top\frac{\widehat{A}}{\eta}u_\ell\right]^{-1}. \tag*{(304)} [ G ζ ] ℓℓ = [ ζ − u ℓ ⊤ η A u ℓ − u ℓ ⊤ η A U − ℓ G ζ − ℓ ( U − ℓ ) ⊤ η A u ℓ ] − 1 . (304)
We use the large-D D D replacement that u ℓ u_\ell u ℓ can be averaged independently of G ζ − ℓ \mathcal{G}_{\zeta}^{-\ell} G ζ − ℓ . Define the scalar order parameter by
y : = lim D → ∞ lim ζ → 0 1 D tr G ζ . (305) y := \lim_{D\to\infty}\lim_{\zeta\to0}\frac{1}{D}\operatorname{tr}\mathcal{G}_{\zeta}. \tag*{(305)} y := D → ∞ lim ζ → 0 lim D 1 tr G ζ . (305)
Averaging the left-hand side of Equation (E.204) over ℓ \ell ℓ gives
lim D → ∞ lim ζ → 0 1 L ∑ ℓ = 1 L [ G ζ ] ℓ ℓ = lim D → ∞ lim ζ → 0 1 L tr G ζ (306) \lim_{D\to\infty}\lim_{\zeta\to0}\frac{1}{L}\sum_{\ell=1}^{L}[\mathcal{G}_{\zeta}]_{\ell\ell}
=
\lim_{D\to\infty}\lim_{\zeta\to0}\frac{1}{L}\operatorname{tr}\mathcal{G}_{\zeta} \tag*{(306)} D → ∞ lim ζ → 0 lim L 1 ℓ = 1 ∑ L [ G ζ ] ℓℓ = D → ∞ lim ζ → 0 lim L 1 tr G ζ (306)
= lim D → ∞ D L ( lim ζ → 0 1 D tr G ζ ) (307) =
\lim_{D\to\infty}\frac{D}{L}\left(\lim_{\zeta\to0}\frac{1}{D}\operatorname{tr}\mathcal{G}_{\zeta}\right) \tag*{(307)} = D → ∞ lim L D ( ζ → 0 lim D 1 tr G ζ ) (307)
= y α . (308) =\frac{y}{\alpha}. \tag*{(308)} = α y . (308)
Applying cavity independence and concentration on the right-hand side of Equation (E.204), and then averaging over ℓ \ell ℓ , gives
lim D → ∞ lim ζ → 0 1 L ∑ ℓ = 1 L [ ζ − u ℓ T A ^ η u ℓ − u ℓ T A ^ η U − ℓ G ζ − ℓ ( U − ℓ ) T A ^ η u ℓ ] − 1 (309) \lim_{D\to\infty}\lim_{\zeta\to0}\frac{1}{L}\sum_{\ell=1}^{L}\left[\zeta-u_\ell^{\mathsf T}\frac{\widehat{A}}{\eta}u_\ell-u_\ell^{\mathsf T}\frac{\widehat{A}}{\eta}\mathcal{U}^{-\ell}\mathcal{G}_{\zeta}^{-\ell}(\mathcal{U}^{-\ell})^{\mathsf T}\frac{\widehat{A}}{\eta}u_\ell\right]^{-1} \tag*{(309)} D → ∞ lim ζ → 0 lim L 1 ℓ = 1 ∑ L [ ζ − u ℓ T η A u ℓ − u ℓ T η A U − ℓ G ζ − ℓ ( U − ℓ ) T η A u ℓ ] − 1 (309)
≃ { − lim D → ∞ lim ζ → 0 1 L D ∑ ℓ = 1 L tr [ A ^ η + A ^ η U − ℓ G ζ − ℓ ( U − ℓ ) T A ^ η ] − 1 } − 1 (310) \simeq\left\{-\lim_{D\to\infty}\lim_{\zeta\to0}\frac{1}{LD}\sum_{\ell=1}^{L}\operatorname{tr}\left[\frac{\widehat{A}}{\eta}+\frac{\widehat{A}}{\eta}\mathcal{U}^{-\ell}\mathcal{G}_{\zeta}^{-\ell}(\mathcal{U}^{-\ell})^{\mathsf T}\frac{\widehat{A}}{\eta}\right]^{-1}\right\}^{-1} \tag*{(310)} ≃ ⎩ ⎨ ⎧ − D → ∞ lim ζ → 0 lim L D 1 ℓ = 1 ∑ L tr [ η A + η A U − ℓ G ζ − ℓ ( U − ℓ ) T η A ] − 1 ⎭ ⎬ ⎫ − 1 (310)
≃ { − lim D → ∞ 1 D tr [ A ^ η + y A ^ η ( I D − y A ^ η ) − 1 A ^ η ] − 1 } − 1 (311) \simeq\left\{-\lim_{D\to\infty}\frac{1}{D}\operatorname{tr}\left[\frac{\widehat{A}}{\eta}+y\frac{\widehat{A}}{\eta}\left(I_D-y\frac{\widehat{A}}{\eta}\right)^{-1}\frac{\widehat{A}}{\eta}\right]^{-1}\right\}^{-1} \tag*{(311)} ≃ ⎩ ⎨ ⎧ − D → ∞ lim D 1 tr η A + y η A ( I D − y η A ) − 1 η A − 1 ⎭ ⎬ ⎫ − 1 (311)
= { − lim D → ∞ 1 D tr [ A ^ η + y ( A ^ η ) 2 ∑ k = 0 ∞ ( y A ^ η ) k ] − 1 } − 1 (312) =\left\{-\lim_{D\to\infty}\frac{1}{D}\operatorname{tr}\left[\frac{\widehat{A}}{\eta}+y\left(\frac{\widehat{A}}{\eta}\right)^2\sum_{k=0}^{\infty}\left(y\frac{\widehat{A}}{\eta}\right)^k\right]^{-1}\right\}^{-1} \tag*{(312)} = ⎩ ⎨ ⎧ − D → ∞ lim D 1 tr η A + y ( η A ) 2 k = 0 ∑ ∞ ( y η A ) k − 1 ⎭ ⎬ ⎫ − 1 (312)
= { − lim D → ∞ 1 D tr [ A ^ η + y ( A ^ η ) 2 + y 2 ( A ^ η ) 3 + ⋯ ] − 1 } − 1 . (313) =\left\{-\lim_{D\to\infty}\frac{1}{D}\operatorname{tr}\left[\frac{\widehat{A}}{\eta}+y\left(\frac{\widehat{A}}{\eta}\right)^2+y^2\left(\frac{\widehat{A}}{\eta}\right)^3+\cdots\right]^{-1}\right\}^{-1}. \tag*{(313)} = ⎩ ⎨ ⎧ − D → ∞ lim D 1 tr η A + y ( η A ) 2 + y 2 ( η A ) 3 + ⋯ − 1 ⎭ ⎬ ⎫ − 1 . (313)
Comparing the averages of the left- and right-hand sides of Equation (E.204) and taking their inverses gives
α y ≃ − lim D → ∞ 1 D tr [ A ^ η ∑ k = 0 ∞ ( y A ^ η ) k ] = − lim D → ∞ 1 D tr [ A ^ η ( I D − y A ^ η ) − 1 ] . (314) \frac{\alpha}{y}\simeq-\lim_{D\to\infty}\frac{1}{D}\operatorname{tr}\left[\frac{\widehat{A}}{\eta}\sum_{k=0}^{\infty}\left(y\frac{\widehat{A}}{\eta}\right)^k\right]
=-\lim_{D\to\infty}\frac{1}{D}\operatorname{tr}\left[\frac{\widehat{A}}{\eta}\left(I_D-y\frac{\widehat{A}}{\eta}\right)^{-1}\right]. \tag*{(314)} y α ≃ − D → ∞ lim D 1 tr η A k = 0 ∑ ∞ ( y η A ) k = − D → ∞ lim D 1 tr η A ( I D − y η A ) − 1 . (314)
Multiplying by y y y and using Proposition E.5 gives
α = − lim D → ∞ 1 D tr [ y A ^ η ( I D − y A ^ η ) − 1 ] (315) \alpha=-\lim_{D\to\infty}\frac{1}{D}\operatorname{tr}\left[y\frac{\widehat{A}}{\eta}\left(I_D-y\frac{\widehat{A}}{\eta}\right)^{-1}\right] \tag*{(315)} α = − D → ∞ lim D 1 tr y η A ( I D − y η A ) − 1 (315)
= − lim D → ∞ 1 D tr [ ( I D − y A ^ η ) − 1 − I D ] (316) =-\lim_{D\to\infty}\frac{1}{D}\operatorname{tr}\left[\left(I_D-y\frac{\widehat{A}}{\eta}\right)^{-1}-I_D\right] \tag*{(316)} = − D → ∞ lim D 1 tr ( I D − y η A ) − 1 − I D (316)
= 1 − r φ ( y ) . (317) =1-r_{\varphi}(y). \tag*{(317)} = 1 − r φ ( y ) . (317)
Hence
r φ ( y ) = 1 − α . (318) r_{\varphi}(y)=1-\alpha. \tag*{(318)} r φ ( y ) = 1 − α . (318)
To obtain the second boundary condition, vary G ζ − ℓ \mathcal{G}_{\zeta}^{-\ell} G ζ − ℓ in Equation (E.204) while keeping u ℓ u_\ell u ℓ fixed. The linear variation satisfies
δ [ G ζ ] ℓ ℓ = [ G ζ ] ℓ ℓ u ℓ T A ^ η U − ℓ ( δ G ζ − ℓ ) ( U − ℓ ) T A ^ η u ℓ . (319) \delta[\mathcal{G}_{\zeta}]_{\ell\ell}=[\mathcal{G}_{\zeta}]_{\ell\ell}u_\ell^{\mathsf T}\frac{\widehat{A}}{\eta}\mathcal{U}^{-\ell}(\delta\mathcal{G}_{\zeta}^{-\ell})(\mathcal{U}^{-\ell})^{\mathsf T}\frac{\widehat{A}}{\eta}u_\ell. \tag*{(319)} δ [ G ζ ] ℓℓ = [ G ζ ] ℓℓ u ℓ T η A U − ℓ ( δ G ζ − ℓ ) ( U − ℓ ) T η A u ℓ . (319)
At the upper boundary, the nonzero eigenvalue support of A c / η A_{\mathrm{c}}/\eta A c / η reaches zero, as shown in Figure 3 K; the corresponding edge of the inference matrix reaches one in Figure 3 E. The resolvent G ζ \mathcal{G}_{\zeta} G ζ then becomes sensitive to a small change in the cavity equation. Using the same scalar y y y as in the first condition, this criterion becomes
1 ≃ lim D → ∞ 1 D ∥ y A ^ η ( I D − y A ^ / η ) − 1 ∥ F 2 (320) 1 \simeq\lim_{D\to\infty} \frac{1}{D}\left\lVert\frac{y\widehat{A}}{\eta}\left(I_D-y\widehat{A}/\eta\right)^{-1}\right\rVert_{\mathrm{F}}^2 \tag*{(320)} 1 ≃ D → ∞ lim D 1 η y A ( I D − y A / η ) − 1 F 2 (320)
= 1 α lim D → ∞ 1 D ∥ ( I D − y A ^ / η ) − 1 − I D ∥ F 2 (321) = \frac{1}{\alpha}\lim_{D\to\infty}\frac{1}{D}\left\lVert\left(I_D-y\widehat{A}/\eta\right)^{-1}-I_D\right\rVert_{\mathrm{F}}^2 \tag*{(321)} = α 1 D → ∞ lim D 1 ( I D − y A / η ) − 1 − I D F 2 (321)
= G φ ( y ) − 2 r φ ( y ) + 1 α . (322) = \frac{G_{\varphi}(y)-2r_{\varphi}(y)+1}{\alpha}. \tag*{(322)} = α G φ ( y ) − 2 r φ ( y ) + 1 . (322)
Substituting Equation (E.218) gives
G φ ( y ) = 1 − α . (323) G_{\varphi}(y)=1-\alpha. \tag*{(323)} G φ ( y ) = 1 − α . (323)
Thus the upper boundary is determined by
r φ ( y ) = 1 − α , G φ ( y ) = 1 − α , y > 0. (324) r_{\varphi}(y)=1-\alpha,\qquad G_{\varphi}(y)=1-\alpha,\qquad y>0. \tag*{(324)} r φ ( y ) = 1 − α , G φ ( y ) = 1 − α , y > 0. (324)
For the scalar elimination, put
β : = v φ + y , m : = φ ⟨ β x u φ + β x ⟩ 1 / φ . (325) \beta:=v_{\varphi}+y,\qquad m:=\varphi\left\langle\frac{\beta x}{u_{\varphi}+\beta x}\right\rangle_{1/\varphi}. \tag*{(325)} β := v φ + y , m := φ ⟨ u φ + β x β x ⟩ 1/ φ . (325)
The first resolvent equation reduces to
1 − α = 1 − φ + φ ⟨ 1 − y x u φ + β x ⟩ 1 / φ (326) 1-\alpha=1-\varphi+\varphi\left\langle1-\frac{yx}{u_{\varphi}+\beta x}\right\rangle_{1/\varphi} \tag*{(326)} 1 − α = 1 − φ + φ ⟨ 1 − u φ + β x y x ⟩ 1/ φ (326)
= 1 − y β m , (327) =1-\frac{y}{\beta}m, \tag*{(327)} = 1 − β y m , (327)
hence y β = α m \frac{y}{\beta}=\frac{\alpha}{m} β y = m α . The MP identity is
u φ β m = ( φ − m ) ( 1 − m ) . (328) \frac{u_{\varphi}}{\beta}m=(\varphi-m)(1-m). \tag*{(328)} β u φ m = ( φ − m ) ( 1 − m ) . (328)
Using y / β = α / m y/\beta=\alpha/m y / β = α / m , it becomes
( φ − m ) ( 1 − m ) = u φ v φ ( m − α ) = ( 1 − α ) ( 1 − α φ ) α ( m − α ) (329) (\varphi-m)(1-m)=\frac{u_{\varphi}}{v_{\varphi}}(m-\alpha)=\frac{(1-\alpha)(1-\alpha\varphi)}{\alpha}(m-\alpha) \tag*{(329)} ( φ − m ) ( 1 − m ) = v φ u φ ( m − α ) = α ( 1 − α ) ( 1 − α φ ) ( m − α ) (329)
for α < m < min { φ , 1 } \alpha<m<\min\{\varphi,1\} α < m < min { φ , 1 } .
We next reduce the Frobenius-resolvent equation (E.132) explicitly. Differentiating the MP identity at fixed u φ u_{\varphi} u φ gives
β ∂ β m = ( u φ / β ) m u φ / β + φ + 1 − 2 m = m ( φ − m ) ( 1 − m ) φ − m 2 , (330) \beta\partial_{\beta}m=\frac{(u_{\varphi}/\beta)m}{u_{\varphi}/\beta+\varphi+1-2m}=\frac{m(\varphi-m)(1-m)}{\varphi-m^2}, \tag*{(330)} β ∂ β m = u φ / β + φ + 1 − 2 m ( u φ / β ) m = φ − m 2 m ( φ − m ) ( 1 − m ) , (330)
φ ⟨ ( β x ) 2 ( u φ + β x ) 2 ⟩ 1 / φ = m − β ∂ β m . (331) \varphi\left\langle\frac{(\beta x)^2}{(u_{\varphi}+\beta x)^2}\right\rangle_{1/\varphi}=m-\beta\partial_{\beta}m. \tag*{(331)} φ ⟨ ( u φ + β x ) 2 ( β x ) 2 ⟩ 1/ φ = m − β ∂ β m . (331)
Subtracting 1 − α 1-\alpha 1 − α from Equation (E.132) and multiplying by its denominator yields
[ 1 − φ y 2 c φ ⟨ x ( u φ + β x ) 2 ⟩ 1 / φ ] [ G φ ( y ) − ( 1 − α ) ] = − α + α 2 m − α 2 m 2 β ∂ β m + ( 1 − α ) α 2 c φ m 2 ( u φ / β ) β ∂ β m (332) \begin{aligned}
\left[1-\varphi y^2c_{\varphi}\left\langle\frac{x}{(u_{\varphi}+\beta x)^2}\right\rangle_{1/\varphi}\right]\left[G_{\varphi}(y)-(1-\alpha)\right] \\
&=-\alpha+\frac{\alpha^2}{m}-\frac{\alpha^2}{m^2}\beta\partial_{\beta}m+\frac{(1-\alpha)\alpha^2c_{\varphi}}{m^2(u_{\varphi}/\beta)}\beta\partial_{\beta}m \tag*{(332)}
\end{aligned} [ 1 − φ y 2 c φ ⟨ ( u φ + β x ) 2 x ⟩ 1/ φ ] [ G φ ( y ) − ( 1 − α ) ] = − α + m α 2 − m 2 α 2 β ∂ β m + m 2 ( u φ / β ) ( 1 − α ) α 2 c φ β ∂ β m (332)
= α φ − m 2 [ m 2 − 2 α m + α − ( 1 − α ) φ + α ( 1 − α ) c φ ] (333) =\frac{\alpha}{\varphi-m^2}\left[m^2-2\alpha m+\alpha-(1-\alpha)\varphi+\alpha(1-\alpha)c_{\varphi}\right] \tag*{(333)} = φ − m 2 α [ m 2 − 2 α m + α − ( 1 − α ) φ + α ( 1 − α ) c φ ] (333)
= − α ( 1 − α ) φ − m 2 [ φ − α − α c φ − ( m − α ) 2 1 − α ] . (334) =-\frac{\alpha(1-\alpha)}{\varphi-m^2}\left[\varphi-\alpha-\alpha c_{\varphi}-\frac{(m-\alpha)^2}{1-\alpha}\right]. \tag*{(334)} = − φ − m 2 α ( 1 − α ) [ φ − α − α c φ − 1 − α ( m − α ) 2 ] . (334)
Thus the upper boundary satisfies the scalar equation
φ − α = α c φ + ( m − α ) 2 1 − α . (335) \varphi-\alpha=\alpha c_{\varphi}+\frac{(m-\alpha)^2}{1-\alpha}. \tag*{(335)} φ − α = α c φ + 1 − α ( m − α ) 2 . (335)
Set z = ( m − α ) / ( 1 − m ) > 0 z=(m-\alpha)/(1-m)>0 z = ( m − α ) / ( 1 − m ) > 0 , so that m = ( α + z ) / ( 1 + z ) m=(\alpha+z)/(1+z) m = ( α + z ) / ( 1 + z ) . Solving Equation (E.229) for φ \varphi φ gives
φ = α m ( 1 − m ) + ( 1 − α ) ( m − α ) α [ ( 1 − m ) + ( 1 − α ) ( m − α ) ] (336) \varphi=\frac{\alpha m(1-m)+(1-\alpha)(m-\alpha)}{\alpha[(1-m)+(1-\alpha)(m-\alpha)]} \tag*{(336)} φ = α [( 1 − m ) + ( 1 − α ) ( m − α )] α m ( 1 − m ) + ( 1 − α ) ( m − α ) (336)
= α 2 + z + ( 1 − α ) z 2 α ( 1 + z ) [ 1 + ( 1 − α ) z ] . (337) =\frac{\alpha^2+z+(1-\alpha)z^2}{\alpha(1+z)[1+(1-\alpha)z]}. \tag*{(337)} = α ( 1 + z ) [ 1 + ( 1 − α ) z ] α 2 + z + ( 1 − α ) z 2 . (337)
Substitution into Equation (E.235) gives
0 = ( 1 − α ) 2 z 4 + ( 1 − α ) [ 3 ( 1 − α 2 ) + α 3 ] z 3 + ( 1 − α ) [ 3 + 3 α ( 1 − α ) + α 4 ] z 2 + [ ( 1 − α ) ( 1 + 2 α ) + α 5 ] z − α 4 ( 1 − α 2 ) . (338) \begin{aligned}
0={}&(1-\alpha)^2z^4+(1-\alpha)[3(1-\alpha^2)+\alpha^3]z^3\\
&+(1-\alpha)[3+3\alpha(1-\alpha)+\alpha^4]z^2\\
&+[(1-\alpha)(1+2\alpha)+\alpha^5]z-\alpha^4(1-\alpha^2). \tag*{(338)}
\end{aligned} 0 = ( 1 − α ) 2 z 4 + ( 1 − α ) [ 3 ( 1 − α 2 ) + α 3 ] z 3 + ( 1 − α ) [ 3 + 3 α ( 1 − α ) + α 4 ] z 2 + [( 1 − α ) ( 1 + 2 α ) + α 5 ] z − α 4 ( 1 − α 2 ) . (338)
This is Equation (E.198). Every nonconstant coefficient is positive and the constant term is negative. The polynomial is therefore strictly increasing on z > 0 z>0 z > 0 and has exactly one positive root. Substituting this root into Equation (E.237) gives Equation (E.199).
The parametrization also gives
1 α − φ = ( 1 − α ) ( 1 + α + z ) α ( 1 + z ) [ 1 + ( 1 − α ) z ] . (339) \frac{1}{\alpha}-\varphi=\frac{(1-\alpha)(1+\alpha+z)}{\alpha(1+z)[1+(1-\alpha)z]}. \tag*{(339)} α 1 − φ = α ( 1 + z ) [ 1 + ( 1 − α ) z ] ( 1 − α ) ( 1 + α + z ) . (339)
The right side decreases from 1 / α − α 1/\alpha-\alpha 1/ α − α to zero, so z > 0 z>0 z > 0 parametrizes the full interval α < φ < 1 / α \alpha<\varphi<1/\alpha α < φ < 1/ α . The linear term of the polynomial bounds its root by
z + < α 4 ( 1 − α 2 ) ( 1 − α ) ( 1 + 2 α ) + α 5 < α . (340) z_+<\frac{\alpha^4(1-\alpha^2)}{(1-\alpha)(1+2\alpha)+\alpha^5}<\alpha. \tag*{(340)} z + < ( 1 − α ) ( 1 + 2 α ) + α 5 α 4 ( 1 − α 2 ) < α . (340)
On the other hand,
φ = 1 ⟺ z ( 1 + z ) = α 1 − α , (341) \varphi=1\Longleftrightarrow z(1+z)=\frac{\alpha}{1-\alpha}, \tag*{(341)} φ = 1 ⟺ z ( 1 + z ) = 1 − α α , (341)
whose positive solution is larger than α \alpha α . Hence α < φ + < 1 \alpha<\varphi_+<1 α < φ + < 1 , and these equations have no further solution before recovery.
Long-time behavior
Propositions E.6 and E.7 determine the two boundaries. Finally, we use the eigenvalues of the iteration matrix to obtain the large-t t t behavior.
Proposition E.8 (Long-time behavior). Suppose 0 < α < 1 0<\alpha<1 0 < α < 1 , λ → 0 \lambda\to0 λ → 0 , and η > 0 \eta>0 η > 0 is sufficiently small. Using the conditional averages in Proposition E.1 , assume that the largest real part among the nonzero eigenvalues of ( ( X i n ) T X i n / ( η L ) ) A c ((X^{\mathrm{in}})^{\mathsf{T}}X^{\mathrm{in}}/(\eta L))A_c (( X in ) T X in / ( η L )) A c changes from negative to positive at φ − \varphi_- φ − , changes from positive to negative at φ + \varphi_+ φ + , and does not change sign elsewhere. Assume also that the normalized traces below have finite limits and that the inverse matrices in the bounded region have uniformly bounded normalized norms.
E ( t ) = { Θ ( t 2 ) , 0 < φ < φ − ( α ) , exp ( Θ ( η t ) ) , φ − ( α ) < φ < φ + ( α ) , O ( 1 ) , φ + ( α ) < φ < 1 / α , E G D ( t ) , φ > 1 / α . (342) \mathcal{E}(t)=
\begin{cases}
\Theta(t^2), & 0<\varphi<\varphi_-(\alpha),\\
\exp(\Theta(\eta t)), & \varphi_-(\alpha)<\varphi<\varphi_+(\alpha),\\
O(1), & \varphi_+(\alpha)<\varphi<1/\alpha,\\
\mathcal{E}_{\mathrm{GD}}(t), & \varphi>1/\alpha.
\end{cases} \tag*{(342)} E ( t ) = ⎩ ⎨ ⎧ Θ ( t 2 ) , exp ( Θ ( η t )) , O ( 1 ) , E GD ( t ) , 0 < φ < φ − ( α ) , φ − ( α ) < φ < φ + ( α ) , φ + ( α ) < φ < 1/ α , φ > 1/ α . (342)
Proof. As φ → ( 1 / α ) − \varphi\to(1/\alpha)^- φ → ( 1/ α ) − , u φ , c φ → 0 u_\varphi,c_\varphi\to0 u φ , c φ → 0 , v φ → 1 v_\varphi\to1 v φ → 1 , and A ^ / η → − I D \widehat{A}/\eta\to-I_D A / η → − I D , so all nonzero eigenvalues have negative real part near 1 / α 1/\alpha 1/ α . Together with Propositions E.6 and E.7, the spectral assumption in the statement implies that the nonzero eigenvalues have negative real part below φ − \varphi_- φ − , positive real part between φ − \varphi_- φ − and φ + \varphi_+ φ + , and negative real part above φ + \varphi_+ φ + . The discussion in Subsection E.4 then gives E ( t ) = Θ ( t 2 ) \mathcal{E}(t)=\Theta(t^2) E ( t ) = Θ ( t 2 ) for 0 < φ < φ − 0<\varphi<\varphi_- 0 < φ < φ − , E ( t ) = exp ( Θ ( η t ) ) \mathcal{E}(t)=\exp(\Theta(\eta t)) E ( t ) = exp ( Θ ( η t )) for φ − < φ < φ + \varphi_-<\varphi<\varphi_+ φ − < φ < φ + , and E ( t ) = O ( 1 ) \mathcal{E}(t)=O(1) E ( t ) = O ( 1 ) for φ + < φ < 1 / α \varphi_{+}<\varphi<1/\alpha φ + < φ < 1/ α . Equation (E.2) shows that the GD matrix has not yet been recovered in the last regime.
Finally, if φ > 1 / α \varphi>1/\alpha φ > 1/ α , then α φ > 1 \alpha\varphi>1 α φ > 1 , and Proposition E.4 gives E ( t ) = E G D ( t ) \mathcal{E}(t)=\mathcal{E}_{\mathrm{GD}}(t) E ( t ) = E GD ( t ) . These arguments prove Equation (E.241).
Finally, 0 < φ − < α < φ + < 1 < 1 / α 0<\varphi_{-}<\alpha<\varphi_{+}<1<1/\alpha 0 < φ − < α < φ + < 1 < 1/ α partitions the entire α < 1 \alpha<1 α < 1 half-plane into the four open intervals in Result 4.2. For α > 1 \alpha>1 α > 1 , Proposition C.2 gives the exact recovery condition φ > 1 \varphi>1 φ > 1 , while Proposition D.2 gives the quadratic phase for 0 < φ < 1 0<\varphi<1 0 < φ < 1 . Together, these propositions give every region of Result 4.2.
Experimental Details for Fully Trained Attention
This appendix provides the full protocol for the experiments in § 6 and Figure 2 .
Data and architectures
We use the Gaussian regression task, teacher GD trajectories, prompt coordinates, and generalization error defined in § 3 . The dimension is D = 32 D=32 D = 32 , the context ratio is α = 0.75 \alpha=0.75 α = 0.75 , the training CoT length is K = 2 K=2 K = 2 , the teacher step size is η = 0.1 \eta=0.1 η = 0.1 , and the observation-noise standard deviation is σ = 0.1 \sigma=0.1 σ = 0.1 .
Both architectures have total token width 2 D + 2 2D+2 2 D + 2 . The context-only mask in § 6 means that the query is formed from the final state column,
z k : = ( E μ , k ) : , L + 1 = ( 0 D 0 s μ , k 1 ) (343) z_k := (E_{\mu,k})_{:,L+1} =
\begin{pmatrix}
0_D\\
0\\
s_{\mu,k}\\
1
\end{pmatrix} \tag*{(343)} z k := ( E μ , k ) : , L + 1 = 0 D 0 s μ , k 1 (343)
whereas the keys and values are formed only from the first L L L context columns,
( c 1 ⋯ c L ) : = ( E μ , k ) : , 1 : L = ( X μ y μ 0 D × L 0 L T ) ∈ R ( 2 D + 2 ) × L . (344) (c_1\ \cdots\ c_L) := (E_{\mu,k})_{:,1:L} =
\begin{pmatrix}
X_\mu\\
y_\mu\\
0_{D\times L}\\
0_L^{\mathsf T}
\end{pmatrix}
\in\mathbb{R}^{(2D+2)\times L}. \tag*{(344)} ( c 1 ⋯ c L ) := ( E μ , k ) : , 1 : L = X μ y μ 0 D × L 0 L T ∈ R ( 2 D + 2 ) × L . (344)
For each head, the three bias-free projections are therefore
q k h = W Q h z k , k ℓ h = W K h c ℓ , v ℓ h = W V h c ℓ . (345) q_k^h = W_Q^h z_k,\qquad k_\ell^h = W_K^h c_\ell,\qquad v_\ell^h = W_V^h c_\ell. \tag*{(345)} q k h = W Q h z k , k ℓ h = W K h c ℓ , v ℓ h = W V h c ℓ . (345)
Only z k z_k z k enters the query projection, and only c 1 , … , c L c_1,\ldots,c_L c 1 , … , c L enter the key and value projections. The resulting head output is
u k h = 1 L ∑ ℓ = 1 L ( ( q k h ) T k ℓ h ) v ℓ h (linear attention), u_k^h = \frac{1}{L}\sum_{\ell=1}^{L}\left((q_k^h)^{\mathsf T}k_\ell^h\right)v_\ell^h
\qquad\text{(linear attention),} u k h = L 1 ℓ = 1 ∑ L ( ( q k h ) T k ℓ h ) v ℓ h (linear attention),
u k h = ∑ ℓ = 1 L exp ( ( q k h ) T k ℓ h / d h ) ∑ j = 1 L exp ( ( q k h ) T k j h / d h ) v ℓ h (softmax attention). (346) u_k^h = \sum_{\ell=1}^{L}\frac{\exp\left((q_k^h)^{\mathsf T}k_\ell^h/\sqrt{d_h}\right)}{\sum_{j=1}^{L}\exp\left((q_k^h)^{\mathsf T}k_j^h/\sqrt{d_h}\right)}v_\ell^h
\qquad\text{(softmax attention).} \tag*{(346)} u k h = ℓ = 1 ∑ L ∑ j = 1 L exp ( ( q k h ) T k j h / d h ) exp ( ( q k h ) T k ℓ h / d h ) v ℓ h (softmax attention). (346)
Thus the state token is absent from the key/value sequence, rather than present with a zero key and value.
Linear attention has one head with d 1 = 2 D + 2 d_1=2D+2 d 1 = 2 D + 2 , learns the matrices W Q 1 , W K 1 , W V 1 ∈ R ( 2 D + 2 ) × ( 2 D + 2 ) W_Q^1,W_K^1,W_V^1\in\mathbb{R}^{(2D+2)\times(2D+2)} W Q 1 , W K 1 , W V 1 ∈ R ( 2 D + 2 ) × ( 2 D + 2 ) , and has no learned output projection. A fixed readout selects the D D D state coordinates of the head output, and the residual connection adds this increment to the current state:
s ^ μ , k + 1 = s μ , k + ( u k 1 ) D + 2 : 2 D + 1 . (347) \hat{s}_{\mu,k+1}=s_{\mu,k}+(u_k^1)_{D+2:2D+1}. \tag*{(347)} s ^ μ , k + 1 = s μ , k + ( u k 1 ) D + 2 : 2 D + 1 . (347)
Its Q/K/V weights use the default PyTorch linear-layer initialization, which samples each entry uniformly from [ − 1 / 2 D + 2 , 1 / 2 D + 2 ] [-1/\sqrt{2D+2},1/\sqrt{2D+2}] [ − 1/ 2 D + 2 , 1/ 2 D + 2 ] , followed by multiplication by 0.1 0.1 0.1 .
Softmax attention has two heads with d 1 = d 2 = D + 1 d_1=d_2=D+1 d 1 = d 2 = D + 1 . It learns the bias-free W Q h , W K h , W V h ∈ R ( D + 1 ) × ( 2 D + 2 ) \mathbf{W}_Q^h,\mathbf{W}_K^h,\mathbf{W}_V^h\in\mathbb{R}^{(D+1)\times(2D+2)} W Q h , W K h , W V h ∈ R ( D + 1 ) × ( 2 D + 2 ) and W O ∈ R ( 2 D + 2 ) × ( 2 D + 2 ) \mathbf{W}_O\in\mathbb{R}^{(2D+2)\times(2D+2)} W O ∈ R ( 2 D + 2 ) × ( 2 D + 2 ) . The two head outputs are concatenated, mapped by W O \mathbf{W}_O W O , restricted to the same D D D state coordinates, and added to the current state:
s ^ μ , k + 1 = s μ , k + [ W O ( u k 1 u k 2 ) ] D + 2 : 2 D + 1 . (348) \hat{s}_{\mu,k+1}=s_{\mu,k}+\left[\mathbf{W}_O\begin{pmatrix}u_k^1\\u_k^2\end{pmatrix}\right]_{D+2:2D+1}. \tag*{(348)} s ^ μ , k + 1 = s μ , k + [ W O ( u k 1 u k 2 ) ] D + 2 : 2 D + 1 . (348)
Optimization and evaluation
Each model is trained for 5,000 AdamW updates with initial learning rate 0.003, cosine decay to 0.00003, weight decay 10 − 4 10^{-4} 1 0 − 4 , gradient-norm clipping at 10, and minibatches of at most 128 transitions. For each seed, evaluation uses 192 independently generated test contexts and a recursive horizon of 128 steps.