TRAINING DATA SIZE INDUCED DOUBLE DESCENT FOR DENOISING NEURAL NETWORKS AND THE ROLE OF TRAINING NOISE LEVEL
Year: 2021

Abstract:
When training a denoising neural network, we show that more data isn’t more beneficial. In fact the generalization error versus number of of training data points is a double descent curve. Training a network to denoise noisy inputs is the most widely used technique for pre-training deep neural networks. Hence one important question is the effect of scaling the number of training data points. We formalize the question of how many data points should be used by looking at the generalization error for denoising noisy test data. Prior work on computing the generalization error focus on adding noise to target outputs. However, adding noise to the input is more in line with current pre-training practices. In the linear (in the inputs) regime, we provide an asymptotically exact formula for the generalization error for rank 1 data and an approximation for the generalization error for rank r data. We show using our formulas, that the generalization error versus number of data points follows a double descent curve. From this, we derive a formula for the amount of noise that needs to be added to the training data to minimize the denoising error and see that this follows a double descent curve as well.

heading: 1 INTRODUCTION
text: Denoising noisy training data is a widely used technique for pretraining networks to learn good representations of the data. Two extremely common examples of pretraining via denoising are Masked Language Modelling (MLM) (Devlin et al., 2019) and Stacked Denoising Autoencoders (SDAE) (Vincent et al., 2010). For many modern problem, we work at large scales in terms of the number of parameters and the number of training samples. Recently there has been significant work in understanding the effect of scaling the number of parameters in the neural network. This resulted
in the discovery of the much celebrated double descent phenomena (Belkin et al., 2019). However, we do not have as good of an understanding of the effect of scaling the number of data points. Works such as Nakkiran et al. (2020); Nakkiran (2020); d’Ascoli et al. (2020); Adlam & Pennington (2020) show either empirically or via theoretical analysis that sample wise double descent exists. However, these were in the regime of supervised learning. On the other hand, our motivation comes from understanding denoising autoencoders. For MLM and SDAEs the denoising is a pretraining procedure, in which case the generalization error would depend on the downstream task. We shall instead look at the generalization error with respect to denoising test data. The difference between prior supervised learning set up and our denoising set up can be seen in Figure 1.
In an attempt to theoretically understand the denoising setting, we look at the simplest setting. Specifically we look at the case, when our network is a linear (with respect to the inputs) network and we are denoising data that lies on a line embedded in high dimensional space. In this setting, we derive the exact asymptotics for the generalization error. We see that in this case, the generalization error spikes at the interpolation threshold (Figure 5a) and the amount of noise that we want to add also spikes at the interpolation threshold (Figure 5b). From the theoretical analysis, we see that the spike occurs due to the variance of the model increasing.
Contributions. The main contributions of our works are as follows.
1. We empirically show that when denoising data using a feedforward network, the curve for the generalization error versus the number of training data points as well the curve for the ratio of the test data SNR to the optimal training data SNR has double descent. Further changing the training data SNR can mitigate the double descent in the generalization error curve. 2. Assuming we have mean 0, rotational invariant noise, we derive an analytical formula for the expected mean squared generalization error for denoising rank 1 data by a linear network. Further, we use the same method to derive an approximation for higher rank data and experimentally verify the accuracy of the formula for general low rank data. 3. Using our formula, we show that even in this simple model, we see that the double descent exists for the generalization error and for the amount of noise that should be added versus the number of training data points.
Related work. Understanding deep neural networks is current active area of research with many exciting theoretical results. The discovery that fixed depth infinite width neural networks can be thought of as kernel regression (Jacot et al., 2018) and the discovery of double descent for neural networks (Belkin et al., 2019) has sparked significant research into understanding the generalization in the linear regime (in parameters not inputs). The exact asymptotic for generalization loss were first understood for ridge regression (Bartlett et al., 2020; Hastie et al., 2019; Belkin et al., 2020; Advani & Saxe, 2020). This was further generalized to understand the situation for the Random Features model and the Neural Tangent Kernel (NTK) model (Mei & Montanari, 2019; Ghorbani et al., 2019; Adlam & Pennington, 2020). A partial list of recent work for supervised learning includes Jacot et al. (2020); Mel & Ganguli (2021); Derezinski et al. (2020); d’Ascoli et al. (2020); Dobriban & Wager (2015); Geiger et al. (2019); Lampinen & Ganguli (2019); Liang et al. (2020); Muthukumar et al. (2019); Loureiro et al. (2021). However, there has been no work, to our knowledge, that looks at the problem either empirically or theoretically for the denoising set up.
The idea of adding noise to improve generalization has been seen before. One popular strategy is to use Dropout (Hinton et al., 2012; Wan et al., 2013; Srivastava et al., 2014), where we randomly zero out either neurons or connections. Another idea that is commonly used is data augmentation. In a revolutionary paper, Krizhevsky et al. (2012) showed that augmenting the dataset with noisy versions of the images, greatly improved the accuracy. Another area where noise is useful is adversarial learning. Dong et al. (2021) shows epoch wise double descent for adversarial training.
In terms of recent theoretical work related to SDAEs, Pretorius et al. (2018) derived the learning dynamics of a linear autoencoder in the presence of noise. They also establish some relationships between the noise added and weight decay. However, they do not look at the generalization error or quantify the optimal amount of noise that should be added. Gnansambandam & Chan (2020) looked at the problem of what is the optimal amount of noise that should be added. However, they studied this from the perspective of minimizing the variance of the performance.

heading: 2 SET-UP
text: Let U ∈ RM×r be our feature matrix. For ease of notation, we assume that the columns of U have unit norm and are pairwise orthogonal. Then to generateN data points, we sample our latent variables V ∈ Rr×N and Σ ∈ Rr×r+ such that V has columns that have unit norm and are pairwise orthogonal and Σ is a diagonal matrix such that ‖Σ‖F = 1. Then a data matrix X is given by X = UΣV T . For us, we have two matrices Xtrn and Xtst that correspond to the train and test data sets. Hence we have corresponding V Ttrn ∈ Rr×Ntrn , V Ttst ∈ Rr×Ntst , and Σtrn, Σtst. We make no other assumptions on U, Vtrn,ΣtrnVtst,Σtst except that they are given and fixed. Finally, let θtst, θtrn ∈ R+ be scalars that will scale the singular values of Xtrn, Xtst so that we can control the SNR. We also assume that θtst is fixed and that we have control over θtrn. Let c = M/Ntrn and let Atrn, Atst be noise matrices that are added to the training and the test data. Let W be the linear autoencoder that is the solution to the following problem
minimizeŴ ‖θtrnXtrn − Ŵ (θtrnXtrn +Atrn︸ ︷︷ ︸ Ytrn )‖2F . (1)
Then, the expected mean squared error, is given by R(θtrn, θtst, c,Σtrn,Σtst) := E [ ‖θtstXtst −W (θtstXtst +Atst)‖2F
Ntst
] . (2)

heading: 2.1 ASSUMPTIONS ABOUT THE NOISE
text: We assume that each entry of the noise matrix A has mean 0, variance 1/M and that the entries of A are pairwise uncorrelated. Additionally, we shall assume that A is rotationally bi-invariant. That is, if Q is an M by M (N by N ) orthogonal matrix, then QA (AQ) has the same distribution as A. Another way to phrase this is if A = UAΣAV TA is the SVD, then UA and VA are uniformly random orthogonal matrices and are independent from ΣA and each other. Finally, we shall assume that A has full rank with probability 1 and that the limiting distribution of the eigenvalues of ATA converge to the Marchenko-Pastur distribution. While such assumptions on the noise may seem restrictive. This encompasses a large family of noise distributions. Proposition 1. If B is a random matrix that has full rank with probability 1 and its entries are independent, have mean 0, have variance 1/M , and bounded fourth moment, and P,Q are uniformly random orthogonal matrices. Then A = PBQ satisfies all of our noise assumptions.

heading: 2.2 SIGNAL TO NOISE RATIO (SNR)
text: A quantity of interest to us will be the SNR, given by ‖X‖F /‖A‖F . Hence, we need to normalize everything by ‖A‖F . In this case, due to our assumptions, we have that E[‖A‖2F ] = N . Hence, for any variables and constants, if it has a hat, then that refers to that variable or constant normalized by√ N . For example, given θtrn, Xtrn, and Atrn, then we have that
‖θtrnXtrn‖F /‖Atrn‖F = θtrn/‖Atrn‖F ≈ θtrn/ √ Ntrn =: θ̂trn.

heading: 3 EMPIRICAL DOUBLE DESCENT
text: We first show that sample wise double descent occurs for denoising neural networks empirically. Figure 2 shows that if we train a feedforward network to denoise data such that the training data signal to noise ratio (SNR) θ̂trn is the same SNR as that of the test data set (θ̂tst), then the curve for the denoising generalization error vs the number of training samples has the shape of a double descent curve. Thus, together with prior work, this suggests that the double descent with respect to the number of data points is a universal phenomena. However, unlike other hyperparameters, such as number of features and number of training epochs, we cannot arbitrarily change the number of data points as we are limited by the data set that we have. Hence it could be the case, that the maximum number of data points that we have corresponds to the peak of the generalization error curve.
However, we can look at the amount of noise that we add to the training data. To see the effect of the noise, for a variety of different θ̂trn/θ̂tst, we compute the denoising generalization error versus
the number of data points curve. We do this for MNIST and CIFAR dataset. We create test data sets by taking the test data for each and then adding Gaussian noise. We fix the test SNR to be 1 for both datasets. Hence we know the test data SNR. We then take various different fractions of the training data and train a 3 layer ReLU neural network (without bias) for various levels of training noise. For each of pair of parameters (number of training data points and the level of training noise), we compute the generalization error averaged over 20 trials for MNIST and 5 trials for CIFAR. Here the test noise and training noise is resampled for each trial. The plots for the generalization error can be seen in Figures 3a (MNIST) and 3b (CIFAR10). The first thing we notice is that for most ratios for the test SNR to training SNR we see sample wise double descent. Further, we see that the optimal denoising error does not occur when the train SNR is equal to the test SNR. This is very surprising as it contradicts standard thought that training data distribution should be the same as the test data distribution. Interestingly, as seen in Figures 4 and 4b, we see that the optimal ratio depends on the number of data points and the shape of the curve for the values θ̂trn/θ̂tst that results in the best generalization error versus the number data points also has the shape of a double descent curve.

heading: 4 THEORETICAL RESULTS AND CONSEQUENCES
text: In this paper, we want to theoretically understand the phenomena seen in Section 3. The main theoretical result of the paper is summarized below in Theorem 1. Theorem 1. Let σtrni , σtsti be entries of Σtrn,Σtst and let r = 1. Let c = M/Ntrn be fixed. Suppose θtrn is O( √ Ntrn) and θtst is O( √ Ntst) Then, if c < 1, we have that
R(θtrn, θtst, c,Σtrn,Σtst) = (θtstσ
tst 1 ) 2
Ntst(1 + (θtrnσtrn1 ) 2c)2
+ c2((θtrnσ trn 1 ) 2 + (θtrnσ trn 1 ) 4)
M(1 + (θtrnσtrn1 ) 2c)2(1− c)
+ o(1)
(3) and if c > 1, we have that
R(θtrn, θtst, c,Σtrn,Σtst) = (θtstσ
tst 1 ) 2
Ntst(1 + (θtrnσtrn1 ) 2)2
+ c(θtrnσ
trn 1 ) 2
M(1 + (θtrnσtrn1 ) 2)(c− 1)
+ o(1). (4)
The o(1) error term goes to 0 as Ntrn,M →∞.
We could imagine that the rank r version is the same as the above but with a summation over the rank as shown in the equations below. But, we shall see in Section 5 that this turns out to only be an approximation. 1
R(θtrn, θtst, c,Σtrn,Σtst) ≈ r∑ i=1
(θtstσ tst i ) 2
Ntst(1 + (θtrnσtrni ) 2c)2
+ c2((θtrnσ trn i ) 2 + (θtrnσ trn i ) 4)
M(1 + (θtrnσtrni ) 2c)2(1− c)
+o(1)
(5)
R(θtrn, θtst, c,Σtrn,Σtst) ≈ r∑ i=1
(θtstσ tst i ) 2
Ntst(1 + (θtrnσtrni ) 2)2
+ c(θtrnσ
trn i ) 2
M(1 + (θtrnσtrni ) 2)(c− 1)
+ o(1).
(6)

heading: 4.1 OPTIMAL AMOUNT OF NOISE
text: First, if we ignore the error term, we can differentiate the formula to get the following formula for the optimal training SNR.
θ2opt−trn Ntrn = max ( 0, θ2tst Ntst ( 1− c 2−c ) − c M(2−c) ) c < 1 max ( 0, 2
θ2tst Ntst (c− 1)− 1 Ntrn
) c > 1
(7)
We already see the surprising result that the optimal training SNR and the test SNR are not equal. This is surprising, as traditional philosophy is that the training data should be drawn from the same distribution as the test data. Here instead we see that the optimal training distribution actually depends c. Further, the formulas in Equation 7 also describe a double descent curve for θopt−trn/Ntrn versus c curve as shown in Figure 5b.
1Derivation and exact assumptions for when the formulas are accurate in the appendix.

heading: 4.2 DOUBLE DESCENT CURVES
text: We have already seen that the optimal amount of training noise follows a double decent curve. This is due to the double descent seen in the asymptotics for the generalization error. To understand this phenomenon, we first note that the bias of our model is given by the first term in formula in Theorem 1 and the variance is given by the second term. That is, we have that the variance given by ∑r i=1 c2((θtrnσ trn i ) 2+(θtrnσ trn i ) 4) M(1+(θtrnσtrni ) 2c)2(1−c) c < 1∑r i=1 c(θtrnσ trn i ) 2
M(1+(θtrnσtrni ) 2)(c−1) c > 1
From these formulas, we can see that as c→ 1 these formulas have a singularity. Since we have a linear model, c = 1 is the interpolation threshold (i.e., the point after which we have 0 training error). Hence as with previous models for double descent, we see that as we approach the interpolation threshold, the variance of model increases, resulting in an increase in the generalization error.
If we fix the number of features M and change c by varying Ntrn, and also scale θtrn as θtrn = θ̂trn √ Ntrn, then we see that as c→ 1, the variance of the model increases. Once we have enough data points so that c < 1, we have the variance of the model starts decreasing. Additionally, we see that as we increase the number of data points, the bias decreases until we hit the interpolation threshold, after this point, the bias is constant. Similarly, if we fixed Ntrn and changed c by changing M then after the interpolation threshold, the inductive bias of the model kicks in. Here we see that the variance terms corresponds to ‖W‖2F . Hence we see that as c→∞, we have that this implicitly regularize the weights of the network and get the second descent in the generalization error. That is, the variance of the model decreases as c→∞. Additionally, we see that as we increase the number of parameters, the bias of the model of the model decreases and then after the interpolation threshold it becomes constant. Note that this value is non-zero and depends on the training SNR.
In previous work (such as Mei & Montanari (2019)) on double descent curves for ridge regression, we see that optimal ridge regularization results in the vanishing of the double descent phenomena. This is also seen empirically for L2 regularization for classification in Nakkiran et al. (2020). However, in our theoretical model even if we optimally pick the amount of training noise, we still have double descent. This is in contrast to results seen with a deep network on real data in Figure 3.

heading: 5 PROOF OF THEOREM 1
text: We prove Theorem 1, via the steps shown in Figure 6. The proofs for all of the lemmas have been moved to the appendix. Here we present a proof sketch that details the high-level ideas.

heading: 5.1 STEP 1: DECOMPOSE THE ERROR INTO BIAS AND VARIANCE TERMS
text: First, we decompose the error into its bias and variance. Lemma 1. If Atst has mean 0 entries and Atst is independent of Xtst and W , then
EAtst [‖θtstXtst −WYtst‖2F ] = θ2tstEAtst [‖Xtst −WXtst‖2F ]︸ ︷︷ ︸ Bias +EAtst [‖WAtst‖2F ]︸ ︷︷ ︸ V ariance . (8)

heading: 5.2 STEP 2: FORMULA FOR W
text: In our current setup, we know that W is the solution to a least-squares problem. Hence W = XtrnY † trn. Expanding this out, we get the following formula for W . Let h = v T trnA † trn, k = A † trnu, s = (I −AtrnA†trn)u, t = vtrn(I −A † trnAtrn), β = 1 + θtrnv T trnA † trnu, τ1 = θ 2 trn‖t‖2‖k‖2 + β2, and τ2 = θ2trn‖s‖2‖h‖2 + β2. Proposition 2. If β 6= 0 and Atrn has full rank then
W =
{ θtrnβ σ1 uh+ θ2trn‖t‖ 2 τ1 ukTA†trn c < 1
θtrnβ σ2
uh+ θ2trn‖h‖ 2
τ2 usT c > 1
.
For Gaussian noise Atrn has full rank with probability 1 and β is a random variable whose expected value is equal to 1, and the distribution is highly concentrated. Thus, Proposition 2 applies when Atrn is isotropic Gaussian noise. Here we restricted ourselves to rank 1, as using Meyer (1973), we can expand formulas of the form (A+ xyT )† where x, y are vectors. For the higher rank case, we apply the formula form Meyer (1973) iteratively. This is the main difficulty of the method. Previous work on deriving asypmtotics for the generalization error had the noise on the output. Hence would take the pseudoinverse of a matrix that only depended on the data. However, in our case, we are taking the pseudoinverse of matrix that depends on the noise.

heading: 5.3 STEP 3:DECOMPOSE THE TERMS INTO SUM OF VARIOUS TRACE TERMS.
text: Let us first look at the bias term. Lemma 2. If W is the solution to Equation 1, then
Xtst −WXtst =
{ β τ1 Xtst if c < 1
β τ2 Xtst if c > 1
.
Let us now look at the second or the variance term. Lemma 3. If the entries of Atst are independent with mean 0, and variance 1/M , then we have that EAtst [‖WAtst‖2] = NtstM ‖W‖ 2.
Note that this did not need any assumptions on W or Xtst. All that was needed were the assumptions on Atst. Thus, this holds more generally. This decomposition also follows from Bishop (1995). In light of Lemmas 1, 2, 3, and the fact that ‖Xtst‖2F = θ2tst, we see that the expected mean squared generalization error is given by,
EAtst [ ‖θtstXtst −WYtst‖2F
Ntst
] = 1
Ntst
β2 τ2i θ2tst + 1 M ‖W‖2F ,
where τi depends on whether c < 1 or c > 1. Finally, let us look at the ‖W‖ term. Lemma 4. If β 6= 0 and Atrn has full rank, then we have that if c < 1,
‖W‖2F = θ2trnβ 2
τ21 Tr(hTh) + 2 θ3trn‖t‖2β τ21 Tr(hT kTA†trn) + θ4trn‖t‖4 τ21 Tr((A†trn) T kkTA†trn)
and if c > 1, then we have that
‖W‖2F = θ2trnβ 2
τ22 Tr(hTh) + 2 θ3trn‖h‖2β τ22 Tr(hT sT ) + θ4trn‖h‖4 τ22 Tr(ssT ).

heading: 5.4 STEP 4: ESTIMATE USING RANDOM MATRIX THEORY.
text: While the formula given by Lemmas 1, 3, and 4 is correct, we need a simpler formula to analyze the situation. Using ideas from random matrix theory, we can simplify the expression for ‖W‖2F . To do so, we first need to prove Lemmas 5 and 6.
The main idea behind Lemmas 5 and 6 is that due to the rotational invariance of Atrn, the expectation of the trace of products of various matrices derived from Atrn is determined by the expected value of some function χ of the eigenvalues of Atrn. However, instead of directly computing this expected value, we note that for any matrix A, that satisfies the noise assumptions, if we let M,N → ∞, with M/N → c, then the eigenvalue distribution converges to the Marchenko - Pastur distribution (Marcenko & Pastur, 1967; Götze & Tikhomirov, 2011; 2003; 2004; 2005; Bai et al., 2003). Götze & Tikhomirov (2004) showed that the distribution of the eigenvalues converged almost surely with a rate of at least O(N−1/2+ ) for any > 0. Thus, we can use the expected value of the χ(λ) for λ sampled from the Marchenko - Pastur distribution as an approximation.
For space reasons, we provide only one instance of the lemmas in the main text. The complete versions can be found in the appendix. Lemma 5. Suppose A is an p by q matrix such that the entries of A are independent and have mean 0, variance 1/q, and bounded fourth moment. Let Wp = AAT and let Wq = ATA. Let C = p/q. Suppose λp, λq are a random eigenvalue of Wp,Wq . Then
1. If p < q, then E [
1 λp ] = 11−C + o(1).
Lemma 6. SupposeA is an p by q matrix that satisfies the noise assumptions. Let x, y be unit vectors in p and q dimensions. Let C = p/q. Then
1. E[Tr(xT (AAT )†x)] =
{ 1
1−C + o(1) p < q q p C−1 1−C−1 + o(1) p > q .
Using these technical lemmas, we can now deal with all of the terms in the expressions in Lemma 4. First, let us look at the non-trace terms. Lemma 7. If Atrn satisfies the noise assumptions, then we have that
1. E[β/θtrn] = 1/θtrn + o(1) and Var(β/θtrn) = c(max(M,Ntrn)|1−c|)) + o(1). 2. If c < 1, then E[‖h‖2] = c 2
1− c + o(1) and Var(‖h‖2) = c
3(2 + c)
Ntrn(1− c)3 + o(1).
3. If c > 1, then E[‖h‖2] = c c− 1 + o(1) and Var(‖h‖2) = c 2(2c− 1) Ntrn(c− 1)3 + o(1). 4. E[‖k‖2] = c 1− c + o(1) and Var(‖k‖2) = c 2(2 + c) M(1− c)3 + o(1).
5. E[‖s‖2] = c− 1 c + o(1) and Var(‖s‖2) = 2 1 Mc + o(1) 6. E[‖t‖2] = 1− c+ o(1), Var(‖t‖2) = 2 c Ntrn + o(1).
Lemma 8. Under the noise assumptions, we have that
E[Tr(hT kTA†trn)] = 0 and Var(Tr(hT kTA † trn)) = χ3(c)/Ntrn,
where χ3(c) = E[1/λ3], λ is an eigenvalue for AAT and A is as in Lemma 6. Lemma 9. Under the noise assumptions, we have that
Tr((A†trn) T kkTA†trn) =
c2
(1− c)3 +o(1) and Var(Tr((A†trn) T kkTA†trn)) = 3 M χ4(c)− 1 M
c4
(1− c)6
where χ4(c) = E[1/λ4], λ is an eigenvalue for AAT and A is as in Lemma 6. Lemma 10. Under the same assumptions as Proposition 2, we have that Tr(hT sT ) = 0.
Lemmas 7, 8, 9, and 10 tell us that all of the terms are highly concentrated. Thus, even though such terms may not be uncorrelated, we can use the fact that |E[XY ]− E[X]E[Y ]| < √ Var(X)Var(Y ), to treat the terms as if they are uncorrelated. Since these variances have now been shown to be o(1), we have that for each of these terms E[XY ] = E[X]E[Y ] + o(1). For example, since τ1 = β
2 + θ2trn‖t‖2‖k‖2 + o(1), using Lemmas 1, 4, and 6, we have that E[τ1] = 1 + θ2trnc+ o(1). Similarly, E[τ2] = 1 + θ2trn + o(1). Finally, using these lemmas, we can simplify the expressions in Lemma 4 to get the formulas for the expected generalization error shown in Equations 3 and 4.

heading: 6 ACCURACY OF APPROXIMATION
text: In this section we experimentally verify the accuracy of our formula for general rank r data. Here for low SNR (θtrn, θtst are O(1)), we sample σtrni , σ tst i I.I.D. from the squared standard Gaussian and
for high SNR (θtrn, θtst are Θ( √ Ntrn),Θ( √ Ntst)), we multiply this by √ Ntrn, √ Ntst. As we can from Figure 7, we see that our formula is better for low SNR and low rank data.

heading: 7 CONCLUSION
text: In this paper, we switch focus from supervised set up to the unsupervised set up. Specifically, we look at the problem of denoising data. We empirically show that sample wise double descent exists for the generalization error. Further, we show that the optimal amount of training noise is not the same as the test noise. In fact, we see sample wise double descent for the ratio for the test SNR to the optimal training noise. To understand this phenomena, we study the simplest model, denoising rank 1 data using a linear model. Here we derive the exact asymptotics for the generalization error.

heading: A NOISE ASSUMPTIONS
text: Proposition 1. If B is a random matrix that has full rank with probability 1 and its entries are independent, have mean 0, and have variance 1/M and P,Q are uniformly random orthogonal matrices. Then A = PBQ satisfies all of our noise assumptions.
Proof. Since P,Q are a uniformly random orthogonal matrices, and A = PBQ, then it is clear that A is rotationally bi-invariant and has full rank.
Since each entry of B has mean 0 and each entry of A is a linear combination of entries of B where the coefficients (i.e., the entries from P,Q are independent of B), we have that each entry of B have mean 0. Due to the orthogonal nature of P,Q, we have the variance for an entry of A is the same as the variance of entry in B.
Thus, the only thing left to prove is that the entries of A are uncorrelated. To do this, we note that
aij = N∑ k=1 M∑ l=1 pilblkqkj .
Consider two entries ai1j1 and ai2j2 . Then we have that
E[ai1j1ai2j2 ] = E [( N∑ k=1 M∑ l=1 pi1lblkqkj1 )( N∑ k=1 M∑ l=1 pi2lblkqkj2 )]
= N∑ k=1 M∑ l=1 E[pi1lpi2l]E[b2lk]E[qkj1qkj2 ]
= 1
M E [ M∑ l=1 pi1lpi2l ] E [ N∑ k=1 qkj1qkj2 ] .
The second inequality follows from the fact that P,Q,B are independent from each other, and that fact that the entries of B are independent and have mean 0. Hence the cross terms have expectation 0. If we have that i1 = i2 and j1 6= j2, then we have that since Q is an orthogonal matrix
N∑ k=1 E[qkj1qkj2 ] = E [ N∑ k=1 qkj1qkj2 ] = 0.
Thus, the entries are uncorrelated. Similarly when i1 6= i2 since P is orthogonal matrix, we get that the entries are uncorrelated.
Convergence to Marchenko-Pastur. If we strengthened the uncorrelated condition, to the entries being independent. Then due to the mean and variance assumptions (along with an assumption that the fourth moment is bounded), we would have convergence to Marchenko-Pastur distribution. However, the independence along with the bi-invariance would then force our noise distribution to be i.i.d. Gaussian.
In general however, with relaxed assumption of the entries only being uncorrelated, convergence is not known. However, in our case, we have a much simpler proof for matrices formed by Proposition 1. In our case, the noise matrices B satisfy the standard assumptions for convergence. We then multiply B by orthogonal matrices that are independent to B. Hence this has no effect on the eigenvalue distribution. Thus, the eigenvalues distribution for these matrices also converge to the Marchenko-Pastur distribution.

heading: B PROOFS
text: Due to our data generation assumptions that ‖Σtrn‖F = ‖Σtst‖F = 1 for rank 1 data, we have that σtrn1 = σ tst 1 = 1.
B.1 STEP ??: DECOMPOSE INTO BIAS AND VARAINCE
Lemma 1. If Atst has mean 0 entries and Atst is independent of Xtst and W , then EAtst [‖Xtst −WYtst‖2F ] = EAtst [‖Xtst −WXtst‖2F ]︸ ︷︷ ︸
Bias
+EAtst [‖WAtst‖2F ]︸ ︷︷ ︸ V ariance .
Proof. Using the fact that for any two matrices ‖G−H‖2F = ‖G‖2F + ‖H‖2F − 2Tr(GTH), we get that
‖Xtst −WYtst‖2 = ‖Xtst −WXtst −WAtst‖2F = ‖Xtst −WXtst‖2F + ‖WAtst‖2 − 2Tr((Xtst −WXtst)TWAtst).
Then since the trace is linear, and Xtst,W are independent of Atst, and Atst has mean 0 entries, we see that EAtst [Tr((Xtst −WXtst)TWAtst)] = 0. Thus, we have the needed result.
B.2 STEP ??: FORMULA FOR Wopt
Proposition 2. Let h = vTtrnA † trn, k = A † trnu, s = (I − AtrnA † trn)u, t = vtrn(I − A † trnAtrn), β = 1 + θtrnv T trnA † trnu, τ1 = θ 2 trn‖t‖2‖k‖2 + β2, and τ2 = θ2trn‖s‖2‖h‖2 + β2. If β 6= 0 and Atrn has full rank then
Wopt =
{ θtrnβ τ1 uh+ θ2trn‖t‖ 2 τ1 ukTA†trn c < 1
θtrnβ τ2
uh+ θ2trn‖h‖ 2
τ2 usT c > 1
.
Proof. Let us first proof the case when c > 1. Here we know that u is arbitrary. Here we have that Atrn has full rank. Thus, since c > 1, we have that M > Ntrn, thus Atrn has rank Ntrn. Thus, the rows of Atrn span the whole space. Thus, vtrn lives in the range of ATtrn. Finally, since β 6= 0, we want Theorem 5 from Meyer (1973).
Here let us further define
p2 = − θ2trn‖s‖2
β A†trnh
T − θtrnk and qT2 = − θtrn‖h‖2
β sT − h
and finally τ2 = θ2trn‖s‖2‖h‖2 + β2. Then we have from Meyer (1973) that
(Atrn + θtrnuv T trn) † = A†trn + θtrn β A†trnh T sT − β τ2 p2q T 2
In our case, we only care about θtrnuvTtrn(Atrn + θtrnuv T trn) †. Thus let us multiply this through and see what we get.
θtrnuv T trn(Atrn + θtrnuv T trn) † = θtrnuv T trn(A † trn + θtrn β A†hT sT − β τ2 p2q T 2 )
= θtrnuh+ θ2trn‖h‖2
β usT +
θtrnβ
τ2 uvTtrn
( θ2trn‖s‖2
β A†trnh T + θtrnk
) qT2
= θtrnuh+ θ2trn‖h‖2
β usT +
θ3trn‖s‖2‖h‖2
τ2 uqT2 +
θ2trnβ
τ2 uhuqT2
Then we have that θ3trn‖s‖2‖h‖2
τ2 cqT2 = −
θ4trn‖s‖2‖h‖4
τ2β usT − θ
3 trn‖s‖2‖h‖2
τ2 uh (9)
and
θ2trnβ
τ2 uhuqT2 = −
θ3trn‖h‖2
τ2 uhusT − θ
2 trnβ
τ2 uhuh. (10)
Using that β − 1 = θtrnvTtrnA † trnu = θtrnhu, we get that
θ2trnβ
τ2 uhuqT2 = − θ2trn‖h‖2(β − 1) τ2 usT − θtrnβ(β − 1) τ2 uh. (11)
Substituting back in and collecting like terms we get that
θtrnuv T trn(Atrn + θtrnuv T trn) † = θtrnu
( 1− θ 2 trn‖s‖2‖h‖2
τ2 − β(β − 1) τ2
) h+
θ2trnu
( ‖h‖2
β − θ
2 trn‖s‖2‖h‖4 τ2β − ‖h‖ 2(β − 1) τ2
) sT
We can then simplify the constants as follows.
1− θ 2 trn‖s‖2‖h‖2 τ2 − β(β − 1) τ2 = τ2 − θ2trn‖s‖2‖h‖2 − β2 + β τ2 = β τ2
and
‖h‖2
β −θ
2 trn‖s‖2‖h‖4 τ2β −‖h‖ 2(β − 1) τ2 = ‖h‖2(τ2 − θ2trn‖s‖2‖h‖2 − β(β − 1) βτ2 = ‖h‖2β βτ2 = ‖h‖2 τ2 .
This gives us the result for c < 1.
If c > 1, then we have that M < Ntrn. Thus, the rank of Atrn is M the range of Atrn is the whole space. Thus, u lives in the range of Atrn. In this case, we then want Theorem 3 from Meyer (1973). In this case, we define
p1 = − θ2trn‖k‖2
β tT − k and qT1 = −
θtrn‖t‖2
β kTA†trn − h.
Then in this case, we have that
(Atrn + θtrnuv T trn) † = A†trn + θtrn β tT kTA†trn − β τ1 p1q T 1 .
Then we simplify the equation as we did before!
B.3 STEP ??: EXPAND INTO TRACE TERMS
Lemma 3. If the entries of Atst are independent with mean 0, and variance 1/M , then we have that EAtst [‖WAtst‖2] = NtstM ‖W‖ 2.
Proof. To see this, we note if we look at AtstATtst, then this is a M by M , for which the expected value of the off diagonal entries is equal to 0, while the expected value of each diagonal entry is Ntst/M . That is, EAtst [AtstATtst] = NtstM IM .
Then note that
‖WAtst‖2 = Tr(ATtstWTWAtst) = Tr(WTWAtstATtst) = Tr(WTWAtstATtst).
Using the fact that the trace is linear again, we see that
EAtst [Tr(WTWAtstATtst)] = Tr(WTWEAtst [AtstATtst]) = Ntst M Tr(WTW ) = Ntst M ‖W‖2F .
Lemma 2. If W is the solution to Equation 1, then
Xtst −WXtst =
{ β τ1 Xtst if c < 1
β τ2 Xtst if c > 1
.
Proof. To see this, we have the following calculation for when Ntrn > M .
Xtst −WXtst = Xtst − θtrnθtstβ
τ1 uhuvTtst −
θ2trnθtst‖t‖2
τ1 ukTA†trnuv T tst
= Xtst − θtrnθtstβ
τ1 uvTtrnA † trnuv T tst −
θ2trnθtst‖t‖2
τ1 ukTA†trnuv T tst.
First, we note that β = 1 + θtrnvTtrnA † trnu. Thus, we have that θv T trnA † trnu = β − 1. Thus, substituting this into the second term, we get that
Xtst −WXtst = Xtst − θtstβ(β − 1)
τ1 uvTtst −
θ2trnθtst‖t‖2
τ1 ukTA†trnuv T tst.
For the third term, we note that k = A†trnu. Thus, we have that k TA†trnu = k
T k = ‖k‖2. Substituting this into the expression, we get that
Xtst −WXtst = Xtst − θtstβ(β − 1)
τ1 uvTtst −
θ2trnθtst‖t‖2‖k‖2
τ1 uvTtst.
Noting that Xtst = θtstuvTtst, we get that Xtst −WXtst = Xtst (
1− β(β − 1) τ1 − θ 2 trn‖t‖2‖k‖2 τ1
) .
To simplify the constants, we note that τ1 = θ2trn‖t‖2‖k‖2 + β2. Thus, we get that
τ1 + β − β2 − θ2trn‖t‖2‖k‖2
τ1 =
β τ1 .
For the case when Ntrn < M , we note that the first term of W is the same (modulo replacing τ1 for τ2) as it is for the case when c > 1. Thus, we just need to deal with the last term. Here we see that the last term is
θ2trnθtst‖h‖2
τ2 usTuvTtst.
Here we note that s = (I −AtrnA†trn)u. Thus, in particular, s is the projection of u onto the kernel of ATtrn. Thus, we have that u = s+ ŝ, where s ⊥ ŝ. This then tells us that sTu = ‖s‖2. Thus, for this term, we get that it is equal to
θ2‖h‖2‖s‖2
τ2 Xtst.
For this term we note that τ2 = β2 + θ2‖h‖2‖u‖2. Thus, doing the same simplification as before, we see that for the case when Ntrn < M , we have that
Xtst −WXtst = β
τ2 Xtst.
In light of Lemma 2 and the fact that ‖Xtst‖2F = θ2tst. We see that if we look at the expected MSE, we have that,
EAtst [ ‖Xtst −W (Xtst +Atst)‖
Ntst
] = β
Ntstτi θ2tst +
1
M ‖W‖2F ,
where τi depends on whether c < 1 or c > 1.
Finally, let us look at the ‖W‖ term.
Lemma 4. If β 6= 0 and Atrn has full rank, then we have that if c < 1,
‖W‖2F = θ2trnβ 2
τ21 Tr(hTh) + 2 θ3trn‖t‖2β τ21 Tr(hT kTA†trn) + θ4trn‖t‖4 τ21 Tr((A†trn) T kkTA†trn)
and if c > 1, then we have that
‖W‖2F = θ2trnβ 2
τ22 Tr(hTh) + 2 θ3trn‖h‖2β τ22 Tr(hT sT ) + θ4trn‖h‖4 τ22 Tr(ssT ).
Proof. To deal with the term Tr(WTW ) we are again going to have to look at whether Ntrn is bigger than or smaller than M . First, let us start by looking at the case when Ntrn > M . Here we have that
‖W‖2F = Tr(WTW )
= Tr
(( θtrnβ
τ1 uh+
θ2trn‖t‖2
τ1 ukTA†trn
)T ( θtrnβ
τ1 uh+
θ2trn‖t‖2
τ1 ukTA†trn
))
= θ2trnβ 2
τ21 Tr(hTuTuh) + 2 θ3trn‖t‖2β τ21 Tr(hTuTukTA†trn) + θ4trn‖t‖4 τ21 Tr((A†trn) T kuTukTA†trn)
= θ2trnβ 2
τ21 Tr(hTh) + 2 θ3trn‖t‖2β τ21 Tr(hT kTA†trn) + θ4trn‖t‖4 τ21 Tr((A†trn) T kkTA†trn).
Where the last inequality is true due to the fact that ‖u‖2 = 1. How about when Ntrn < M . Then we have the following string of equalities instead.
‖W‖2F = Tr(WTW )
= Tr
(( θtrnβ
τ2 uh+
θ2trn‖h‖2
τ2 usT
)T ( θtrnβ
τ2 uh+
θ2trn‖h‖2
τ2 usT
))
= θ2trnβ 2
τ22 Tr(hTuTuh) + 2 θ3trn‖h‖2β τ22 Tr(hTuTusT ) + θ4trn‖h‖4 τ21 Tr(suTusT )
= θ2trnβ 2
τ22 Tr(hTh) + 2 θ3trn‖h‖2β τ22 Tr(hT sT ) + θ4trn‖h‖4 τ22 Tr(ssT ).
B.4 STEP ??: ESTIMATE USING RANDOM MATRIX THEORY.
Lemma 5. Suppose A is an p by q matrix such that the entries of A are independent and have mean 0, variance 1/q, and bounded fourth moment. Let Wp = AAT and let Wq = ATA. Let C = p/q. Suppose λp, λq are a random eigenvalue of Wp,Wq . Then
1. If p < q, then E [
1 λp ] = 11−C + o(1).
2. If p < q, then E [
1 λ2p ] = 1(1−C)3 + o(1).
3. If p < q, then E [
1 λ3p ] = 1(1−C)5 + o(1).
4. If p < q, then E [
1 λ4p
] = C2+ 226 c+1
(1−C)7 + o(1). 5. If p > q, then E [
1 λq
] = C −1
1−C−1 + o(1). 6. If p > q, then E [
1 λ2q
] = C −2
(1−C−1)3 + o(1).
7. If p > q, then E [
1 λ3p
] = C
−3(1+C−1) (1−C−1)5 + o(1). 8. If p > q, then E [
1 λ4p
] = C−4(C−2+ 226 C −1+1)
(1−C−1)7 + o(1).
Proof. Suppose A is an p by q matrix such that the entries of A are independent and have mean 0, variance 1/q, and bounded fourth moment. Then we know that Wp = AAT is an p by p Wishart matrix with c = C. If we send p, q to infinity such that p/q remains constant, then we have the eigenvalue distribution Fp converges to the Marchenko Pastur distribution F in probability.
From Rao & Edelman (2008), we know there exists a bi variate polynomial L(m, z) = czm2 − (1− c− z)m+ 1 such that the zeros of L(m, z) given by L(m(z), z) are such that
m(z) =
∫ 1
λ− z dF (λ) = Eλ
[ 1
λ− z
] .
For the Marchenko-Pastur distribution, we have that for z = 0, we get that m(z) = 1/(1− c). Thus, for λp is an eigenvalue value of Wp, we have that
E [ 1
λp
] = 1
1− c + o(1).
For Eλ [ 1 (λ−z)2 ] we need to calculate m′(0). Using the implicit function theorem, we know that
m′(z) = −1 ( ∂L
∂m (m(z), z)
)−1 ∂L
∂z (m(z), z).
Here we can see that ∂L/∂m = 2czm + c + z − 1. Thus, at (1/(1 − c), 0), this is equal to c − 1. Also ∂L/∂z = cm2 +m. Again at (1/(1− c), 0) this is equal to c(1−c)2 + 1 1−c = 1 (1−c)2 . Thus, we have that
m′(0) = 1
(1− c)3 .
Similarly, using the implicit function formulation, we can calculate m′′(0) and m′′′(0).
On the other hand if q < p, then Wq := ATA is not a Wishart matrix here, because it is scaled by the wrong constant. However, multiplying it by 1/C gives us the correct scaling. Thus, ATA/C is a Wishart matrix with c = 1/C Thus, for λq is an eigenvalue value of Wq , we have that
E [ 1
λq
] = C−1
1− C−1 + o(1).
We can obtain the rest in a similar manner from the previous results.
Lemma 6. Suppose A is an p by q matrix that satsifies the standard noise assumptions. Let x, y be unit vectors in p and q dimensions. Let C = p/q. Then
1. E[Tr(xT (AAT )†x)] =
{ 1
1−C + o(1) p < q q p C−1 1−C−1 + o(1) p > q .
2. E[Tr(xT (AAT )†(AAT )†x)] =
{ 1
(1−C)3 + o(1) p < q q p C−2 (1−C−1)3 + o(1) p > q .
3. E[Tr(yT (ATA)†y)] =
{ p q
1 1−C + o(1) p < q C−1
1−C−1 + o(1) p > q .
4. E[Tr(yT (ATA)†(ATA)†y)] =
{ p q
1 (1−C)3 + o(1) p < q C−2
(1−C−1)3 + o(1) p > q .
Proof. Let A = UΣV T be the SVD. Then we have that (AAT )† = U(Σ2)†UT . Then since A is bi-unitary invariant, we have that U is a uniformly random unitary matrix. Thus, a = xTU is a uniformly random unit vector. Note with probability 1, the rank of A is full and that the non-zero eigenvalues of ATA and AAT are the same.
If p < q, then we have that
E[Tr(xT (AAT )†x)] = p∑ i=1 a2i 1 σ2i .
Using Lemma 5, we have that E[1/2i ] = 1/(1− C) + o(1). Thus, we have that
E[Tr(xT (AAT )†x)] = p∑ i=1 1 p 1 1− C + o(1).
On the other hand, if p > q, from Lemma 5, we have that E[1/2i ] = C−1/(1− C−1) + o(1). Thus,
E[Tr(xT (AAT )†x)] = q∑ i=1 1 p C−1 1− C−1 + o(1).
Similarly, if we had we looking at Tr(xT (AAT )†(AAT )†x), we would have a 1/4i term instead. Thus, if p < q, we would have that
E[Tr(xT (AAT )†(AAT )†x)] = 1
(1− C)3 + o(1).
A similar calculation holds for the others.
Now we have the following Lemma in the main text. However, here instead of having one big proof, we will separate each term out into its own lemma.
Lemma 7. If Atrn satisfies the standard noise assumptions, then we have that
1. E[β] = 1 + o(1) and Var(β) = θ 2 trnc
(max(M,Ntrn)|1−c|)) + o(1).
2. If c < 1, then E[‖h‖2] = c 2 1− c + o(1) and Var(‖h‖2) = c 3(2 + c) Ntrn(1− c)3 + o(1). 3. If c > 1, then E[‖h‖2] = c c− 1 + o(1) and Var(‖h‖2) = c 2(2c− 1) Ntrn(c− 1)3 + o(1). 4. E[‖k‖2] = c 1− c + o(1) and Var(‖k‖2) = c 2(2 + c) M(1− c)3 + o(1). 5. E[‖s‖2] = c− 1 c + o(1) and Var(‖s‖2) = 2 1 Mc + o(1) 6. E[‖t‖2] = 1− c+ o(1), Var(‖t‖2) = 2 c Ntrn + o(1).
Lemma 11. β term.
Proof. First, we calculate the expected value of β. To do so, let Atrn = UΣV T be the SVD. Then since Atrn is bi-unitarily invariant, we have that U, V are uniformly random unitary matrices. Since u, vtrn are fixed. We have that a := vTtrnV ∈ RNtrn and b := UTu ∈ RM are uniformly random unit vectors. In particular, we have that E[ai] = 0,E[bi] = 0,Var(ai) = 1/Ntrn,Var(bi) = 1/M .
Thus, if σi are the singular values for Atrn, then we have that
β = 1 + θtrn min(M,Ntrn)∑ i=1 1 σi aibi.
Thus, if you take the expectation you get that
E[β] = 1.
On the other hand, lets look at the variance. For the variance, we need to compute E[β2]. Now if we let T := θtrnvTtrnA † trnu. Then we have that
β2 = 1 + T 2 + 2T.
Thus, again if we take the expectation, we get that
E[β2] = 1 + E[T 2].
Again due to the fact that a, b are independent have have mean 0 entries, the cross terms in E[T 2]. Thus, we have that
E[T 2] = θtrn2E min(M,Ntrn)∑ i=1 1 σ2i a2i b 2 i  = θtrn2 1 MNtrn E min(M,Ntrn)∑ i=1 1 σ2i  . Now we need to case on whether M > Ntrn or M < Ntrn. Now to use Lemma 5, we note that q = M and p = Ntrn.
Suppose we have that M > Ntrn, then in this case, we have that q > p. Thus, we have that E [ 1
σ2i
] = 1
1− C + o(1),
where C = p/q = Ntrn/M = 1/c. Thus, we have that E [ 1
σ2i
] =
1
1− 1/c + o(1) =
c
c− 1 + o(1).
Thus, we have that
E[T 2] = θ2trn c
M(c− 1) + o
( 1
M
) .
Thus, we have
Var(β) = θ2trn c
M(c− 1) + o
( 1
M
) .
On the other hand, if M < Ntrn. Then we have that q < p. Thus, we have that E [ 1
σ2i
] = C−1
1− C−1 + o(1),
where C = p/q = Ntrn/M = 1/c. Thus, we have that E [ 1
σ2i
] = c
1− c + o(1).
Thus, we have that
E[T 2] = θ2trn 1
Ntrn
( c
1− c + o(1)
) =
c
Ntrn(1− c) + o
( 1
Ntrn
) .
Thus, we have
Var(β) = θ2trn c
Ntrn(1− c) + o
( 1
Ntrn
) .
Lemma 12. ‖h‖2 term.
Proof. We want to do a calculation similar to that in Lemma 1. Here we have that
‖h‖2 = Tr(hTh) = Tr((A†trn)T vtrnvTtrnA † trn) = Tr(v T trnA † trn(A † trn) T vtrn) = Tr(vTtrn(A T trnAtrn) †vtrn).
To use Lemma 6, we note that A = ATtrn, q = M , p = Ntrn. Let us now suppose that M < Ntrn. Then again taking the expectation, we see that
E[‖h‖2] = M Ntrn
( c
1− c + o(1)
) = c2
1− c + o(1).
For the expectation of ‖h‖4, let Atrn = UΣV T be the svd. Then h = vTtrnV Σ†UT . Let a = vTtrnV and note that a is a uniformly random unit vector. Thus, we have that
‖h‖2 = M∑ i=1 1 σ2i a2i .
For the expectation of ‖h‖4, we note that
‖h‖4 = M∑ i=1 M∑ j=1 1 σ2i σ 2 j a2i a 2 j = M∑ i=1 1 σ4i a4i + ∑ i 6=j 1 σ2i 1 σ2j a2i a 2 j .
Taking the expectation of the first term, we get M∑ i=1 E [ 1 σ4i ] E[a4i ] = 3M N2trn ( c2 (1− c)3 + o(1) ) = 3
c3
Ntrn(1− c)3 + o(1).
Taking the expectation of the second term, we get M(M−1)E [ 1
σ2i
]2 E[a2i ]2 = M(M−1) 1
N2trn
( c2
(1− c)2 + o(1)
) =
c4
(1− c)2 − c
3
Ntrn(1− c)2 +o(1).
Thus, we have that
E[‖h‖4] = c 4
(1− c)2 +
c3(2 + c)
Ntrn(1− c)3 + o(1).
Thus, the variance is
Var(‖h‖2) = c 3(2 + c)
Ntrn(1− c)3 + o(1).
For M > Ntrn, we instead have that
E[‖h‖2] = Ntrn Ntrn
( c
c− 1 + o(1)
) = c
c− 1 + o(1).
For the expectation of ‖h‖4, we note that
‖h‖4 = Ntrn∑ i=1 Ntrn∑ j=1 1 σ2i σ 2 j a2i a 2 j = Ntrn∑ i=1 1 σ4i a4i + ∑ i 6=j 1 σ2i 1 σ2j a2i a 2 j .
Taking the expectation of the first term, we get Ntrn∑ i=1 E [ 1 σ4i ] E[a4i ] = 3Ntrn N2trn ( c3 (c− 1)3 + o(1) ) = 3
c3
Ntrn(c− 1)3 + o(1).
Taking the expectation of the second term, we get Ntrn(Ntrn − 1)E [ 1
σ2i
]2 E[a2i ]2 = Ntrn(Ntrn − 1) 1
N2trn
( c2
(c− 1)2 + o(1) ) = c2
(c− 1)2 − c
2
Ntrn(c− 1)2 + o(1).
Thus, we have that
E[‖h‖4] = c 2
(c− 1)2 + 3
c3
Ntrn(c− 1)3 − c
2
Ntrn(c− 1)2 +o(1) =
c2
(c− 1)2 + c2(2c− 1) Ntrn(c− 1)3 +o(1).
Thus, the variance is
Var(‖h‖2) = c 2(2c− 1)
Ntrn(c− 1)3 + o(1).
Lemma 13. ‖k‖2 term.
Proof. First note that k only appears in the formula when c < 1. Thus, we can focus on this case. As with h, we have that
‖k‖2 = Tr(uT (A†trn)TA † trnu) = Tr(u T (AtrnA T trn) †u).
Again using Lemma 6, with q = M,p = Ntrn, A = Atrn, y = u. Thus, since we have q = M < Ntrn = p, we get that
E[‖k‖2] = c 1− c + o(1).
To calculate the variance, we need to calculate the expectation of ‖k‖4. Here be again letA = UΣV T be the SVD. Then let b := UTu. Then we have that
‖k‖2 = M∑ i=1 1 σ2i b2i .
Thus, we see that
‖k‖4 = M∑ i=1 1 σ4i b4i + ∑ i6=j 1 σ2i 1 σ2j b2i b 2 j .
Taking the expectation of the first term we get
3 M M2 c2 (1− c)3 =
3c2
M(1− c)3 .
Taking the expectation of the second term we get
M(M − 1) M2 c2 (1− c)2 =
c2
(1− c)2 − c
2
M(1− c)2 .
Thus, we have that
E[‖k‖4] = c 2
(1− c)2 +
c2(2 + c)
M(1− c)3 + o(1).
Thus, we have that
Var(‖k‖2) = c 2(2 + c)
M(1− c)3 + o(1).
Lemma 14. ‖s‖2 term.
Proof. First, we note that s only appears when M > Ntrn. Thus, we only need to deal with that case. For this term, we note that (I − AtrnA†trn) is a projection matrix onto a uniformly random M −Ntrn dimensional subspace. Here be again let A = UΣV T be the SVD. Then let b := UTu.
E[‖s‖2] = E[uTu− uTAtrnA†trnu] = E [ 1− bT [ INtrn 0
0 0
] b ] = 1− Ntrn∑ i=1 1 M = 1− 1 c
Similarly, we have that
‖s‖4 = ( 1−
Ntrn∑ i=1 b2i
)2
= 1 + ( Ntrn∑ i=1 b2i )2 − 2 Ntrn∑ i=1 b2i
= 1 + Ntrn∑ i=1 b4i + Ntrn∑ i6=j b2i b 2 j − 2 Ntrn∑ i=1 b2i
Taking the expectation, we get that
E[‖s‖4] = 1 + 3 Ntrn∑ i=1 1 M2 + Ntrn∑ i 6=j 1 M2 − 2 Ntrn∑ i=1 1 M
= 1 + 3 cM + Ntrn(Ntrn − 1) M2 − 21 c = 1 + 3
cM +
1 c2 − 1 cM − 21 c
= ( 1− 1
c
)2 + 2
cM
Thus, we have that
Var(‖s‖2) = 2 1 cM
Lemma 15. ‖t‖2 term.
Proof. First, we note that t only appears when M < Ntrn. Thus, we only need to deal with that case. For this term, we note that (I − A†trnAtrn) is a projection matrix onto a uniformly random Ntrn −M dimensional subspace. Then similar to ‖s‖2, we have that
E[‖t‖2] = E[vTtrnvtrn − vTtrnA † trnAtrnvtrn] = E
[ 1− aT [ IM 0 0 0 ] a ] = 1− M∑ i=1 1 Ntrn = 1− c
Similarly, we have that
‖t‖4 = ( 1−
M∑ i=1 a2i
)2
= 1 + ( M∑ i=1 a2i )2 − 2 M∑ i=1 a2i
= 1 + M∑ i=1 a4i + M∑ i 6=j a2i a 2 j − 2 M∑ i=1 a2i
Taking the expectation, we get that
E[‖t‖4] = 1 + 3 M∑ i=1 1 N2trn + M∑ i 6=j 1 N2trn − 2 M∑ i=1 1 Ntrn
= 1 + 3c Ntrn + Ntrn(Ntrn − 1) M2 − 2c = 1 + 3c
Ntrn + c2 − c Ntrn − 2c
= (1− c)2 + 2 cM
Thus, we have that Var(‖t‖2) = 2 c
Ntrn
Now we could just use the the fact that |E[XY ]− E[X]E[Y ]| < √
Var(X)Var(Y ). Another way to do this is via using big O in probability. Which is defined as follows:
Definition 1. We save that a sequence of random variables Xn is OP (an), if there exists an N such that for all > 0, there exists a constantL such that for all n ≥ N , we have that Pr[|Xn| > Lan] < .
Then the trace terms.
Lemma 8. Under standard noise assumptions, we have that
E[Tr(hT kTA†trn)] = 0 and Var(Tr(hT kTA†trn)) = χ3(c)/Ntrn, where χ3(c) = E[1/λ3], λ is an eigenvalue for AAT and A is as in Lemma 6.
Proof. First we note that
Tr(hT kTA†trn) = Tr((A † trn) T vtrnu T (A†trn) TA†trn) = u T (A†trn) T (A†trnA † trn) T vtrn).
Again let Atrn = UΣV T be the SVD. Then, we have the middle terms depending on Atrn simplifies to
(A†trn) TA†trn(A † trn) T = U(Σ†)TΣ†(Σ†)TV T .
Thus, again letting b = uTU and a = V T vtrn. We see that
Tr(hT kTA†trn) = M∑ i=1 aibi 1 σ3i .
Now if take the expectation, since a, b are independent and mean 0, we see that
EAtrn [Tr(hT kTA † trn)] = 0.
Let us also compute the variance. Here we have that
E[Tr(hT kTA†trn)2] = M∑ i=1 E [ 1 σ6i ] E[a2i ]E[b2i ] + 0.
Now for the Marchenko Pastur distribution we have that the expectation of 1/λ3 = χ3(c). where χ3 is some function. Thus, we have that
E[Tr(hT kTA†trn)2] = 1
Ntrn χ3(c) + o(1).
Lemma 9. Under standard noise assumptions, we have that
Tr((A†trn) T kkTA†trn) =
c2
(1− c)3 + o(1)
and
Var(Tr((A†trn) T kkTA†trn)) =
3
M χ4(c)−
1
M
c4
(1− c)6
where χ4(c) = E[1/λ4], λ is an eigenvalue for AAT and A is as in Lemma 6.
Proof. Now using Lemma 6, we see that
EAtrn [Tr((A † trn) T kkTA†trn)] = c2
(1− c)3 .
Similar to proofs before, we have that
EAtrn [Tr((A † trn) T kkTA†trn) 2] = M∑ i=1 3 M2 χ4(c) + ∑ i 6=j 1 M2 c4 (1− c)6 + o(1).
Where χ4(c) = E[1/λ4] for the Marchenko Pastur distribution. Thus, we have that
Var(Tr((A†trn) T kkTA†trn)) =
3
M χ4(c) +
1
M
c4
(1− c)6 + o(1).
Lemma 10. Under the same assumptions as Proposition 2, we have that Tr(hT sT ) = 0.
Proof. Here we note that hT = (A†trn) T vtrn and sT = uT (I −AtrnA†trn)T . Thus, we have that
Tr(hT sT ) = Tr((A†trn) T vtrnu T − (A†trn)T vtrnuT (AtrnA † trn) T )
= Tr(vTtrnA † trnu)− Tr(uT (AtrnA † trn) T (A†trn) T vtrn) = Tr(vTtrnA † trnu)− Tr(vTtrnA † trnAtrnA † trnu) = Tr(vTtrnA † trnu)− Tr(vTtrnA † trnu)
= 0
As we can see that if we take the expectation of ‖W‖ over Atrn, since the variance of each of the terms is small, we can approximate E[XY ] with E[X]E[Y ]. Then we get the following.
If M < Ntrn, we have that
EAtrn [‖W‖2] = θ2trn
(1 + θ2trnc) 2
c2
(1− c) + 0 +
θ4trn(1− c)2 (1 + θ2trnc) 2
c2
(1− c)3
= c2 θ2trn + θ 4 trn
(1 + θ2trnc) 2(1− c)
.
On the other hand, M > Ntrn, we have that
EAtrn [‖W‖2] = θ2trn
(1 + θ2trn) 2
c
c− 1 + θ4trn (1 + θ2trn) 2
c2 (c− 1)2 c− 1 c
= c c− 1 θ2trn(1 + θ 2 trn)
(1 + θ2trn) 2
= θ2trn
1 + θ2trn
c
c− 1 .
Now combining everything together, we get that
EAtrn,Atst [ ‖Xtst −W (Xtst+Atst)‖
Ntst
] =  θ2tst Ntst(1+θ2trnc) 2 + 1 M c 2 θ 2 trn+θ 4 trn (1+θ2trnc) 2(1−c) c < 1
θ2tst Ntst(1+θ2trnc) 2 + 1 M θ2trn 1+θ2trn c c−1 c > 1
.
B.5 PROOF OF THEOREM
We can see that the main text has how to put all of the pieces together to prove the main Theorem. We don’t replicate that here.
B.6 FORMULA FOR θ̂opt−trn
As stated in the main text, we only need to take the derivative. So, we don’t present that calculation here as it is fairly straightforward.

heading: C GENERALIZATIONS
text: In this section we discuss some possible generalizations of the method.
C.1 HIGHER RANK
Let us present some heuristics for the higher rank formula. To do so we shall need some notation. Let Xtrn = ∑r i=1 σ trn i ui(v trn i ) T . Let A be the noise matrix. Then for 1 ≤ j ≤ r, define
Aj =
( A+
j−1∑ i=1 σtrni ui(v trn i ) T
)
We shall now make some assumptions. Specifically, we assume that uj , vtrnj , and Aj are all such that for i1 6= i2, and for all j we have that
E[uTi1AjA † jui2 ] = E[(v trn i1 ) TA†jAjv trn i2 ] = 0.
Additionally, we assume that for all i1, i2, j we have that E[(vtrni1 ) TA†jui2 ] = 0. We also assume that the variance of these terms goes to 0 as Ntrn,M go to infinity. Lemma 16. With the given assumptions, we have that for all i < j,
σtrni ui(v trn i ) TA†j ≈ σ trn i ui(v trn i ) TA†j−1 ≈ σ trn i ui(v trn i ) TA†j−2 ≈ . . . ≈ σ trn i ui(v trn i ) TA†i+1
Proof. Write Aj = Aj−1 + σtrnj uj(v trn k ) T and the use Meyer (1973) to expand the pseudoinverse of Aj . When we do this, we see that due to the assumption all terms expect σtrni ui(v trn i )
TA†j−1 are small.
Define hj = (vtrnj ) TA†j , kj = σ trn j A † juj , tj = (v trn j ) T (I − A†jAj), sj = σtrnj (I − AjA † j)uj ,
βj = 1 + σ trn j (v trn j ) TA†juj , τ (j) 1 = ‖tj‖2‖kj‖2 + β2j , τ (j) 2 = ‖sj‖2‖hj‖2 + β2j , and similarly p (j) 1 , p (j) 2 , q (j) 1 , and q (j) 2 . Now, we can write
Xtrn +A = σ trn r ur(v trn r ) T +Ar−1
Then we have that
W = X(σtrnr ur(v trn r ) T +Ar) † = r∑ i=1 σtrni ui(v trn i ) T (σtrnr ur(v trn r ) T +Ar) †
Expanding and using the lemma, we get that
W ≈ r∑ i=1 σtrni ui(v trn i ) TA†i+1 =  ∑r i=1 σtrni βi τ (i) 1 uihi + (σtrni ) 2‖ti‖2 τ (i) 1 uik T i A † i c < 1∑r i=1 σtrni βi
τ (i) 2
uihi + (σtrni ) 2‖hi‖2
τ (i) 2
uis T i c > 1
Where the second equality comes from the rank 1 results.
Now that we have an approximation for W (given our assumptions), we can now approximate the variance and bias terms again. Let Wi denote the ith factor (corresponding to ui) of W . First, for the bias, due to the orthogonality of the u’s we get that
‖Xtst −WXtst‖2F = r∑ i=1 ∥∥∥∥∥∥σtsti ui(vtsti )T −Wi r∑ j=1 σtsti ui(v tst i ) T ∥∥∥∥∥∥ 2
F
Again, using our assumptions, we see that the terms in the j summation dropout besides when j = i. Then again using our rank 1 result, we get that
‖Xtst −WXtst‖2F = r∑ i=1
( βi
τ (i) idx
σtsti )2 For the variance, we again estimate the norm of W by expanding the trace. Here we see that the cross terms are 0 due to factors of uTi1ui2 . For the diagonal terms, we again use the rank 1 results and get that
‖W‖2F = r∑ i=1 (σtrni ) 2β2i (τ (i) 1 ) 2 Tr(hTi hi) + 2 (σtrni ) 3‖ti‖2βi (τ (i) 1 ) 2 Tr(hTi k T i A † i ) + (σtrni ) 4‖ti‖4 (τ (i) 1 ) 2 Tr((A†i ) T kik T i A † i )
and if c > 1, then we have that
‖W‖2F = r∑ i=1 (σtrni ) 2β2i (τ (i) 2 ) 2 Tr(hTi hi) + 2 (σtrni ) 3‖hi‖2βi (τ (i) 2 ) 2 Tr(hTi s T i ) + (σtrni ) 4‖hi‖4 (τ (i) 2 ) 2 Tr(sisTi ).
The final step would be to estimate each of these terms using random matrix theory. However, unfortunately the Aj may not satisfy all of the needed conditions. However, we know that Aj is a perturbation of A and A satisfies all of the needed conditions. Hence, if the perturbation is small, we can replace Aj with A and hopefully not incur too much cost. Note this is also the reason why the previous assumptions might be reasonable. If we replace Aj’s with A use our estimates from the rank 1 result. We then get our estimate for the generalization error for general rank r data.
R(θtrn, θtst, c,Σtrn,Σtst) = r∑ i=1
(θtstσ tst i ) 2
Ntst(1 + (θtrnσtrni ) 2c)2
+ c2((θtrnσ trn i ) 2 + (θtrnσ trn i ) 4)
M(1 + (θtrnσtrni ) 2c)2(1− c)
+o(1)
(12) and if c > 1, we have that
R(θtrn, θtst, c,Σtrn,Σtst) = r∑ i=1
(θtstσ tst i ) 2
Ntst(1 + (θtrnσtrni ) 2)2
+ c(θtrnσ
trn i ) 2
M(1 + (θtrnσtrni ) 2)(c− 1)
+ o(1).
(13)
In the experimental section, we see that for small values of r for c bounded away from 1. This seems to be good estimate for the generalization error.
C.2 RANDOM FEATURES MODEL
Here we assumed that our data is given X = UΣV T . One generalization of this that we have a G who entries i.i.d Gaussian, or whose columns are uniformly distributed on the unit sphere. Then for non linear function σ, we assume that X = σ(GUΣV T ). If we assume that σ is linear, the we have that as L → ∞, GTG → IM . Thus, we have that GU approximately satisfies our assumptions of orthogonal columns. Hence we expect our formula to still be a reasonable approximation.

heading: D EXPERIMENTS
text: Please see accompanying notebook for code to produce the data for all of the figures.
D.1 LOW SNR AND HIGH SNR DATA
For low SNR data, we sample the θ times singular values from a squared standard Gaussian. We do this independently for all 2r singular values. We call this the low SNR region because θ is not being scaled with the number of data points. Hence as Ntrn, Ntst →∞, the SNR goes to 0. For the high rank data, we sample θ times singular values from a squared Gaussian and then multiply by √ Ntrn, √ Ntst. Hence here the SNR does not go to 0 as Ntrn, Ntst →∞.

heading: E GENERALIZATION ERROR VERSUS TRAINING NOISE LEVEL PLOTS
text: E.1 MORE TESTS FOR RANK 1
Here we provide more examples of c and how our theoretical formula matches the experimental performance exactly.
Each empirical point is the average over 50 trials. These were run on a laptop with 8gb of RAM and an i3 processors. The average time to produce any of these plots is about 10 to 30 minutes.
E.2 RANK 2 DATA
Let us now demonstrate that the double descent shaped curve exists beyond rank 1 data and linear autoencoders. We will do this by gradually making the set up more complicated until we can no longer recreate this phenomena. First, we consider rank 2 data is of the following form. Let Wdata be some fixed matrix, then our data is generated by
X = relu(Wdatarelu(uv T ).
Where a different v is sampled for the training and test data. the results for this can be seen in Figure 9. As we can from the figure, we have the exact same qualitative trend for c that we saw before. That is, as c goes from 0 to 1, we have that θ̂trn goes from θ̂tst to 0, and then as c→∞, we have that θ̂trn goes to infinity as well.
E.3 MNIST DATA
We now look at the linear network with MNIST data.
E.3.1 NON-LINEAR NETWORK
Here, we trained each network for 1500 epochs. During each epoch we computed a gradient using the whole data set. We used Adam as the optimizer with the code written in Pytorch. Each data point was generated over 20 trials.
These experiments take a little bit more time to run and the one with bigger amounts of data can take upto 5 hours on a google cloud instance with 16gb RAM. Here we used a Telse P4 gpu.
LRL - is a model with a reLU at the end of the first layer only.

Review summaries:
This paper identifies and studies a double descent phenomenon (wrt the training data size) for a denoising problem, where the goal is to recover a low-rank ground truth given a corrupted version of it (with added full-rank noise). The paper considers the linear regression estimator, and gives the exact formula for the test risk in the asymptotic regime for the rank-1 case; for a general rank r, the paper also gives a formula, but it's not entirely rigorous. Furthermore, the paper also studies the role of the training and testing SNRs.

In this paper, the authors study overparameterization of autoencoders in terms of varying sample size. They derive an analytic expression for the bias-variance decomposition of the loss for a bottleneck of size 1. Furthermore, they approximate the bias-variance decomposition for larger bottleneck sizes. This is done with all linear networks. They experimentally show double descent in nonlinear networks as well.

The paper investigates a new double-descent in denoising task for linear predictors. As the number of samples increases the denoising loss exhibits a peak in the case of linear predictions, but the peaks are less pronounced in the case of neural networks, except for the case with rank 1 data. The authors calculate an asymptotical formula for their special rank-1 data model in theorem 1 which proves the explosion at (c=1). For the arbitrary rank data, the authors present an approximate formula too. 

This paper considers a denoising setup for a linear model. Compared with the traditional supervised learning setup where the noise is added to the output, the denoising setup has noise in the input. The authors provide an asymptotically exact formula for the generalization error for rank 1 data and an approximation for higher rank data. Both the theoretical and numerical results validate that the generalization error has a peak when the number of samples is equal to the number of features, which is consistent with existing literature about the double descent phenomenon. Authors also derive a formula for the amount of noise in the training data for the best generalization performance, which leads to a novel conclusion that the optimal noise amount in the training data is not always equal to the noise level in the test data.