Adjacency Spectral Embeddings of Correlation Networks Keith Levin Abstract In many applications, weighted networks are constructed based on time series data: each time series is associated to a vertex and edge weights are given by pairwise correlations. The result is a network whose edge dependency structure violates the assumptions of most common network models. Nonetheless, it is common to analyze these “correlation networks” using embedding methods derived from edge-independent network models, based on a belief that the edges are approximately independent. In this work, we put this modeling choice on firm theoretical ground. We show that when the time series are expressible in terms of a small number of Fourier basis elements (or in some other suitably-chosen basis), correlation networks correspond to latent space networks with dependent edge noise in which the vertex-level latent variables encode the basis coefficients. Further, we show that when time series are observed subject to noise, spectral embedding of the resulting noisy correlation network still recovers these true vertex-level latent representations under suitable assumptions. This characterization of embeddings as learning Fourier coefficients appears to be folklore in the signal processing community in the context of principal component analysis, but is, to the best of our knowledge, new to the statistical network analysis literature. 1 Introduction Networks have emerged as crucial data sources in scientific disciplines including neuroscience ( 57 ; 65 ) , economics ( 17 ; 63 ) , microbiomics ( 20 ; 29 ) and sociology ( 34 ; 76 ) to name but a few. As a result, a handful of workhorse statistical network models have emerged. For example, the stochastic blockmodel ( 27 ; 2 , SBM;) posits that each vertex belongs to one of d communities, and the probability that two vertices form an edge is fully determined by their community memberships, with edges generated independently conditional on community memberships. In recent years, the SBM has been extended in a variety of ways ( 33 ; 4 ; 55 ; 23 ; 22 ; 72 ; 2 ; 31 , see, e.g.,) . For example, the degree-corrected SBM ( 33 ) modifies the SBM to give each vertex a “popularity” parameter, so that vertices from the same community may exhibit distinct behaviors in their propensity to form edges. Models such as the random dot product graph ( 70 ; 5 ; 54 , RDPG;) , graph root distribution ( 37 ) , Hoff-style models ( 26 ) , and the graphon ( 43 ; 61 ) further extend this idea, modeling network structure as driven by latent vertex-level vectors. All of these models and their attendant estimation procedures rely on the assumption that edges are generated independently conditional on latent vertex-level structure. In many applications, these edge independence assumptions are grossly violated. Most notably, weighted networks are often derived from correlations between time series: a time series or other sequence is associated to each vertex, and edge weights are given by the correlations between these sequences. In these correlation networks , edge independence assumptions clearly fail to hold: the same time series appears in all edge weights incident upon a given vertex. As an example, consider connectomic networks ( 57 ) , in which vertices correspond to brain regions, and edge weights encode the strength of interaction between brain regions. These interaction strengths are typically measured by correlations between blood oxygen levels in these brain regions ( 47 ; 30 ) . Thus, many connectomic networks are weighted (or are binarized versions of weighted networks; see 35 ; 48 , and citations therein) , with edges given by correlations between noisily-measured underlying signals from different brain regions. As another example, consider affinity matrices, which encode networks whose vertices are stocks or other assets, and edges describe similarities of those assets ( 19 ; 28 ; 18 ) , usually measured by correlation across some set (e.g., correlation of prices or similarity of internet search activity). As yet another example, in microbiome studies, it is common to construct networks whose vertices correspond to species of microorganisms, and edges capture the correlation of abundance counts across a collection of patients or environments ( 36 ; 7 ; 77 ; 6 ) . In all of these example settings, the networks under study have weighted edges, with weights given by correlations between sequences. For a given vertex, all edges incident on that vertex are based on the same sequence’s correlations with all other observed sequences. For example, in connectomic networks, the blood oxygen levels measured at brain region i are used to compute the edge weights between region i and all other brain regions. The result is that edges in this network are clearly not independent, even after conditioning on any obvious choice of latent structure. Despite this gap between model assumptions and reality, independent-edge latent variable models have been applied to these and related application domains with clear success. The apparent consensus in the network analysis community is that this violation of independence assumptions is not a concern. The goal of the present work is to put this folklore on firm ground by studying the properties of these correlation networks. In particular, we focus here on the behavior of embeddings of correlation networks. Embeddings, whereby vertices of a network are represented in a low-dimensional Euclidean space ( 58 ; 59 ; 62 ; 24 ) , are widely deployed for analysis and visualization of network data. Embedding methods, by and large, bring with them implicit modeling assumptions. For example, the adjacency spectral embedding ( 58 , ASE;) implicitly assumes that the observed symmetric adjacency matrix \mathbf{A}\in\mathbb{R}^{n\times n} can be written as a low-rank matrix subject to noise, \mathbf{A}={\mathbf{X^{\star}}}{\mathbf{X^{\star}}}^{\top}+\mathbf{E}, (1) where the rows of {\mathbf{X^{\star}}}\in\mathbb{R}^{n\times d} encode “latent positions” of the n vertices, and the matrix \mathbf{E}\in\mathbb{R}^{n\times n} has mean-zero entries independent (up to symmetry) given {\mathbf{X^{\star}}} . Similar ideas appear in, for example, 54 ; 38 ; 37 ; 39 ; 21 . See 5 for discussion of the RDPG, the model that motivates the ASE and related spectral embeddings. More generally, embeddings arise naturally in community detection as an input to k -means or other clustering methods to recover community memberships in the stochastic blockmodel ( 44 ; 53 ; 45 ; 52 ; 46 ) . In light of the conditional independence assumptions on \mathbf{E} , applying spectral embedding methods to correlation matrices violates what are otherwise standard, albeit unrealistic, network modeling assumptions. Nonetheless, embeddings are used to analyze correlation or covariance networks throughout the sciences. The “folklore” belief is that edge dependence can be safely ignored because the correlations are approximately independent. An additional concern relates to the fact that network embeddings in edge-independent models can typically estimate a sensibly-defined latent structure. For example, under suitable assumptions on \mathbf{E} in Equation ( 1 ), the ASE of \mathbf{A} recovers {\mathbf{X^{\star}}} , up to orthogonal non-identifiability (see Section 2 for further discussion). When one applies the ASE or some other embedding method to a correlation network, there is no obvious analogue of the low-rank structure {\mathbf{X^{\star}}} in Equation ( 1 ) for the embedding to estimate, nor is there an obvious interpretation for such a structure. This work sets out to address these concerns and put the “folklore” on firm ground. First, we show that correlation networks have a natural analogue of the low-dimensional latent structure {\mathbf{X^{\star}}} in Equation ( 1 ), which encode the Fourier coefficients of the time series (or the coefficients under any other suitably-chosen transform). This is made formal in Lemmas 1 and 2 below. Second, we show in Theorem 1 that when a collection of time series is observed subject to noise, the ASE applied to the correlation matrix recovers this low-dimensional encoding of the Fourier coefficients, up to non-identifiability constraints, at a rate that is qualitatively similar to those established for other related estimation problems. Notation. For a positive integer n , we write [n]=\{1,2,\dots,n\} . Throughout, matrices and vectors are bolded, while scalars are in normal typeface. For a matrix \mathbf{B} , we use \mathbf{B}^{\top} to denote its transpose and \mathbf{B}^{\text{H}} to denote its conjugate transpose. We write \|\mathbf{B}\| for the spectral norm of \mathbf{B} , \|\mathbf{B}\|_{F} for its Frobenius norm, and \|\mathbf{B}\|_{{2,\infty}} for its ({2,\infty}) -norm, i.e., the maximum Euclidean norm of the rows of \mathbf{B} . We denote the identity matrix by \mathbf{I} , the matrix of all ones by \mathbf{J} and the matrix of all zeros by {\bf 0} , with dimensions made clear by context. We use \mathrm{i}\mkern 1.0mu to denote the imaginary unit. Note that we use the similar looking i in places, but only ever as a summation index or subscript, so there is no risk of confusion. For a complex number z\in\mathbb{C} , we use \Re(z) and \Im(z) to denote its real and imaginary components, respectively, so that z=\Re(z)+\mathrm{i}\mkern 1.0mu\Im(z) . We write \bar{z} for the complex conjugate of z . 2 Model Setup and Main Results Consider a collection of n length- T discrete-time time series, so that for each i\in[n] and t\in[T] , Z^{\star}_{i,t}\in\mathbb{R} is the value of the i -th time series at time t\in[T] . We write {\mathbf{Z}^{\star}_{i}}\in\mathbb{R}^{T} to denote the i -th time series, written as a T -dimensional vector. We model these time series as subject to noise, so that our observed data takes the form {\mathbf{Z}_{i}}={\mathbf{Z}^{\star}_{i}}+\mathbf{N}_{i} for each i\in[n] , where \mathbf{N}_{i}\in\mathbb{R}^{T} is a vector of measurement noise (precise noise assumptions are given in Section 2.2 ). For example, in our neuroimaging example discussed in Section 1 , the true signal {\mathbf{Z}^{\star}_{i}} corresponds to underlying brain activity in the brain region indexed by i\in[n] , while the noisy signal {\mathbf{Z}_{i}} corresponds to the measured blood oxygen level in brain region i . Collecting the true signals {\mathbf{Z}^{\star}_{i}} into the rows of {\mathbf{Z^{\star}}}\in\mathbb{R}^{n\times T} and forming matrices \mathbf{Z}\in\mathbb{R}^{n\times T} and \mathbf{N}\in\mathbb{R}^{n\times T} analogously, we may write \mathbf{Z}={\mathbf{Z^{\star}}}+\mathbf{N}\in\mathbb{R}^{n\times T}. (2) In the applications discussed in Section 1 , it is common to form a weighted network with vertices i\in[n] by assigning edge weights via correlation among these time series. That is, ignoring measurement noise for now, we form a weighted network with adjacency matrix \mathbf{R^{\star}}=\left[R^{\star}_{i,j}\right]=\left[\operatorname{Corr}({\mathbf{Z}^{\star}_{i}},{\mathbf{Z}^{\star}_{j}})\right]=\left[\frac{\operatorname{Cov}({\mathbf{Z}^{\star}_{i}},{\mathbf{Z}^{\star}_{j}})}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}\right]\in\mathbb{R}^{n\times n}, (3) where {\sigma^{\star}_{i}}^{2}=\frac{1}{T}\sum_{t=1}^{T}\left(Z^{\star}_{i,t}-\frac{1}{T}\sum_{s=1}^{T}Z^{\star}_{i,s}\right)^{2}. (4) We refer to a network with adjacency matrix as in Equation ( 3 ) as a correlation network , in light of the fact that its edge weights encode correlations between time series. Remark 1 . On first glance, it is tempting to interpret {\sigma^{\star}_{i}}^{2} as simply a variance. However, since we interpret {\mathbf{Z}^{\star}_{i}}\in\mathbb{R}^{T} as encoding network structure, rather than random noise, {\sigma^{\star}_{i}}^{2} is better viewed as a measure of signal strength. Indeed, {\sigma^{\star}_{i}}^{2} corresponds precisely to the power in the signal {\mathbf{Z}^{\star}_{i}} after centering about its time-average ( 50 ) . Defining the “centering” matrix \mathbf{M}=\frac{1}{T}\left(\mathbf{I}-\mathbf{J}\right)\in\mathbb{R}^{T\times T}, (5) we may write \mathbf{R^{\star}} as a matrix product, \mathbf{R^{\star}}=\frac{1}{T}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}, (6) where \mathbf{\Sigma^{\star}}=\operatorname{diag}\left({\sigma^{\star}_{1}}^{2},{\sigma^{\star}_{2}}^{2},\dots,{\sigma^{\star}_{n}}^{2}\right)\in\mathbb{R}^{n\times n}. (7) Of course, in practice, we do not observe the true signals in {\mathbf{Z^{\star}}} , but instead observe \mathbf{Z} as in Equation ( 2 ), and our resulting correlation network has an adjacency matrix given by \mathbf{R}=\frac{1}{T}\boldsymbol{\Sigma}^{-1/2}\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}\boldsymbol{\Sigma}^{-1/2}, (8) where \boldsymbol{\Sigma}=\operatorname{diag}\left(\sigma_{1}^{2},\sigma_{2}^{2},\dots,\sigma_{n}^{2}\right)\in\mathbb{R}^{n\times n} (9) is the diagonal matrix of (noisy) variances, \sigma_{i}^{2}=\frac{1}{T}\sum_{t=1}^{T}\left(Z_{i,t}-\frac{1}{T}\sum_{s=1}^{T}Z_{i,s}\right)^{2}. (10) In the applications in Section 1 , one observes a collection of time series and forms a correlation network with adjacency matrix as in Equation ( 3 ) or ( 8 ). We then apply an embedding method to this network. Our goal in the present work is to address two questions: 1. Is there a sense in which \mathbf{R^{\star}} is driven by a low-dimensional latent structure, analogous to the role played by {\mathbf{X^{\star}}} in Equation ( 1 )? 2. Under what conditions does an embedding of the noisy correlation network \mathbf{R} in Equation ( 8 ) recover this latent structure, and at what rate? Below, we address both of these questions as they pertain to the adjacency spectral embedding. Given a network with adjacency matrix \mathbf{A}\in\mathbb{R}^{n\times n} , the d -dimensional ASE produces an n -by- d matrix whose rows encode d -dimensional embeddings of the vertices: \operatorname{ASE}(\mathbf{A},d)=\mathbf{V}~|\mathbf{D}|^{1/2}\in\mathbb{R}^{n\times d} (11) where \mathbf{D}\in\mathbb{R}^{d\times d} is the diagonal matrix of the d largest-magnitude eigenvalues of \mathbf{A} and \mathbf{V}\in\mathbb{R}^{n\times d} contains as its columns the corresponding eigenvectors. Under a variety of network models, \mathbf{A} can be expressed as in Equation ( 1 ), and {\mathbf{X^{\star}}} is naturally viewed as a low-rank structure underlying the observed network. As such, {\mathbf{X^{\star}}} is a natural target for estimation and inference. Of course, estimation of {\mathbf{X^{\star}}} is possible only up to right-multiplication by an orthogonal matrix, since for any \mathbf{Q}\in\mathbb{O}_{d} , {\mathbf{X^{\star}}}{\mathbf{X^{\star}}}^{\top}={\mathbf{X^{\star}}}\mathbf{Q}({\mathbf{X^{\star}}}\mathbf{Q})^{\top}. Under suitable assumptions on {\mathbf{X^{\star}}} and \mathbf{E} in Equation ( 1 ) ( 45 ; 5 ; 54 ; 53 ; 39 ; 21 , see, e.g.,) , \min_{\mathbf{Q}\in\mathbb{O}_{d}}\left\|\operatorname{ASE}(\mathbf{A},d)\mathbf{Q}-{\mathbf{X^{\star}}}\right\|_{{2,\infty}}=o_{P}\left(1\right). That is, the ASE recovers the latent structure {\mathbf{X^{\star}}} , up to orthogonal non-identifiability, uniformly over the vertices i\in[n] . Our goal is to identify a low-dimensional structure analogous to {\mathbf{X^{\star}}} that gives rise to \mathbf{R^{\star}} , and to show that the ASE of \mathbf{R^{\star}} recovers this structure (up to non-identifiability constraints) under suitable assumptions. We focus here on the ASE owing to its comparative simplicity, but we anticipate that much of our analysis can be extended to other spectral embeddings and related methods ( 62 ; 49 ; 54 ; 24 ; 42 ; 56 ; 73 , e.g.,) . 2.1 Latent structure in correlation networks To understand the low-dimensional structure encoded in \mathbf{R^{\star}} , we will aim to mimic the construction in Equation ( 1 ) and write \mathbf{R^{\star}}={\mathbf{X^{\star}}}{\mathbf{X^{\star}}}^{\top} for some choice of {\mathbf{X^{\star}}}\in\mathbb{R}^{n\times d} , where d\ll n . Toward this end, define {\mathbf{\widetilde{Z}^{\star}}}=\frac{1}{\sqrt{T}}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}\in\mathbb{R}^{n\times T}, (12) noting that the i -th row of this matrix, {\mathbf{\widetilde{Z}}^{\star}_{i}}\in\mathbb{R}^{T} , corresponds to a centered, normalized version of the i -th observed time series {\mathbf{Z}^{\star}_{i}}\in\mathbb{R}^{T} . Since \mathbf{M} is idempotent, we may rewrite Equation ( 3 ) as \mathbf{R^{\star}}=\left(\frac{1}{\sqrt{T}}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}\right)\left(\frac{1}{\sqrt{T}}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}\right)^{\top}={\mathbf{\widetilde{Z}^{\star}}}{\mathbf{\widetilde{Z}^{\star\top}}}. (13) Applying the discrete Fourier transform, we can express, for any i\in[n] and t\in[T] , \widetilde{Z}^{\star}_{i,t}=\frac{1}{T}\sum_{k=1}^{T}F^{\star}_{i,k}\exp\left\{\frac{2\pi\mathrm{i}\mkern 1.0mu}{T}(k-1)(t-1)\right\}, (14) where F^{\star}_{i,k} denotes the (k-1) -th Fourier coefficient of the i -th standardized time series {\mathbf{\widetilde{Z}}^{\star}_{i}} for each k\in[T] . That is, F^{\star}_{i,k}=\sum_{t=1}^{T}\widetilde{Z}^{\star}_{i,t}\exp\left\{\frac{-2\pi\mathrm{i}\mkern 1.0mu}{T}(k-1)(t-1)\right\}. (15) We note that under this convention, F^{\star}_{i,1} is the Fourier coefficient of {\mathbf{\widetilde{Z}^{\star}}}_{i} associated to frequency zero, which is T times its mean. Since {\mathbf{\widetilde{Z}^{\star}}}_{i} is standardized, we have F^{\star}_{i,1}=0 . Denote by \mathbf{\Omega}\in\mathbb{C}^{T\times T} the (unitary) inverse discrete Fourier transform matrix, with entries \Omega_{k,t}=\frac{1}{\sqrt{T}}\exp\left\{\frac{2\pi\mathrm{i}\mkern 1.0mu}{T}(k-1)(t-1)\right\},~k,t\in[T]. Examining Equation ( 14 ), we see that we can express {\mathbf{\widetilde{Z}^{\star}}} as {\mathbf{\widetilde{Z}^{\star}}}=\frac{1}{\sqrt{T}}\mathbf{F^{\star}}\mathbf{\Omega}. Substituting this into Equation ( 6 ), \mathbf{R^{\star}}=\frac{1}{\sqrt{T}}\mathbf{F^{\star}}\mathbf{\Omega}\left(\frac{1}{\sqrt{T}}\mathbf{F^{\star}}\mathbf{\Omega}\right)^{\top}=\frac{1}{\sqrt{T}}\mathbf{F^{\star}}\mathbf{\Omega}\left(\frac{1}{\sqrt{T}}\mathbf{F^{\star}}\mathbf{\Omega}\right)^{\text{H}}=\frac{1}{T}\mathbf{F^{\star}}\mathbf{F^{\star}}^{\text{H}}, (16) where the second equality follows from the fact that {\mathbf{Z^{\star}}} is real and the last equality follows from the fact that \mathbf{\Omega} is unitary. Since \mathbf{F^{\star}} encodes the Fourier transforms of real sequences, basic symmetry properties of the discrete Fourier transform ( 50 , Chapter 8) , along with the fact that the rows of {\mathbf{\widetilde{Z}^{\star}}} are centered, imply \overline{F^{\star}_{i,k}}=\begin{cases}F^{\star}_{i,k}=0&\mbox{ if }k=1\\ F^{\star}_{i,T-k+2}&\mbox{ if }k\in\{2,3,\dots,T\}.\end{cases} (17) Define a matrix \mathbf{K}\in\mathbb{R}^{T\times T} according to K_{s,t}=\begin{cases}1&\mbox{ if }s=t=1\\ 1&\mbox{ if }s+t=T+2\\ 0&\mbox{ otherwise, }\end{cases} (18) and observe that by Equation ( 17 ), \mathbf{F^{\star}}^{\text{H}}=\left(\mathbf{F^{\star}}\mathbf{K}\right)^{\top} . Substituting this into Equation ( 16 ) and observing that \mathbf{K} is a permutation matrix and thus has a square root \mathbf{K}^{1/2}\in\mathbb{C}^{T\times T} , \mathbf{R^{\star}}=\frac{1}{T}\mathbf{F^{\star}}\mathbf{K}^{1/2}\left(\mathbf{F^{\star}}\mathbf{K}^{1/2}\right)^{\top}, (19) Basic properties of the Fourier transform yield the following result. A detailed proof is given in Appendix A . Lemma 1 . If the matrix {\mathbf{Z^{\star}}} has all real entries, then so does the matrix \mathbf{F^{\star}}\mathbf{K}^{1/2} , and these entries are given by \left[\mathbf{F^{\star}}\mathbf{K}^{1/2}\right]_{i,k}=\Re\left(F^{\star}_{i,k}\right)-\Im\left(F^{\star}_{i,k}\right)~~~i\in[n],k\in[T]. (20) In light of Lemma 1 and Equation ( 19 ), we see that \mathbf{R^{\star}} is indeed encoded by a low-rank structure if \mathbf{F^{\star}}\mathbf{K}^{1/2} is low rank. Suppose that there exist at most d_{0} non-zero columns of \mathbf{F^{\star}} . That is, suppose that there exists a collection of d_{0} Fourier basis elements whose span contains all of the rows in {\mathbf{\widetilde{Z}^{\star}}} . Equations ( 17 ) and ( 20 ) imply the existence of \mathbf{W}\in\mathbb{O}_{T} such that the i -th row of \mathbf{F^{\star}}\mathbf{K}^{1/2}\mathbf{W} encodes, up to scaling, the real and imaginary parts of the Fourier coefficients of {\mathbf{\widetilde{Z}^{\star}}}_{i} , and \mathbf{F^{\star}}\mathbf{K}^{1/2}\mathbf{W} has at most 2d_{0} non-zero columns. It follows that \mathbf{R^{\star}} has rank d\leq 2d_{0} , since from Equation ( 19 ), we have \mathbf{R^{\star}}=\frac{1}{T}\mathbf{F^{\star}}\mathbf{K}^{1/2}\left(\mathbf{F^{\star}}\mathbf{K}^{1/2}\mathbf{W}\right)^{\top}=\frac{1}{T}\mathbf{F^{\star}}\mathbf{K}^{1/2}\mathbf{W}\left(\mathbf{F^{\star}}\mathbf{K}^{1/2}\mathbf{W}\right)^{\top}. Thus, we may further write \mathbf{R^{\star}}={\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}{\mathbf{U^{\star}}}^{\top}, (21) where {\mathbf{\Lambda}^{\star}}=\operatorname{diag}({\lambda^{\star}_{1}},{\lambda^{\star}_{2}},\dots,{\lambda^{\star}_{d}}) contains the d\leq 2d_{0} non-zero eigenvalues of \mathbf{R^{\star}} on its diagonal and {\mathbf{U^{\star}}}\in\mathbb{R}^{n\times d} has the d corresponding orthonormal eigenvectors as its columns. It follows that we may define {\mathbf{X^{\star}}}={\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{1/2}\in\mathbb{R}^{n\times d} (22) to be the “population embedding” of our (centered, scaled) time series data {\mathbf{\widetilde{Z}^{\star}}}\in\mathbb{R}^{n\times T} based on the correlation matrix \mathbf{R^{\star}} , analogous to the low-rank matrix in Equation ( 1 ). Since {\mathbf{X^{\star}}}{\mathbf{X^{\star}}}^{\top}={\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}{\mathbf{U^{\star}}}^{\top}=\mathbf{R^{\star}}={\mathbf{\widetilde{Z}^{\star}}}{\mathbf{\widetilde{Z}^{\star\top}}}=\left(\frac{1}{\sqrt{T}}\mathbf{F^{\star}}\mathbf{K}^{1/2}\right)\left(\frac{1}{\sqrt{T}}\mathbf{F^{\star}}\mathbf{K}^{1/2}\right)^{\top} and all entries of \mathbf{F^{\star}}\mathbf{K}^{1/2} are real, there must exist \mathbf{\widetilde{W}}\in\mathbb{O}_{T} such that \begin{bmatrix}{\mathbf{X^{\star}}}&{\bf 0}\end{bmatrix}=\frac{1}{\sqrt{T}}\mathbf{F^{\star}}\mathbf{K}^{1/2}\mathbf{\widetilde{W}}. We have shown the following. Lemma 2 . If the standardized time series in the rows of {\mathbf{\widetilde{Z}^{\star}}}\in\mathbb{R}^{n\times T} can be represented in a d_{0} -dimensional Fourier basis, then there exists a d\leq 2d_{0} and \mathbf{\widetilde{W}}\in\mathbb{O}_{T} such that \begin{bmatrix}\operatorname{ASE}(\mathbf{R^{\star}},d)&{\bf 0}\end{bmatrix}=\frac{1}{\sqrt{T}}\mathbf{F^{\star}}\mathbf{K}^{1/2}\mathbf{\widetilde{W}}. That is, the d -dimensional ASE of \mathbf{R^{\star}} corresponds precisely to the Fourier representation of the signals in {\mathbf{\widetilde{Z}^{\star}}} , up to orthogonal non-identifiability. Said another way, Lemma 2 states that the Fourier coefficients of the signals in {\mathbf{\widetilde{Z}^{\star}}} correspond to a low-rank latent representation of the vertices in the correlation network \mathbf{R^{\star}} . Remark 2 . While our discussion above focused on representing the standardized time series {\mathbf{\widetilde{Z}^{\star}}} in the Fourier basis, the same basic argument applies to any basis that we might consider (e.g., wavelets or the discrete cosine transform). While we restrict our attention to the Fourier basis for the sake of concreteness, our results and analysis are largely agnostic to this choice of basis. Key to our results is that there exist some unitary matrix \mathbf{\Omega} such that the rows of {\mathbf{\widetilde{Z}^{\star}}}\mathbf{\Omega}^{\text{H}} encode the observed time series in the chosen basis. 2.2 Recovering low-dimensional latent structure Lemmas 1 and 2 indicate that the noiseless correlation network \mathbf{R^{\star}} has a low-rank latent structure given by Fourier transforms of the time series in the rows of {\mathbf{Z^{\star}}} . We turn our attention now to the matter of recovering this latent structure from \mathbf{R} , the noisy version of \mathbf{R^{\star}} , as given in Equation ( 8 ). Following previous work on network embeddings ( 58 ; 38 ; 62 ; 40 ) , we wish to study the adjacency spectral embedding of the observed correlation matrix \mathbf{R} as defined in Equation ( 8 ). In particular, write \mathbf{R}=\mathbf{U}\boldsymbol{\Lambda}\mathbf{U}^{\top}+\mathbf{U}_{\perp}\boldsymbol{\Lambda}_{\perp}\mathbf{U}_{\perp}^{\top}, (23) where \boldsymbol{\Lambda}=\operatorname{diag}({\lambda_{1}},{\lambda_{2}},\dots,{\lambda_{d}}) contains the d largest eigenvalues of \mathbf{R} , \mathbf{U}\in\mathbb{R}^{n\times d} contains the corresponding orthonormal eigenvectors as its columns, and \boldsymbol{\Lambda}_{\perp}=\operatorname{diag}({\lambda_{d+1}},{\lambda_{d+2}},\dots,{\lambda_{n}}) and \mathbf{U}_{\perp}\in\mathbb{R}^{n\times(n-d)} are defined analogously for the trailing n-d eigenvalues. The d -dimensional ASE of the noisy correlation network is then given by {\mathbf{\hat{X}}}=\operatorname{ASE}(\mathbf{R},d)=\mathbf{U}\boldsymbol{\Lambda}^{1/2}\in\mathbb{R}^{n\times d}, (24) and we may hope that if the noise is not too severe, {\mathbf{\hat{X}}} recovers {\mathbf{X^{\star}}} in Equation ( 22 ) up to non-identifiability. Of course, in practice, the dimension d is unknown and must be selected from data. This model selection task is well-studied in the networks literature under latent space models with conditionally independent edges ( 14 ; 41 ; 25 ; 13 ; 60 , see, e.g.,) . Myriad selection techniques for PCA and related dimensionality reduction methods have also been developed ( 32 ; 75 ) , which may be applicable as well. We leave a thorough exploration of this matter for future work, but Appendix B includes an experimental investigation of the effects of model misspecification under the setting of Equation ( 2 ). Whether the ASE of \mathbf{R} recovers the latent structure {\mathbf{X^{\star}}} depend, of course, on the behavior of the noise \mathbf{N}=\mathbf{Z}-{\mathbf{Z^{\star}}} . We assume comparatively little about the specific structure of \mathbf{N} beyond row-wise independence. In particular, we allow for dependence within the rows of \mathbf{N} , subject to tail decay conditions. Assumption 1 . The rows \mathbf{N}_{1},\mathbf{N}_{2},\dots,\mathbf{N}_{n}\in\mathbb{R}^{T} of \mathbf{N} are mean-zero and independent, with n=O(T). (25) For each i\in[n] , \mathbf{N}_{i} is a \nu_{i} -subgaussian random vector ( 64 , Chapter 3) . That is, for any fixed unit vector \mathbf{u}\in\mathbb{R}^{T} , the random variable \mathbf{u}^{\top}\mathbf{N}_{i} is a \nu_{i} -subgaussian random variable ( 9 ; 64 ) . Viewing the subgaussian parameter \nu_{i} as a proxy for the variance in the i -th row of \mathbf{N} , our results require that the noise not overwhelm the signal carried in {\mathbf{Z^{\star}}} . In particular, the threshold for this rate of growth is set by the spectrum of the signal matrix \mathbf{R^{\star}} . Defining \gamma=\min_{i\in[n]}\frac{{\sigma^{\star}_{i}}^{2}}{\nu_{i}}, (26) our results require that the condition number \kappa={\lambda^{\star}_{1}}/{\lambda^{\star}_{d}} of \mathbf{R^{\star}} not grow too quickly with respect to \gamma and that the smallest signal eigenvalue {\lambda^{\star}_{d}} is bounded away from zero. Assumption 2 . The signal eigenvalues {\lambda^{\star}_{1}}\geq{\lambda^{\star}_{2}}\geq\cdots\geq{\lambda^{\star}_{d}}>0 of the true correlation matrix \mathbf{R^{\star}} are such that {\lambda^{\star}_{d}}=\Omega_{P}\left(1\right) (27) and the condition number \kappa={\lambda^{\star}_{1}}/{\lambda^{\star}_{d}} is such that \kappa=o(T) and \frac{\kappa\log T}{\gamma}=o(1). (28) The following theorem characterizes how well the embeddings of \mathbf{R} recover their population counterparts. The result serves as a correlation network analogue of ({2,\infty}) -norm estimation error bounds found in, for example, 58 ; 45 ; 54 ; 62 ; 39 , which rely on edge independence assumptions. A proof of this theorem can be found in Appendix F . Theorem 1 . Under Assumptions 1 and 2 , let {\mathbf{X^{\star}}}\in\mathbb{R}^{n\times d} be as in Equation ( 22 ), and let {\mathbf{\hat{X}}}=\operatorname{ASE}(\mathbf{R},d) . There exists \mathbf{Q}\in\mathbb{O}_{d} such that \displaystyle\min_{\mathbf{Q}\in\mathbb{O}_{d}}\left\|{\mathbf{\hat{X}}}-{\mathbf{X^{\star}}}\mathbf{Q}\right\|_{{2,\infty}}\leq C\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}\left[1+\kappa\left(\kappa\sqrt{\frac{\log n}{\gamma}}+\sqrt{\frac{1}{T}}\right)\|\mathbf{R^{\star}}\|_{{2,\infty}}\right] It is instructive to consider the upper bound in Theorem 1 when \kappa and d are both bounded above by constants. Using basic properties of the ({2,\infty}) -norm ( 11 ; 12 ) and the fact that {\mathbf{\widetilde{Z}^{\star}}} has standardized rows, we have \|\mathbf{R^{\star}}\|_{{2,\infty}}=\|{\mathbf{\widetilde{Z}^{\star}}}{\mathbf{\widetilde{Z}^{\star\top}}}\|_{{2,\infty}}\leq\|{\mathbf{\widetilde{Z}^{\star}}}\|_{{2,\infty}}\|{\mathbf{\Lambda}^{\star}}^{1/2}\|=\sqrt{{\lambda^{\star}_{1}}}. It follows that when \max\{\kappa,d\}=O(1) , we can rewrite the bound in Theorem 1 as \min_{\mathbf{Q}\in\mathbb{O}_{d}}\left\|{\mathbf{\hat{X}}}-{\mathbf{X^{\star}}}\mathbf{Q}\right\|_{{2,\infty}}\leq C\sqrt{\frac{\log T}{\gamma}}\left(\sqrt{\frac{1}{{\lambda^{\star}_{d}}}}+\sqrt{\frac{\log n}{\gamma}}+\sqrt{\frac{1}{T}}\right), (29) and we see that consistent estimation occurs under Assumption 2 . Among previous work, most similar to the setting of Theorem 1 is the literature on heteroscedastic PCA, which considers a setting similar to Equation ( 2 ), where one observes \mathbf{Z}={\mathbf{Z^{\star}}}+\mathbf{N} , and aims to recover the left singular vectors of {\mathbf{Z^{\star}}} . When the entries within a row of \mathbf{N} differ in their variances, as we allow in the present work, “vanilla” PCA fails due to bias in the diagonal entries of the empirical covariance matrix. Methods for correcting this bias include zeroing out the diagonal of the empirical covariance before computing its eigenvectors ( 1 ; 10 ) and iterative approaches that seek to impute or otherwise debias these diagonal entries ( 71 ; 74 ) . Importantly, the estimation problem considered in Theorem 1 differs from heteroscedastic PCA (and many other related subspace estimation tasks) in its target of inference: we aim to estimate the scaled leading eigenvectors of \mathbf{R^{\star}} (i.e., {\mathbf{X^{\star}}} in Theorem 1 ; see also Lemma 2 ), while PCA aims to estimate the left singular vectors of {\mathbf{Z^{\star}}} . Given this difference, Theorem 1 cannot be directly compared to results for heteroscedastic PCA. Nonetheless, it is informative to compare our assumptions with those used in this related literature. 71 consider the setting where the rows of {\mathbf{Z^{\star}}} are drawn i.i.d. from a distribution with rank- d covariance matrix \mathbf{\Delta}_{0}\in\mathbb{R}^{T\times T} , and one observes \mathbf{Z}={\mathbf{Z^{\star}}}+\mathbf{N} where the rows of \mathbf{N} are i.i.d. mean zero with independent entries, but these entries are allowed to differ in their variances. The goal is to estimate the signal eigenvectors of \mathbf{\Delta}_{0} . 10 ; 69 ; 74 consider a similar setting, with relaxed assumptions on the noise \mathbf{N} more in line with the tail bounds of our Assumption 1 , but still requiring entrywise independence in \mathbf{N} . We note that 10 ; 69 allow for missing entries in \mathbf{Z} , which we do not consider here, though we expect that low-rank imputation methods as used in 41 can be applied in the setting of Theorem 1 . Most similar in spirit to our assumptions are 1 ; 3 , both of which allow for dependence within rows of \mathbf{N} and impose tail bounds similar to our Assumption 1 . Both also require SNR-related assumptions that are superficially similar to our Assumption 2 , but are in fact largely incomparable. Assumption 2 concerns \gamma , which measures how the signal present in individual rows of {\mathbf{Z^{\star}}} , as measured by {\sigma^{\star}_{i}}^{2} , compare to the variance-like quantity \nu_{i} , which describes the tail behavior of the i -th row of the noise matrix \mathbf{N} . In contrast, 1 ; 3 measure SNR by comparing {\lambda^{\star}_{d}} to the variance of the noise (i.e., \nu_{1},\nu_{2},\dots,\nu_{n} in our notation). 1 and 3 also require assumptions on the coherence of the left singular vectors of {\mathbf{Z^{\star}}} . It is interesting to note that Theorem 1 requires no analogous assumptions on the eigenstructure of \mathbf{R^{\star}} . Nor does it require assumptions on how the covariances within the rows of \mathbf{N} interact with the signal eigenstructure, as required in 3 . 3 Experiments We turn now to a brief exploration of our theoretical results. In particular, we are interested in verifying the estimation bound in Theorem 1 , which predicts the rate at which \operatorname{ASE}(\mathbf{R},d) should recover {\mathbf{X^{\star}}} once we account for orthogonal non-identifiability. When evaluating an estimate \mathbf{Y}\in\mathbb{R}^{n\times d} of {\mathbf{X^{\star}}} , we will take advantage of the fact that, per Lemma 2 , {\mathbf{X^{\star}}} and {\mathbf{\widetilde{Z}^{\star}}} are equal up to orthogonal rotation, and assess estimation error by \min_{\mathbf{W}\in\mathbb{O}_{T}}\left\|\begin{bmatrix}\mathbf{Y}&{\bf 0}\end{bmatrix}\mathbf{W}-{\mathbf{\widetilde{Z}^{\star}}}\right\|_{{2,\infty}}, (30) where we have appended T-d columns of zeros to \mathbf{Y} so that it is conformal with {\mathbf{\widetilde{Z}^{\star}}} . In what follows, we compare the ASE against two baseline methods for estimating {\mathbf{\widetilde{Z}^{\star}}} . The first is based on applying d -dimensional PCA to the centered matrix of time series \mathbf{Z}\mathbf{M}\in\mathbb{R}^{n\times T} followed by standardizing the rows. Note that we perform a scaled PCA, with the eigenvectors scaled by the square roots of the eigenvalues. In essence, this PCA-based estimate reverses the steps of the ASE by applying eigenvalue truncation before performing row normalization. Our second comparison is with a naïve method, whereby we simply use \mathbf{\widetilde{Z}}=\frac{1}{\sqrt{T}}\boldsymbol{\Sigma}^{-1/2}\mathbf{Z}\mathbf{M}\in\mathbb{R}^{n\times T}, as our estimate of {\mathbf{\widetilde{Z}^{\star}}} . While such an estimate fails to yield dimensionality reduction the way that the ASE or other PCA-based methods might, it serves as a baseline comparison to indicate whether an estimator is successfully removing noise from the observed signals. 3.1 Effect of variance on estimation We begin by examining how the behavior of the rows of \mathbf{N} influence estimation accuracy. For a given number of vertices n , number of time series T , and a number of signal frequencies d_{0}0 , \Pr\left[\left\|\mathbf{N}_{i}\right\|\geq\tau\right]\leq C_{0}\exp\left\{T-\frac{C_{1}\tau^{2}}{\nu_{i}}\right\}, for suitably-chosen positive constants C_{0} and C_{1} . Taking \tau=\sqrt{C\nu_{i}T\log n} for C>0 suitably large and rearranging, \Pr\left[\frac{\left\|\mathbf{N}_{i}\right\|^{2}}{\nu_{i}}\geq CT\log n\right]\leq Cn^{-3}. A union bound over all i\in[n] then yields that with probability at least 1-O(n^{-2}) , \max_{i\in[n]}\frac{\left\|\mathbf{N}_{i}\right\|^{2}}{\nu_{i}}\leq CT\log n, as we set out to show. ∎ Lemma 4 . Suppose that Assumption 1 holds. Then with high probability, it holds uniformly over all i\in[n] that \left|\sigma_{i}^{2}-{\sigma^{\star}_{i}}^{2}\right|\leq C\nu_{i}\log n+\sqrt{\frac{{\sigma^{\star}_{i}}^{2}\nu_{i}\log n}{T}} Proof. For i\in[n] , recalling {\sigma^{\star}_{i}}^{2} and \sigma_{i}^{2} from Equations ( 4 ) and ( 10 ), respectively, \sigma_{i}^{2}-{\sigma^{\star}_{i}}^{2}=\frac{1}{T}\sum_{t=1}^{T}N_{i,t}^{2}+\frac{2}{T}\sum_{t=1}^{T}N_{i,t}Z^{\star}_{i,t}-\left(\frac{1}{T}\sum_{t=1}^{T}N_{i,t}\right)^{2}-\frac{2\mu_{i}}{T}\sum_{t=1}^{T}N_{i,t}. Rearranging and recalling the centering matrix \mathbf{M} from Equation ( 5 ), \sigma_{i}^{2}-{\sigma^{\star}_{i}}^{2}=\frac{1}{T}\|\mathbf{M}\mathbf{N}_{i}\|^{2}+\frac{2}{T}\mathbf{N}_{i}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{i}}. (37) By assumption, each \mathbf{N}_{i} is a \nu_{i} -subgaussian random vector. Noting that \|\mathbf{M}{\mathbf{Z}^{\star}_{i}}\|^{2}=T{\sigma^{\star}_{i}}^{2} , standard concentration inequalities [ 64 ] yield that with high probability, \left|\frac{2}{T}\mathbf{N}_{i}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{i}}\right|\leq\frac{C}{\sqrt{T}}\sqrt{\nu_{i}{\sigma^{\star}_{i}}^{2}\log n}~\text{ for all }~i\in[n]. Taking absolute values in Equation ( 37 ) and applying the above bound, \left|\sigma_{i}^{2}-{\sigma^{\star}_{i}}^{2}\right|\leq\frac{1}{T}\|\mathbf{M}\mathbf{N}_{i}\|^{2}+\frac{C}{\sqrt{T}}\sqrt{\nu_{i}{\sigma^{\star}_{i}}^{2}\log n}~\text{ for all }~i\in[n]. (38) Applying submultiplicativity followed by Lemma 3 , \max_{i\in[n]}\left\|\mathbf{M}\mathbf{N}_{i}\right\|^{2}\leq\max_{i\in[n]}\left\|\mathbf{N}_{i}\right\|^{2}\leq C\max_{i\in[n]}\nu_{i}T\log n. Applying this bound to Equation ( 38 ), it holds with high probability that \left|\sigma_{i}^{2}-{\sigma^{\star}_{i}}^{2}\right|\leq C\left(\nu_{i}\log n+\sqrt{\frac{{\sigma^{\star}_{i}}^{2}\nu_{i}\log n}{T}}\right)~\text{ for all }~i\in[n], as we set out to show. ∎ Lemma 5 . Suppose that Assumptions 1 and 2 hold. Then with high probability, it holds uniformly over all i\in[n] that \max\left\{\left|\frac{\sigma_{i}}{{\sigma^{\star}_{i}}}-1\right|,\left|\frac{\sigma_{i}}{{\sigma^{\star}_{i}}}-1\right|\right\}\leq C\left(\frac{\log n}{\gamma}+\sqrt{\frac{\log n}{T\gamma}}\right). (39) Further, with high probability, \max_{i\in[n]}\max\left\{\left|\frac{{\sigma^{\star}_{i}}}{\sigma_{i}}\right|,\left|\frac{\sigma_{i}}{{\sigma^{\star}_{i}}}\right|\right\}\leq C. (40) Proof. By Lemma 4 , it holds uniformly over all i\in[n] that \sigma_{i}^{2}\geq{\sigma^{\star}_{i}}^{2}-C\left(\nu_{i}\log n+\sqrt{\frac{{\sigma^{\star}_{i}}^{2}\nu_{i}\log n}{T}}\right)={\sigma^{\star}_{i}}^{2}\left(1-\frac{C\nu_{i}\log n}{{\sigma^{\star}_{i}}^{2}}-C\sqrt{\frac{\nu_{i}}{{\sigma^{\star}_{i}}^{2}}\frac{\log n}{T}}\right). Applying our growth assumption in Equation ( 28 ), it follows that uniformly over i\in[n] , \sigma_{i}^{2}\geq{\sigma^{\star}_{i}}^{2}\left(1-o_{P}\left(1\right)\right). (41) For all i\in[n] , multiplying through by appropriate quantities, we have \frac{\sigma_{i}}{{\sigma^{\star}_{i}}}-1=\frac{\sigma_{i}-{\sigma^{\star}_{i}}}{{\sigma^{\star}_{i}}}=\frac{\sigma_{i}^{2}-{\sigma^{\star}_{i}}^{2}}{{\sigma^{\star}_{i}}\left({\sigma^{\star}_{i}}+\sigma_{i}\right)}. (42) Again using Lemma 4 , \left|\frac{\sigma_{i}}{{\sigma^{\star}_{i}}}-1\right|\leq\frac{C}{{\sigma^{\star}_{i}}\left({\sigma^{\star}_{i}}+\sigma_{i}\right)}\left(\nu_{i}\log n+\sqrt{\frac{{\sigma^{\star}_{i}}^{2}\nu_{i}\log n}{T}}\right). Applying Equation ( 41 ) yields that \left|\frac{\sigma_{i}}{{\sigma^{\star}_{i}}}-1\right|\leq C\left(\frac{\nu_{i}\log n}{{\sigma^{\star}_{i}}^{2}}+\sqrt{\frac{\nu_{i}\log n}{T{\sigma^{\star}_{i}}^{2}}}\right). To see the same bound for {\sigma^{\star}_{i}}/\sigma_{i} , note that \frac{{\sigma^{\star}_{i}}}{\sigma_{i}}-1=\frac{1}{\sigma_{i}/{\sigma^{\star}_{i}}}-1=\left(1-\frac{\sigma_{i}}{{\sigma^{\star}_{i}}}\right)\frac{1}{\sigma_{i}/{\sigma^{\star}_{i}}}. Applying Equation ( 42 ) and using our growth assumption in Equation ( 28 ) yields Equation ( 39 ). Equation ( 40 ) then follows from the growth assumption in Equation ( 28 ). ∎ Lemma 6 . Suppose that Assumptions 1 and 2 hold. Then it holds with high probability that, uniformly over all i,j\in[n] , \left|\frac{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}{\sigma_{i}\sigma_{j}}-1\right|=O_{P}\left(\frac{\log n}{\gamma}+\sqrt{\frac{\log n}{T\gamma}}\right). Proof. We begin by noting that \frac{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}{\sigma_{i}\sigma_{j}}-1=\frac{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}-\sigma_{i}\sigma_{j}}{\sigma_{i}\sigma_{j}}=\frac{({\sigma^{\star}_{i}}-\sigma_{i}){\sigma^{\star}_{j}}+\sigma_{i}({\sigma^{\star}_{j}}-\sigma_{j})}{\sigma_{i}\sigma_{j}}. Multiplying through by appropriate quantities, \frac{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}{\sigma_{i}\sigma_{j}}-1=\frac{({\sigma^{\star}_{i}}^{2}-\sigma_{i}^{2}){\sigma^{\star}_{j}}}{\sigma_{i}\sigma_{j}({\sigma^{\star}_{i}}+\sigma_{i})}+\frac{(\sigma_{j}^{2}-{\sigma^{\star}_{j}}^{2})}{\sigma_{j}({\sigma^{\star}_{j}}+\sigma_{j})}. Applying the triangle inequality followed by Equation ( 40 ) from Lemma 5 , it holds uniformly over all i,j\in[n] that \left|\frac{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}{\sigma_{i}\sigma_{j}}-1\right|\leq\frac{C\left|{\sigma^{\star}_{i}}^{2}-\sigma_{i}^{2}\right|}{\sigma_{i}({\sigma^{\star}_{i}}+\sigma_{i})}+\frac{\left|\sigma_{j}^{2}-{\sigma^{\star}_{j}}^{2}\right|}{\sigma_{j}({\sigma^{\star}_{j}}+\sigma_{j})}. (43) For ease of notation, for each i\in[n] define B_{i}=\nu_{i}\log n+\sqrt{\frac{{\sigma^{\star}_{i}}^{2}\nu_{i}\log n}{T}}. (44) By Lemma 4 , uniformly over all i\in[n] , \left|\sigma_{i}^{2}-{\sigma^{\star}_{i}}^{2}\right|\leq CB_{i}. Thus, applying this bound to Equation ( 43 ), it holds uniformly over all i,j\in[n] that \left|\frac{\sigma_{i}\sigma_{j}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}-1\right|\leq\frac{CB_{i}}{\sqrt{{\sigma^{\star}_{i}}^{2}-CB_{i}}\left({\sigma^{\star}_{i}}+\sqrt{{\sigma^{\star}_{i}}^{2}-CB_{i}}\right)}+\frac{CB_{j}}{\sqrt{{\sigma^{\star}_{j}}^{2}-CB_{j}}\left({\sigma^{\star}_{j}}+\sqrt{{\sigma^{\star}_{j}}^{2}-CB_{j}}\right)}. (45) By our assumption in Equation ( 28 ), \max_{i\in[n]}\frac{B_{i}}{{\sigma^{\star}_{i}}^{2}}=o_{P}\left(1\right). Applying this fact to Equation ( 45 ), it holds with high probability that, \left|\frac{\sigma_{i}\sigma_{j}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}-1\right|\leq\frac{CB_{i}}{{\sigma^{\star}_{i}}^{2}}+\frac{CB_{j}}{{\sigma^{\star}_{j}}^{2}}~\text{ for all }~i,j\in[n]. Taking a maximum over all i,j\in[n] and recalling the definition of B_{i} from Equation ( 44 ), \left|\frac{\sigma_{i}\sigma_{j}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}-1\right|\leq C\left[\max_{i\in[n]}\frac{\nu_{i}\log n}{{\sigma^{\star}_{i}}^{2}}+\max_{i\in[n]}\sqrt{\frac{\nu_{i}\log n}{T{\sigma^{\star}_{i}}^{2}}}\right]. Recalling the definition of \gamma from Equation ( 26 ) completes the proof. ∎ Appendix D Controlling Matrix Norms Here we collect technical results related to controlling the variation of \mathbf{R} about \mathbf{R^{\star}} . These are used in Appendix E below, as well as in our proof of Theorem 1 given in Appendix F . Lemma 7 . With \mathbf{R^{\star}} as in Equation ( 3 ), \sqrt{n}\leq\|\mathbf{R^{\star}}\|_{F}\leq n . Further, the leading eigenvalue of \mathbf{R^{\star}} obeys 1\leq{\lambda^{\star}_{1}}\leq n . Proof. The lower-bound on \|\mathbf{R^{\star}}\|_{F} follows from the fact that all diagonal entries of \mathbf{R^{\star}} are 1 by construction. The upper bound follows from the fact that all entries of \mathbf{R^{\star}} are bounded between -1 and 1 . The lower-bound on {\lambda^{\star}_{1}} follows from the fact that for any standard basis vector \mathbf{e}_{i} , i\in[n] , we have \mathbf{e}_{i}^{\top}\mathbf{R^{\star}}\mathbf{e}_{i}=1 (again because \mathbf{R^{\star}} has all diagonal entries equal to one). The upper bound follows from the fact that {\lambda^{\star}_{1}}\leq\|\mathbf{R^{\star}}\|_{F}\leq n . ∎ Lemma 8 . Suppose that Assumptions 1 and 2 hold. Then with high probability, it holds uniformly over i\in[n] that \|\mathbf{N}_{i}\|^{2}\leq C\nu_{i}T\log T. (46) Further, \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\right\|_{{2,\infty}}=O_{P}\left(\sqrt{\frac{T\log T}{\gamma}}\right). (47) Proof. Note that for a fixed basis vector \mathbf{e}_{t}\in\mathbb{R}^{T} , since \mathbf{N}_{i} is a subgaussian random vector by assumption, it holds with high probability that \left|\mathbf{e}_{t}^{\top}\mathbf{N}_{i}\right|\leq\sqrt{C\nu_{i}\log T}. Choosing the constant C>0 large enough, we can ensure that this bound holds uniformly over all t\in[T] , so that \|\mathbf{N}_{i}\|^{2}=\sum_{t=1}^{T}\left(\mathbf{e}_{t}^{\top}\mathbf{N}_{i}\right)^{2}\leq CT\nu_{i}\log T. Again choosing C>0 suitably large and recalling our assumption in Equation ( 25 ), a union bound ensures that this holds for all i\in[n] with high probability, establishing Equation ( 46 ). Noting that \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\right\|_{{2,\infty}}=\max_{i\in[n]}\frac{\|\mathbf{N}_{i}\|}{{\sigma^{\star}_{i}}}, Equation ( 47 ) follows immediately, once we recall the definition of \gamma from Equation ( 26 ). ∎ Lemma 9 . Suppose that Assumption 1 holds. \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\right\|=O_{P}\left(\sqrt{T\frac{\log n}{\gamma}}\right). Proof. Let \mathbf{u}\in\mathbb{R}^{n} and \mathbf{v}\in\mathbb{R}^{T} be fixed unit-norm vectors. \mathbf{u}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{v}=\sum_{i=1}^{n}\frac{u_{i}\mathbf{N}_{i}^{\top}\mathbf{v}}{{\sigma^{\star}_{i}}}. Since the rows of \mathbf{N} are independent subgaussian vectors by Assumption 1 , standard concentration inequalities [ 64 ] yield that with high probability, \left|\sum_{i=1}^{n}\frac{u_{i}\mathbf{N}_{i}^{\top}\mathbf{v}}{{\sigma^{\star}_{i}}}\right|\leq C\sqrt{\sum_{i=1}^{n}u_{i}^{2}\frac{\nu_{i}}{{\sigma^{\star}_{i}}^{2}}v_{i}^{2}\log n}\leq C\sqrt{\frac{\log n}{\gamma}}. Modifying the concentration inequality to encompass a union bound over \varepsilon -nets covering the unit spheres in \mathbb{R}^{n} and \mathbb{R}^{T} [ 64 ] , it holds with high probability that \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\right\|=O_{P}\left(\sqrt{\frac{(n+T)\log n}{\gamma}}\right). Using our assumption that n=O(T) completes the proof. ∎ Lemma 10 . Suppose that Assumption 1 holds. Then \max\left\{\left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{N}\right\|,\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\right\|\right\}=O_{P}\left(\sqrt{\frac{T\log n}{\gamma}}\right) Proof. Multiplying through by appropriate quantities and using submultiplicativity, \left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{N}\right\|\leq\left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}\right\|\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\right\|. Applying Lemma 5 , \left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{N}\right\|\leq C\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\right\|, and Lemma 9 completes the proof. ∎ Lemma 11 . Suppose that Assumption 1 holds. Then \left\|\mathbf{R}-\mathbf{R^{\star}}\right\|_{F}=o_{P}\left(\|\mathbf{R^{\star}}\|_{F}\right). Proof. For i,j\in[n] , we have \displaystyle\left(\mathbf{R}-\mathbf{R^{\star}}\right)_{i,j} \displaystyle=\frac{\mathbf{Z}_{i}^{\top}\mathbf{M}\mathbf{Z}_{j}}{T\sigma_{i}\sigma_{j}}-\frac{{\mathbf{Z}^{\star}_{i}}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{j}}}{T{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}} \displaystyle=\frac{1}{T\sigma_{i}\sigma_{j}}\left(\mathbf{Z}_{i}^{\top}\mathbf{M}\mathbf{Z}_{j}-{\mathbf{Z}^{\star}_{i}}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{j}}\right)+\frac{{\mathbf{Z}^{\star}_{i}}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{j}}}{T{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}\left(\frac{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}{\sigma_{i}\sigma_{j}}-1\right). Squaring and summing over all i,j\in[n] , noting that \mathbf{R} and \mathbf{R^{\star}} have all diagonal entries equal to 1 by construction, \displaystyle\left\|\mathbf{R}-\mathbf{R^{\star}}\right\|_{F}^{2} \displaystyle=\frac{1}{T^{2}}\sum_{i=1}^{n}\sum_{j:j\neq i}\left(\frac{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}{\sigma_{i}\sigma_{j}}\right)^{2}\left(\frac{\mathbf{Z}_{i}^{\top}\mathbf{M}\mathbf{Z}_{j}-{\mathbf{Z}^{\star}_{i}}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{j}}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}\right)^{2}+\sum_{i=1}^{n}\sum_{j:j\neq i}\left(\frac{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}{\sigma_{i}\sigma_{j}}-1\right)^{2}{R^{\star}_{i,j}}^{2}. Applying Lemma 6 , \displaystyle\left\|\mathbf{R}-\mathbf{R^{\star}}\right\|_{F}^{2} \displaystyle\leq\frac{C}{T^{2}}\sum_{i=1}^{n}\sum_{j:j\neq i}\left(\frac{\mathbf{Z}_{i}^{\top}\mathbf{M}\mathbf{Z}_{j}-{\mathbf{Z}^{\star}_{i}}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{j}}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}\right)^{2}+\left(\frac{\log n}{\gamma}+\sqrt{\frac{\log n}{T\gamma}}\right)^{2}\left\|\mathbf{R^{\star}}\right\|_{F}^{2}. (48) Recalling that \mathbf{Z}_{i}={\mathbf{Z}^{\star}_{i}}+\mathbf{N}_{i} , we have \left|\frac{\mathbf{Z}_{i}^{\top}\mathbf{M}\mathbf{Z}_{j}-{\mathbf{Z}^{\star}_{i}}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{j}}}{\sqrt{T}{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}\right|\leq\frac{\left|\mathbf{N}_{i}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{j}}\right|+\left|{\mathbf{Z}^{\star}_{i}}^{\top}\mathbf{M}\mathbf{N}_{j}\right|+\left|\mathbf{N}_{i}^{\top}\mathbf{M}\mathbf{N}_{j}\right|}{\sqrt{T}{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}, and standard subgaussian concentration inequalities and Lemma 8 yield that with high probability, uniformly over all i,j\in[n] distinct, \left|\frac{\mathbf{Z}_{i}^{\top}\mathbf{M}\mathbf{Z}_{j}-{\mathbf{Z}^{\star}_{i}}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{j}}}{\sqrt{T}{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}\right|\leq C\sqrt{\frac{\log n}{\gamma}}+\frac{C\sqrt{n\nu_{i}\nu_{j}}\log T}{\sqrt{T}{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}\leq C\sqrt{\frac{\log n}{\gamma}}+C\sqrt{\frac{n}{T}}\frac{\log T}{\gamma}. Applying this to Equation ( 48 ), \displaystyle\left\|\mathbf{R}-\mathbf{R^{\star}}\right\|_{F}^{2} \displaystyle\leq\frac{C}{T}\sum_{i=1}^{n}\sum_{j:j\neq i}\left(\sqrt{\frac{\log n}{\gamma}}+\sqrt{\frac{n}{T}}\frac{\log T}{\gamma}\right)^{2}+\left(\frac{\log n}{\gamma}+\sqrt{\frac{\log T}{T\gamma}}\right)^{2}\left\|\mathbf{R^{\star}}\right\|_{F}^{2} \displaystyle\leq\frac{Cn^{2}}{T}\left(\sqrt{\frac{\log n}{\gamma}}+\sqrt{\frac{n}{T}}\frac{\log T}{\gamma}\right)^{2}+\left(\frac{\log n}{\gamma}+\sqrt{\frac{\log T}{T\gamma}}\right)^{2}\left\|\mathbf{R^{\star}}\right\|_{F}^{2}. Applying the growth assumptions in Equations ( 25 ) and ( 28 ), \displaystyle\left\|\mathbf{R}-\mathbf{R^{\star}}\right\|_{F}^{2}=o_{P}\left(n+\|\mathbf{R^{\star}}\|_{F}^{2}\right). Considering the diagonal entries of \mathbf{R^{\star}} yields the trivial lower bound \|\mathbf{R^{\star}}\|_{F}^{2}\geq n , which completes the proof. ∎ Lemma 12 . Suppose Assumption 1 holds. Then \left\|\mathbf{R}-\mathbf{R^{\star}}\right\|_{{2,\infty}}=o_{P}\left(\|\mathbf{R^{\star}}\|_{{2,\infty}}\right). Proof. The proof follows the same argument as Lemma 11 , summing along a row of \mathbf{R}-\mathbf{R^{\star}} rather than summing over all entries. ∎ Lemma 13 . Suppose that Assumption 1 holds. Then \left\|\mathbf{R}-\mathbf{R^{\star}}\right\|\leq C\left(\frac{{\lambda^{\star}_{1}}\log n}{\gamma}+\sqrt{\frac{{\lambda^{\star}_{1}}\log n}{\gamma}}\right). Proof. Expanding the definitions of \mathbf{R} and \mathbf{R^{\star}} from Equations ( 8 ) and ( 3 ), respectively, and applying the triangle inequality, \displaystyle\left\|\mathbf{R}-\mathbf{R^{\star}}\right\| \displaystyle\leq\left\|\frac{1}{T}\boldsymbol{\Sigma}^{-1/2}\left(\mathbf{N}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}+{\mathbf{Z^{\star}}}\mathbf{M}\mathbf{N}^{\top}+\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\right)\boldsymbol{\Sigma}^{-1/2}\right\| (49) \displaystyle+\left\|\frac{\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}}{T}\right\|. Adding and subtracting appropriate quantities and applying the triangle inequality, \displaystyle\left\|\frac{\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\boldsymbol{\Sigma}^{-1/2}\!-\!\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}}{T}\right\| \displaystyle\leq\left\|\frac{1}{T}\left(\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}\!\right)\!{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\boldsymbol{\Sigma}^{-1/2}\right\|+\left\|\frac{1}{T}\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\left(\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}\right)\right\|. Factoring out \mathbf{\Sigma^{\star}}^{-1/2} , recalling the definition of \mathbf{R^{\star}} from Equation ( 3 ) and using submultiplicativity of the norm, \displaystyle\left\|\frac{1}{T}\!\left(\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\boldsymbol{\Sigma}^{-1/2}\!-\!\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right)\right\| \displaystyle\leq\left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}-\mathbf{I}\right\|\left\|\mathbf{R^{\star}}\right\|\left\|\mathbf{\Sigma^{\star}}^{1/2}\boldsymbol{\Sigma}^{-1/2}\right\| \displaystyle+\left\|\mathbf{R^{\star}}\right\|\left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}-\mathbf{I}\right\|. Applying Lemma 5 , it holds with high probability that \left\|\frac{\boldsymbol{\Sigma}^{-1/2}ZMZ^{\top}\boldsymbol{\Sigma}^{-1/2}\!-\!\boldsymbol{\Sigma}^{-1/2}ZMZ^{\top}\boldsymbol{\Sigma}^{-1/2}}{T}\right\|\leq C{\lambda^{\star}_{1}}\left(\frac{\log n}{\gamma}+\sqrt{\frac{\log n}{T\gamma}}\right). (50) Applying the triangle inequality and basic properties of the norm, \displaystyle\left\|\frac{1}{T}\boldsymbol{\Sigma}^{-1/2}\!\left(\!\mathbf{N}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\!+\!{\mathbf{Z^{\star}}}\mathbf{M}\mathbf{N}^{\top}\!+\!\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\!\right)\!\boldsymbol{\Sigma}^{-1/2}\right\| \displaystyle\leq\frac{2}{T}\left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{N}\right\|\left\|\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}\right\| (51) \displaystyle+\frac{1}{T}\left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{N}\right\|^{2}~\left\|\mathbf{M}\right\|. Using the fact that \mathbf{M} is a projection and applying Lemma 10 , \frac{1}{T}\left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{N}\right\|^{2}~\left\|\mathbf{M}\right\|\leq\frac{C\log n}{\gamma}. Again using Lemma 10 , \frac{1}{T}\left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{N}\right\|\left\|\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}\right\|\leq\frac{C\log n}{\sqrt{T\gamma}}\left\|\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}\right\|\leq C\sqrt{\frac{{\lambda^{\star}_{1}}\log n}{\gamma}}, where the second inequality follows from the definition of \mathbf{R^{\star}} . Applying the above two displays to Equation ( 51 ), \left\|\frac{1}{T}\boldsymbol{\Sigma}^{-1/2}\!\left(\!\mathbf{N}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\!\!+\!{\mathbf{Z^{\star}}}\mathbf{M}\mathbf{N}^{\top}\!\!+\!\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\!\right)\!\boldsymbol{\Sigma}^{-1/2}\right\|\!\leq C\sqrt{\frac{\log n}{\gamma}}\!\!\left(\!\sqrt{{\lambda^{\star}_{1}}}+\!\sqrt{\frac{\log n}{\gamma}}\right)\leq\!C\!\sqrt{\frac{{\lambda^{\star}_{1}}\log n}{\gamma}}, where the second inequality follows from the assumptions in Equations ( 28 ) and ( 27 ), along with the trivial bound {\lambda^{\star}_{d}}\leq{\lambda^{\star}_{1}} . Applying this and Equation ( 50 ) to Equation ( 49 ), \left\|\mathbf{R}-\mathbf{R^{\star}}\right\|\leq C{\lambda^{\star}_{1}}\left(\frac{\log n}{\gamma}+\sqrt{\frac{\log n}{T\gamma}}\right)+C\sqrt{\frac{{\lambda^{\star}_{1}}\log n}{\gamma}}. Collecting terms, using Lemma 7 to bound 1\leq{\lambda^{\star}_{1}}\leq n , and applying the assumption in Equation ( 25 ), \left\|\mathbf{R}-\mathbf{R^{\star}}\right\|\leq C\left(\frac{{\lambda^{\star}_{1}}\log n}{\gamma}+\sqrt{\frac{{\lambda^{\star}_{1}}\log n}{\gamma}}\right), completing the proof. ∎ Lemma 14 . Suppose that Assumption 1 holds and let \mathbf{B}\in\mathbb{R}^{T\times p} be such that the rows of \mathbf{N} are independent given \mathbf{B} . Then \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{B}\right\|_{{2,\infty}}=O_{P}\left(\|\mathbf{B}\|_{F}\sqrt{\frac{\log(n+p)}{\gamma}}\right). Proof. By definition, \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{B}\right\|_{{2,\infty}}^{2}=\max_{i\in[n]}\frac{1}{{\sigma^{\star}_{i}}^{2}}\sum_{k=1}^{p}\left|\mathbf{N}_{i,\cdot}^{\top}\mathbf{B}_{\cdot,k}\right|^{2}. (52) By standard concentration inequalities, it holds with high probability that, for all i\in[n] and k\in[p] , \left|\mathbf{N}_{i,\cdot}^{\top}\mathbf{B}_{\cdot,k}\right|\leq C\sqrt{\nu_{i}\log(n+p)}. It follows that \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{B}\right\|_{{2,\infty}}^{2}\leq C\max_{i\in[n]}\frac{\nu_{i}\log(n+p)}{{\sigma^{\star}_{i}}^{2}}\sum_{k=1}^{n}\left\|\mathbf{B}_{\cdot,k}\right\|^{2}. Applying this to Equation ( 52 ), taking square roots and recalling the definition of \gamma from Equation ( 26 ) completes the proof. ∎ Lemma 15 . Suppose that Assumption 1 holds. Then \left\|{\mathbf{U^{\star}}}^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}\right\|_{F}\leq Cd\left\|\mathbf{R^{\star}}\right\|_{F}\left(\frac{\log T}{\gamma}+\sqrt{\frac{\log T}{T\gamma}}\right). Proof. Recalling the definitions of \mathbf{R} and \mathbf{R^{\star}} from Equations ( 8 ) and ( 3 ) and applying the triangle inequality, \displaystyle\left\|{\mathbf{U^{\star}}}^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}\right\|_{F} \displaystyle\leq\frac{1}{T}\left\|{\mathbf{U^{\star}}}^{\top}\left(\boldsymbol{\Sigma}^{-1/2}\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right){\mathbf{U^{\star}}}\right\|_{F} (53) \displaystyle+\frac{1}{T}\left\|{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\left(\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}-{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\right)\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right\|_{F}. For k,\ell\in[d] , \displaystyle\frac{1}{T} \displaystyle\left[{\mathbf{U^{\star}}}^{\top}\left(\boldsymbol{\Sigma}^{-1/2}\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right){\mathbf{U^{\star}}}\right]_{k,\ell} \displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{n}\mathbf{R}_{i,j}\left(\frac{\sigma_{i}\sigma_{j}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}-1\right)U^{\star}_{i,k}{\mathbf{U^{\star}}}{j,\ell}, and the Cauchy-Schwarz inequality implies \displaystyle\left[\frac{1}{T}{\mathbf{U^{\star}}}^{\top}\left(\boldsymbol{\Sigma}^{-1/2}\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right){\mathbf{U^{\star}}}\right]_{k,\ell}^{2} \displaystyle\leq\left\|\mathbf{R}\right\|_{F}^{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\left(\frac{\sigma_{i}\sigma_{j}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}-1\right)^{2}{U^{\star}_{i,k}}^{2}{U^{\star}_{j,\ell}}^{2}\leq C\left\|\mathbf{R}\right\|_{F}^{2}\max_{i,j\in[n]}\left(\frac{\sigma_{i}\sigma_{j}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}-1\right)^{2}, where the second inequality follows from the fact that {\mathbf{U^{\star}}} has orthonormal columns. Applying Lemma 6 , summing over k,\ell\in[d] and taking square roots, \displaystyle\frac{1}{T} \displaystyle\left\|{\mathbf{U^{\star}}}^{\top}\left(\boldsymbol{\Sigma}^{-1/2}\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right){\mathbf{U^{\star}}}\right\|_{F} \displaystyle\leq Cd\left\|\mathbf{R}\right\|_{F}\left(\frac{\log n}{\gamma}+\sqrt{\frac{\log n}{T\gamma}}\right). Applying Lemma 11 , \displaystyle\frac{1}{T} \displaystyle\left\|{\mathbf{U^{\star}}}^{\top}\left(\boldsymbol{\Sigma}^{-1/2}\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right){\mathbf{U^{\star}}}\right\|_{F} (54) \displaystyle\leq Cd\left\|\mathbf{R^{\star}}\right\|_{F}\left(\frac{\log n}{\gamma}+\sqrt{\frac{\log n}{T\gamma}}\right). Again fixing k,\ell\in[d] and expanding the matrix-vector products, \displaystyle\frac{1}{T}\left[{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{k,\ell} \displaystyle=\frac{1}{T}\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{\mathbf{N}_{i}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{j}}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}{U^{\star}_{ik}}{U^{\star}_{j\ell}} \displaystyle=\frac{1}{\sqrt{T}}\sum_{i=1}^{n}\frac{{U^{\star}_{ik}}\mathbf{N}_{i}^{\top}}{{\sigma^{\star}_{i}}}\sum_{j=1}^{n}\frac{{U^{\star}_{j\ell}}\mathbf{M}{\mathbf{Z}^{\star}_{j}}}{\sqrt{T}{\sigma^{\star}_{j}}}. Since the rows of \mathbf{N} are independent by assumption, standard concentration inequalities yield \displaystyle\left|\frac{1}{T}\left[{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{k,\ell}\right| \displaystyle\leq\frac{1}{\sqrt{T}}\sqrt{\sum_{i=1}^{n}\frac{{U^{\star}_{ik}}^{2}\nu_{i}\log n}{{\sigma^{\star}_{i}}^{2}}}\left\|\sum_{j=1}^{n}\frac{\mathbf{M}{\mathbf{Z}^{\star}_{j}}{U^{\star}_{j\ell}}}{\sqrt{T}{\sigma^{\star}_{j}}}\right\| \displaystyle\leq\frac{1}{\sqrt{T}}\sqrt{\frac{\log n}{\gamma}}\sqrt{\sum_{j=1}^{n}\left\|\frac{\mathbf{M}{\mathbf{Z}^{\star}_{j}}}{\sqrt{T}{\sigma^{\star}_{j}}}\right\|^{2}}, where the second inequality follows from the triangle and Cauchy-Schwarz inequalities. Since \|\mathbf{M}{\mathbf{Z}^{\star}_{j}}/\sqrt{T}{\sigma^{\star}_{j}}\|=1 for all j\in[n] , \left|\frac{1}{T}\left[{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{k,\ell}\right|\leq\sqrt{\frac{n}{T}\frac{\log n}{\gamma}}. Squaring, summing over k,\ell\in[d] , and taking square roots, \displaystyle\left\|\frac{1}{T}{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right\|_{F}\leq Cd\sqrt{\frac{n\log n}{T\gamma}}. (55) Once more fixing k,\ell\in[d] and expanding, \left[\frac{1}{T}{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{k,\ell}=\sum_{i=1}^{n}\frac{\mathbf{N}_{i}^{\top}\mathbf{M}\mathbf{N}_{i}U^{\star}_{i,k}U^{\star}_{i,\ell}}{T{\sigma^{\star}_{i}}^{2}}+\sum_{i=1}^{n}\sum_{j:j\neq i}\frac{\mathbf{N}_{i}^{\top}\mathbf{M}\mathbf{N}_{j}U^{\star}_{i,k}U^{\star}_{j,\ell}}{T{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}. Applying Lemma 8 , \left|\left[\frac{1}{T}{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{k,\ell}\right|\leq\frac{C\log T}{\gamma}\sum_{i=1}^{n}|U^{\star}_{i,k}U^{\star}_{i,\ell}|+\left|\sum_{i=1}^{n}\sum_{j:j\neq i}\frac{\mathbf{N}_{i}^{\top}\mathbf{M}\mathbf{N}_{j}U^{\star}_{i,k}U^{\star}_{j,\ell}}{T{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}\right|. Applying the Cauchy-Schwarz and triangle inequalities, \left|\left[\frac{1}{T}{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{k,\ell}\right|\leq\frac{C\log T}{\gamma}+\sum_{i=1}^{n}\left|\frac{U^{\star}_{i,k}\mathbf{N}_{i}^{\top}\mathbf{M}}{{\sigma^{\star}_{i}}}\sum_{j:j\neq i}\frac{\mathbf{N}_{j}U^{\star}_{j,\ell}}{T{\sigma^{\star}_{j}}}\right|, (56) Since the rows of \mathbf{N} are independent by assumption, subgaussian concentration inequalities yield that with high probability, for all i\in[n] , \left|\frac{U^{\star}_{i,k}\mathbf{N}_{i}^{\top}\mathbf{M}}{{\sigma^{\star}_{i}}}\sum_{j:j\neq i}\frac{\mathbf{N}_{j}U^{\star}_{j,\ell}}{T{\sigma^{\star}_{j}}}\right|\leq\frac{C}{T}\left\|\frac{U^{\star}_{i,k}\mathbf{N}_{i}^{\top}\mathbf{M}}{{\sigma^{\star}_{i}}}\right\|\sqrt{\sum_{j:j\neq i}\frac{{U^{\star}_{j,\ell}}^{2}\nu_{j}\log T}{{\sigma^{\star}_{j}}^{2}}}\leq\frac{C}{T}\left\|\frac{U^{\star}_{i,k}\mathbf{N}_{i}^{\top}\mathbf{M}}{{\sigma^{\star}_{i}}}\right\|\sqrt{\frac{\log T}{\gamma}}. Applying this to Equation ( 56 ) and using the Cauchy-Schwarz inequality along with the fact that \mathbf{M} is a projection, \left|\left[\frac{1}{T}{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{k,\ell}\right|\leq\frac{C\log T}{\gamma}+\frac{C}{T}\sqrt{\frac{\log T}{\gamma}}\sqrt{\sum_{i=1}^{n}\frac{\|\mathbf{N}_{i}\|^{2}}{{\sigma^{\star}_{i}}^{2}}}. Again using Lemma 8 , \left|\left[\frac{1}{T}{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{k,\ell}\right|\leq\frac{C\log T}{\gamma}+\frac{C}{T}\sqrt{\frac{\log T}{\gamma}}\sqrt{\sum_{i=1}^{n}\frac{T\nu_{i}\log T}{{\sigma^{\star}_{i}}^{2}}}\leq\frac{C\log T}{\gamma}. Squaring and summing over all k,\ell\in[d] , \left\|\frac{1}{T}{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right\|_{F}\leq\frac{Cd\log T}{\gamma}. (57) Recalling \mathbf{Z}={\mathbf{Z^{\star}}}+\mathbf{N} and applying the triangle inequality and Equations ( 55 ) and ( 57 ), \frac{1}{T}\left\|{\mathbf{U^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\left(\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}-{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\right)\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right\|_{F}\leq Cd\left(\sqrt{\frac{n\log T}{T\gamma}}+\frac{\log T}{\gamma}\right). Applying this and Equation ( 54 ) to Equation ( 53 ), \left\|{\mathbf{U^{\star}}}^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}\right\|_{F}\leq Cd\left\|\mathbf{R^{\star}}\right\|_{F}\left(\frac{\log T}{\gamma}+\sqrt{\frac{\log T}{T\gamma}}\right)+Cd\left(\frac{\log T}{\gamma}+\sqrt{\frac{n\log T}{T\gamma}}\right). Collecting terms and applying Lemma 7 completes the proof. ∎ Lemma 16 . Suppose that Assumptions 1 and 2 hold. Then \left\|\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq C\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}\left[1+\left(\sqrt{\frac{\log n}{\gamma}}+\sqrt{\frac{1}{T}}\right)\|\mathbf{R^{\star}}\|_{{2,\infty}}\right], Proof. Recalling the definitions of \mathbf{R} and \mathbf{R^{\star}} from Equations ( 8 ) and ( 3 ), respectively, and applying the triangle inequality, \displaystyle\left\|\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} (58) \displaystyle\leq\frac{1}{T}\left\|\boldsymbol{\Sigma}^{-1/2}\left(\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}-{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\right)\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} \displaystyle+\frac{1}{T}\left\|\left(\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}. Recalling from Equation ( 2 ) that \mathbf{Z}={\mathbf{Z^{\star}}}+\mathbf{N} applying the triangle inequality, and using basic properties of the ({2,\infty}) -norm with Lemma 5 , \displaystyle\frac{1}{T}\left\|\boldsymbol{\Sigma}^{-1/2}\left(\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}-{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\right)\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} (59) \displaystyle\leq\frac{C}{T}\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} \displaystyle+\frac{C}{T}\left\|\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} \displaystyle+\frac{C}{T}\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}. For ease of notation, recall {\mathbf{\widetilde{Z}^{\star}}} from Equation ( 12 ). We have \displaystyle\frac{1}{T}\!\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}{\mathbf{Z^{\star}}}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\!=\frac{1}{\sqrt{T}}\!\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}{\mathbf{\widetilde{Z}^{\star\top}}}\mathbf{\Sigma^{\star}}^{1/2}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}. (60) Adding and subtracting appropriate quantities and applying the triangle inequality, \displaystyle\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}{\mathbf{\widetilde{Z}^{\star\top}}}\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} (61) \displaystyle\leq\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}{\mathbf{\widetilde{Z}^{\star\top}}}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}+\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}{\mathbf{\widetilde{Z}^{\star\top}}}\left(\mathbf{I}-\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}. Applying Lemma 14 with \mathbf{B}={\mathbf{\widetilde{Z}^{\star\top}}}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2} , \displaystyle\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}{\mathbf{\widetilde{Z}^{\star\top}}}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} \displaystyle\leq C\left\|{\mathbf{\widetilde{Z}^{\star\top}}}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{F}\sqrt{\frac{\log n}{\gamma}}\leq C\sqrt{\frac{d\log n}{\gamma}}, (62) where the second inequality follows from the fact that {\mathbf{\widetilde{Z}^{\star}}}{\mathbf{\widetilde{Z}^{\star\top}}}=\mathbf{R^{\star}}={\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}{\mathbf{U^{\star}}}^{\top}. By basic properties of the ({2,\infty}) -norm, \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}{\mathbf{\widetilde{Z}^{\star\top}}}\left(\mathbf{I}-\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq\frac{1}{\sqrt{{\lambda^{\star}_{d}}}}\left\|\mathbf{\Sigma^{\star}}^{1/2}\mathbf{N}{\mathbf{\widetilde{Z}^{\star\top}}}\right\|_{{2,\infty}}\left\|\mathbf{I}-\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}\right\|. Applying Lemma 14 with \mathbf{B}={\mathbf{\widetilde{Z}^{\star\top}}} , \displaystyle\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}{\mathbf{\widetilde{Z}^{\star\top}}}\left(\mathbf{I}-\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} \displaystyle\leq\frac{C}{\sqrt{\gamma{\lambda^{\star}_{d}}}}\|{\mathbf{\widetilde{Z}^{\star}}}\|_{F}\left\|\mathbf{I}-\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}\right\| \displaystyle\leq C\sqrt{\frac{d{\lambda^{\star}_{1}}\log n}{{\lambda^{\star}_{d}}\gamma}}\left\|\mathbf{I}-\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}\right\|, where the second inequality follows from the fact that the d non-zero singular values of {\mathbf{\widetilde{Z}^{\star}}} are precisely the square roots of the eigenvalues of \mathbf{R^{\star}} . Applying this and Equation ( 62 ) to Equation ( 61 ), \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}{\mathbf{\widetilde{Z}^{\star\top}}}\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq C\sqrt{\frac{d\log n}{\gamma}}\left(1+\kappa\left\|\mathbf{I}-\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}\right\|\right). Applying Lemma 5 and using our assumption in Equation ( 28 ) and our assumption that \kappa=o(T) , \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}{\mathbf{\widetilde{Z}^{\star\top}}}\boldsymbol{\Sigma}^{-1/2}\mathbf{\Sigma^{\star}}^{1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq C\sqrt{\frac{d\log n}{\gamma}}. Applying this to Equation ( 60 ), \frac{1}{T}\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}{\mathbf{Z^{\star}}}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq C\sqrt{\frac{d\log n}{T\gamma}}\leq C\sqrt{\frac{d\log n}{\gamma{\lambda^{\star}_{d}}}}, (63) where we have used the trivial bound {\lambda^{\star}_{d}}\leq{\lambda^{\star}_{1}} followed by Lemma 7 and Equation ( 25 ). By basic properties of the ({2,\infty}) -norm, \frac{1}{T}\left\|\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq\frac{C}{\sqrt{T{\lambda^{\star}_{d}}}}\left\|{\mathbf{\widetilde{Z}^{\star}}}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}\right\|_{{2,\infty}}. (64) Applying the triangle inequality and using basic properties of the ({2,\infty}) -norm, \left\|{\mathbf{\widetilde{Z}^{\star}}}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}\right\|_{{2,\infty}}\leq\left\|{\mathbf{\widetilde{Z}^{\star}}}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right\|_{{2,\infty}}+\left\|{\mathbf{\widetilde{Z}^{\star}}}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right\|_{{2,\infty}}\left\|\mathbf{\Sigma^{\star}}^{1/2}\boldsymbol{\Sigma}^{-1/2}-\mathbf{I}\right\|. (65) Fixing i\in[n] and k\in[d] , \left[{\mathbf{\widetilde{Z}^{\star}}}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{ik}=\sum_{j=1}^{n}\frac{\langle{\mathbf{\widetilde{Z}^{\star}}}_{i\cdot},\mathbf{N}_{j}\rangle U^{\star}_{j,k}}{{\sigma^{\star}_{j}}}. Since the rows of {\mathbf{\widetilde{Z}^{\star}}} are all unit-norm and the rows of \mathbf{N} are subgaussian random vectors, standard concentration inequalities yield that with high probability, it holds for all i\in[n] that \left|\left[{\mathbf{\widetilde{Z}^{\star}}}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{i,k}\right|\leq C\sqrt{\sum_{j=1}^{n}\frac{\nu_{j}{U^{\star}_{j,k}}^{2}\log n}{{\sigma^{\star}_{j}}^{2}}}\leq C\sqrt{\frac{\log n}{\gamma}}. It follows that with high probability, \left\|{\mathbf{\widetilde{Z}^{\star}}}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right\|_{{2,\infty}}=O_{P}\left(\sqrt{\frac{d\log n}{\gamma}}\right). (66) Similarly, \left\|{\mathbf{\widetilde{Z}^{\star}}}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq C\sqrt{\sum_{j=1}^{n}\frac{\nu_{j}\log n}{{\sigma^{\star}_{j}}^{2}}}\leq C\sqrt{\frac{n\log n}{\gamma}}, so that \left\|{\mathbf{\widetilde{Z}^{\star}}}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right\|_{{2,\infty}}\left\|\mathbf{\Sigma^{\star}}^{1/2}\boldsymbol{\Sigma}^{-1/2}-\mathbf{I}\right\|\leq C\sqrt{\frac{n\log n}{\gamma}}\left\|\mathbf{\Sigma^{\star}}^{1/2}\boldsymbol{\Sigma}^{-1/2}-\mathbf{I}\right\|. Applying this and Equation ( 66 ) to Equation ( 65 ), \left\|{\mathbf{\widetilde{Z}^{\star}}}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}\right\|_{{2,\infty}}\leq C\sqrt{\frac{\log n}{\gamma}}\left(\sqrt{d}+\sqrt{n}\left\|\mathbf{\Sigma^{\star}}^{1/2}\boldsymbol{\Sigma}^{-1/2}-\mathbf{I}\right\|\right). Applying this in turn to Equation ( 64 ), \displaystyle\frac{1}{T}\left\|\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} \displaystyle\leq C\sqrt{\frac{\log n}{\gamma{\lambda^{\star}_{d}}}}\left(\sqrt{\frac{d}{T}}+\left\|\mathbf{\Sigma^{\star}}^{1/2}\boldsymbol{\Sigma}^{-1/2}-\mathbf{I}\right\|\right) (67) \displaystyle\leq C\sqrt{\frac{\log n}{\gamma{\lambda^{\star}_{d}}}}, where the second inequality follows from Lemma 5 , Equations ( 28 ) and ( 25 ), and our assumption that \kappa=o(T) . By basic properties of the ({2,\infty}) -norm and Lemma 5 , \frac{1}{T}\left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq\frac{C}{T\sqrt{{\lambda^{\star}_{d}}}}\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}\right\|_{{2,\infty}}. (68) Applying basic properties of the ({2,\infty}) -norm and using the triangle inequality, \displaystyle\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}\right\|_{{2,\infty}} \displaystyle\leq\!\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\!\mathbf{\Sigma^{\star}}^{-1/2}\!\left(\mathbf{\Sigma^{\star}}^{1/2}\boldsymbol{\Sigma}^{-1/2}\!-\!\mathbf{I}\right)\!{\mathbf{U^{\star}}}\right\|_{{2,\infty}} (69) \displaystyle+\!\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right\|_{{2,\infty}}. For i\in[n] and k\in[d] , \left[\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{i,k}=\sum_{j=1}^{n}\frac{\mathbf{N}_{i}^{\top}\mathbf{M}\mathbf{N}_{j}U^{\star}_{j,k}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}=\frac{\mathbf{N}_{i}^{\top}\mathbf{M}\mathbf{N}_{i}U^{\star}_{i,k}}{{\sigma^{\star}_{i}}^{2}}+\sum_{j\neq i}\frac{\mathbf{N}_{i}^{\top}\mathbf{M}\mathbf{N}_{j}U^{\star}_{j,k}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}. (70) Applying Cauchy-Schwarz followed by Lemma 8 , \left|\frac{\mathbf{N}_{i}^{\top}\mathbf{M}\mathbf{N}_{i}U^{\star}_{i,k}}{{\sigma^{\star}_{i}}^{2}}\right|\leq\frac{\|\mathbf{N}_{i}\|^{2}|U^{\star}_{i,k}|}{{\sigma^{\star}_{i}}^{2}}\leq\frac{C\nu_{i}|U^{\star}_{i,k}|T\log T}{{\sigma^{\star}_{i}}^{2}}\leq\frac{CT\log T}{\gamma}. (71) Similarly, noting that the sum on the right-hand side of Equation ( 70 ) is a sum of independent sub-Gaussian random variables, \left|\sum_{j\neq i}\frac{\mathbf{N}_{i}^{\top}\mathbf{M}\mathbf{N}_{j}U^{\star}_{j,k}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}\right|\leq\frac{C\|\mathbf{N}_{i}\|}{{\sigma^{\star}_{i}}}\sqrt{\sum_{j\neq i}\frac{\nu_{j}{U^{\star}_{j,k}}^{2}}{{\sigma^{\star}_{j}}^{2}}}\leq\frac{C\|\mathbf{N}_{i}\|}{\sqrt{{\sigma^{\star}_{i}}^{2}\gamma}}. Again using Lemma 8 , \left|\sum_{j\neq i}\frac{\mathbf{N}_{i}^{\top}\mathbf{M}\mathbf{N}_{j}U^{\star}_{j,k}}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}\right|\leq\frac{C\sqrt{\nu_{i}T\log T}}{\sqrt{{\sigma^{\star}_{i}}^{2}\gamma}}\leq\frac{C\sqrt{T}\log T}{\gamma}. Applying this and Equation ( 71 ) to Equation ( 70 ), it holds with high probability that for all i\in[n] and k\in[d] , \left|\left[\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{i,k}\right|\leq\frac{CT\log T}{\gamma}, from which \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right\|_{{2,\infty}}^{2}\leq C\max_{i\in[n]}\sum_{k=1}^{d}\left[\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right]_{i,k}^{2}\leq\frac{CdT^{2}\log^{2}T}{\gamma^{2}}. Taking square roots, \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{U^{\star}}}\right\|_{{2,\infty}}\leq\frac{C\sqrt{d}T\log T}{\gamma}. (72) Applying basic properties of the ({2,\infty}) -norm, \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}^{\top}\left(\mathbf{\Sigma^{\star}}^{-1/2}\boldsymbol{\Sigma}^{1/2}-\mathbf{I}\right){\mathbf{U^{\star}}}\right\|_{{2,\infty}}\leq\left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}^{\top}\right\|_{{2,\infty}}\left\|\mathbf{\Sigma^{\star}}^{-1/2}\boldsymbol{\Sigma}^{1/2}-\mathbf{I}\right\|. Applying Lemma 8 , \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}^{\top}\left(\mathbf{\Sigma^{\star}}^{-1/2}\boldsymbol{\Sigma}^{1/2}-\mathbf{I}\right){\mathbf{U^{\star}}}\right\|_{{2,\infty}}\leq C\sqrt{\frac{T\log T}{\gamma}}\left\|\mathbf{\Sigma^{\star}}^{-1/2}\boldsymbol{\Sigma}^{1/2}-\mathbf{I}\right\|. Applying this and Equation ( 72 ) to Equation ( 69 ), \left\|\mathbf{\Sigma^{\star}}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq\sqrt{\frac{dT\log T}{\gamma}}\left(1+\left\|\mathbf{\Sigma^{\star}}^{-1/2}\boldsymbol{\Sigma}^{1/2}-\mathbf{I}\right\|\right). Applying this in turn to Equation ( 68 ), \frac{1}{T}\left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq C\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}\left(1+\left\|\mathbf{\Sigma^{\star}}^{-1/2}\boldsymbol{\Sigma}^{1/2}-\mathbf{I}\right\|\right) and Lemma 5 , along with Equations ( 28 ) and ( 25 ) and our assumption that \kappa=o(T) , yields \frac{1}{T}\left\|\boldsymbol{\Sigma}^{-1/2}\mathbf{N}\mathbf{M}\mathbf{N}^{\top}\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq C\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}. (73) Applying Equations ( 63 ), ( 67 ) and ( 73 ) to Equation ( 59 ), \displaystyle\frac{1}{T}\left\|\boldsymbol{\Sigma}^{-1/2}\left(\mathbf{Z}\mathbf{M}\mathbf{Z}^{\top}-{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\right)\boldsymbol{\Sigma}^{-1/2}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} \displaystyle\leq C\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}. (74) Applying this in turn to Equation ( 58 ), \displaystyle\left\|\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} (75) \displaystyle\leq\frac{1}{T}\left\|\left(\!\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\!\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\!\mathbf{\Sigma^{\star}}^{-1/2}\!\right)\!{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}+C\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}. For i\in[n] and k\in[d] , \displaystyle\frac{1}{T} \displaystyle\left[\left(\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right]_{i,k} \displaystyle=\sum_{j=1}^{n}\left(\frac{1}{\sigma_{i}\sigma_{j}}-\frac{1}{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}\right)\frac{{\mathbf{Z}^{\star}_{i}}^{\top}\mathbf{M}{\mathbf{Z}^{\star}_{j}}U^{\star}_{j,k}}{T\sqrt{{\lambda^{\star}_{k}}}}=\sum_{j=1}^{n}\left(\frac{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}{\sigma_{i}\sigma_{j}}-1\right)\frac{R^{\star}_{i,j}U^{\star}_{j,k}}{\sqrt{{\lambda^{\star}_{k}}}}. Applying the Cauchy-Schwarz inequality, \displaystyle\left[\frac{1}{T}\left(\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right]_{i,k}^{2} \displaystyle\leq\left[\sum_{j=1}^{n}\left(\frac{{\sigma^{\star}_{i}}{\sigma^{\star}_{j}}}{\sigma_{i}\sigma_{j}}-1\right)^{2}\frac{{U^{\star}_{j,k}}^{2}}{{\lambda^{\star}_{k}}}\right]\left[\sum_{j=1}^{n}{R^{\star}_{i,j}}^{2}\right]\leq\frac{C}{{\lambda^{\star}_{k}}}\left(\frac{\log n}{\gamma}+\sqrt{\frac{\log n}{T\gamma}}\right)^{2}\sum_{j=1}^{n}{R^{\star}_{i,j}}^{2}, where the second inequality follows from Lemma 6 . Summing over k\in[d] , taking a maximum over i\in[n] , and taking square roots, \displaystyle\left\|\frac{1}{T}\left(\boldsymbol{\Sigma}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\boldsymbol{\Sigma}^{-1/2}-\mathbf{\Sigma^{\star}}^{-1/2}{\mathbf{Z^{\star}}}\mathbf{M}{\mathbf{Z^{\star}}}^{\top}\mathbf{\Sigma^{\star}}^{-1/2}\right){\mathbf{U^{\star}}}\right\|_{{2,\infty}} \displaystyle\leq C\sqrt{\frac{d}{{\lambda^{\star}_{d}}}}\left(\frac{\log n}{\gamma}+\sqrt{\frac{\log n}{T\gamma}}\right)\|\mathbf{R^{\star}}\|_{{2,\infty}}. Using Equation ( 25 ) and applying this to Equation ( 75 ), \left\|\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}\left[1+\left(\sqrt{\frac{\log n}{\gamma}}+\sqrt{\frac{1}{T}}\right)\|\mathbf{R^{\star}}\|_{{2,\infty}}\right], completing the proof. ∎ Appendix E Controlling eigenspaces Here we collect results related to alignment of the leading eigenspace of \mathbf{R} with the signal eigenspace of \mathbf{R^{\star}} , to be used in the proof of Theorem 1 in Appendix F . We draw from standard results in subspace geometry [ 16 , 8 , 12 , 11 , see, e.g.,] . As elsewhere in this work, the main technical challenge (and hence the main departure from previous work) lies in the dependence structure in the error \mathbf{R}-\mathbf{R^{\star}} . Lemma 17 . Suppose that Assumption 1 holds. Then \min_{\mathbf{W}\in\mathbb{O}_{d}}\left\|\mathbf{U}\mathbf{W}-{\mathbf{U^{\star}}}\right\|\leq\sqrt{2}\left\|\sin\boldsymbol{\Theta}\right\|\leq C\left(\frac{\kappa\log n}{\gamma}+\sqrt{\frac{\kappa\log n}{\gamma{\lambda^{\star}_{d}}}}\right). (76) Proof. Basic results in subspace geometry [ 11 , 12 ] yield the first inequality in Equation ( 76 ). To establish the second, the Davis-Kahan theorem [ 8 , Theorem VII.3.2] implies \left\|\sin\boldsymbol{\Theta}\right\|\leq\frac{C\left\|\mathbf{R}-\mathbf{R^{\star}}\right\|}{{\lambda^{\star}_{d}}}. Applying Lemma 13 completes the proof. ∎ In order to align the estimated subspace \mathbf{U} to the signal subspace {\mathbf{U^{\star}}} , following 15 , define \mathbf{H}=\mathbf{U}^{\top}{\mathbf{U^{\star}}}\in\mathbb{O}_{d} (77) and the related Procrustes alignment matrix \mathbf{Q}=\operatorname{sgn}\left(\mathbf{H}\right)=\operatorname{sgn}\left(\mathbf{U}^{\top}{\mathbf{U^{\star}}}\right), (78) where, for \mathbf{H}\in\mathbb{R}^{d\times d} with SVD \mathbf{H}=\mathbf{V}_{1}\mathbf{D}\mathbf{V}_{2}^{\top} , \operatorname{sgn}(\mathbf{B})=\mathbf{V}_{1}\mathbf{V}_{2}^{\top} . The following lemma largely follows Lemma 4.15 in 15 . The main change is that we must account for the different error structure in \mathbf{R}-\mathbf{R^{\star}} compared to the independent edges considered in that work. Lemma 18 . Suppose that Assumptions 1 and 2 hold. Let \mathbf{H} and \mathbf{Q} be as in Equations ( 77 ) and ( 78 ), respectively. Then \left\|\mathbf{H}-\mathbf{Q}\right\|\leq\frac{C\kappa\log n}{\gamma}\left[\frac{\kappa\log n}{\gamma}+\frac{1}{{\lambda^{\star}_{d}}}\right] (79) and \left\|\mathbf{H}^{-1}\right\|=O_{P}\left(1\right). (80) Proof. Recall that by definition, \mathbf{H}=\mathbf{U}^{\top}{\mathbf{U^{\star}}} . Let \cos\boldsymbol{\Theta}\in\mathbb{R}^{d\times d} be the diagonal matrix of the cosines of the principal angles between \mathbf{U} and {\mathbf{U^{\star}}} so that the SVD of \mathbf{H} is given by \mathbf{H}=\mathbf{V}_{1}\cos\boldsymbol{\Theta}~\mathbf{V}_{2}^{\top} [ 8 ] . By definition, \mathbf{Q}=\operatorname{sgn}(\mathbf{H})=\mathbf{V}_{1}\mathbf{V}_{2}^{\top}, and it follows that \left\|\mathbf{H}-\mathbf{Q}\right\|\leq\left\|\cos\boldsymbol{\Theta}-\mathbf{I}\right\|\leq\left\|\cos^{2}\boldsymbol{\Theta}-\mathbf{I}\right\|=\left\|\sin^{2}\boldsymbol{\Theta}\right\|. Applying Lemma 17 yields Equation ( 79 ). By Weyl’s inequality, \sigma_{d}(\mathbf{H})\geq\sigma_{d}\left(\mathbf{Q}\right)-\left\|\mathbf{H}-\mathbf{Q}\right\|=1-\left\|\mathbf{H}-\mathbf{Q}\right\|, where we have used the fact that \mathbf{Q}=\mathbf{V}_{1}\mathbf{V}_{2}^{\top} has d singular values all equal to 1 . Applying Equation ( 79 ) along with our growth assumptions in Equations ( 28 ) and ( 27 ) yields Equation ( 80 ). ∎ The following two lemmas serve as analogues of the bounds in Lemma 17 of 46 , adapted to the correlation network setting. Lemma 19 . Suppose that Assumptions 1 and 2 hold. Then, with \mathbf{Q}\in\mathbb{O}_{d} as in Equation ( 78 ). \left\|\boldsymbol{\Lambda}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}\right\|_{F}\leq C\frac{\sqrt{d}\kappa^{2}\log n}{\gamma}\left(\frac{{\lambda^{\star}_{1}}\log n}{\gamma}+1\right)+\left\|\mathbf{R^{\star}}\right\|_{F}\left(\frac{\log T}{\gamma}+\sqrt{\frac{\log T}{T\gamma}}\right). Proof. Adding and subtracting appropriate quantities \displaystyle\boldsymbol{\Lambda}\mathbf{Q} \displaystyle=\boldsymbol{\Lambda}\left(\mathbf{Q}-\mathbf{H}\right)+\boldsymbol{\Lambda}\mathbf{H}=\boldsymbol{\Lambda}\left(\mathbf{Q}-\mathbf{H}\right)+\mathbf{U}^{\top}\mathbf{R}{\mathbf{U^{\star}}}, where the second equality follows from the definition of \mathbf{H} . Adding and subtracting appropriate quantities again, \displaystyle\boldsymbol{\Lambda}\mathbf{Q} \displaystyle=\boldsymbol{\Lambda}\left(\mathbf{Q}-\mathbf{H}\right)+\mathbf{U}^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}+\mathbf{U}^{\top}\mathbf{R^{\star}}{\mathbf{U^{\star}}} (81) \displaystyle=\boldsymbol{\Lambda}\left(\mathbf{Q}-\mathbf{H}\right)+\left(\mathbf{U}-{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\mathbf{U}\right)^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}} \displaystyle+\mathbf{U}^{\top}{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}+\mathbf{U}^{\top}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}, where we have used the fact that \mathbf{R^{\star}}{\mathbf{U^{\star}}}={\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}} . Recalling \mathbf{H}=\mathbf{U}^{\top}{\mathbf{U^{\star}}} and writing \mathbf{U}^{\top}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}=\left(\mathbf{H}-\mathbf{Q}\right){\mathbf{\Lambda}^{\star}}+\mathbf{Q}{\mathbf{\Lambda}^{\star}}, rearranging Equation ( 81 ) yields \displaystyle\boldsymbol{\Lambda}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}} \displaystyle=\boldsymbol{\Lambda}\left(\mathbf{Q}-\mathbf{H}\right)+\left(\mathbf{U}-{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\mathbf{U}\right)^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}} \displaystyle+\mathbf{U}^{\top}{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}+\left(\mathbf{H}-\mathbf{Q}\right){\mathbf{\Lambda}^{\star}}. Applying the triangle inequality and using basic properties of the norm, \displaystyle\left\|\boldsymbol{\Lambda}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}\right\|_{F} \displaystyle\leq\left\|\boldsymbol{\Lambda}\right\|_{F}\left\|\mathbf{Q}-\mathbf{H}\right\|+\left\|\left(\mathbf{U}-{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\mathbf{U}\right)^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}\right\|_{F} \displaystyle+\left\|\mathbf{H}\right\|\left\|{\mathbf{U^{\star}}}^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}\right\|_{F}+\left\|\mathbf{H}-\mathbf{Q}\right\|\left\|{\mathbf{\Lambda}^{\star}}\right\|_{F}. Applying Lemma 13 and the growth bounds in Assumption 2 , \displaystyle\left\|\boldsymbol{\Lambda}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}\right\|_{F} \displaystyle\leq C\left\|{\mathbf{\Lambda}^{\star}}\right\|_{F}\left\|\mathbf{Q}-\mathbf{H}\right\|+\left\|\left(\mathbf{U}-{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\mathbf{U}\right)^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}\right\|_{F} \displaystyle+\left\|\mathbf{H}\right\|\left\|{\mathbf{U^{\star}}}^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}\right\|_{F}. Applying Lemmas 15 and 18 , \displaystyle\left\|\boldsymbol{\Lambda}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}\right\|_{F} \displaystyle\leq\left\|\left(\mathbf{U}-{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\mathbf{U}\right)^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}\right\|_{F} \displaystyle+C\left\|\boldsymbol{\Lambda}\right\|_{F}\left[\left(\frac{\kappa\log n}{\gamma}\right)^{2}+\frac{\kappa\log n}{\gamma{\lambda^{\star}_{d}}}\right]+C\left\|\mathbf{R^{\star}}\right\|_{F}\left(\frac{\log T}{\gamma}+\sqrt{\frac{\log T}{T\gamma}}\right). Again applying Lemma 13 and the growth bounds in Assumption 2 , \displaystyle\left\|\boldsymbol{\Lambda}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}\right\|_{F} \displaystyle\leq\left\|\left(\mathbf{U}-{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\mathbf{U}\right)^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}\right\|_{F} (82) \displaystyle+C\sqrt{d}{\lambda^{\star}_{1}}\left[\left(\frac{\kappa\log n}{\gamma}\right)^{2}+\frac{\kappa\log n}{\gamma{\lambda^{\star}_{d}}}\right]+C\left\|\mathbf{R^{\star}}\right\|_{F}\left(\frac{\log T}{\gamma}+\sqrt{\frac{\log T}{T\gamma}}\right). Applying basic properties of the Frobenius norm followed by Lemmas 13 \displaystyle\left\|\left(\mathbf{U}-{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\mathbf{U}\right)^{\top}\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}\right\|_{F} \displaystyle\leq\left\|\mathbf{U}-{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\mathbf{U}\right\|\left\|\mathbf{R}-\mathbf{R^{\star}}\right\|\left\|{\mathbf{U^{\star}}}\right\|_{F} \displaystyle\leq C\sqrt{d}\left(\frac{{\lambda^{\star}_{1}}\log n}{\gamma}+\sqrt{\frac{{\lambda^{\star}_{1}}\log n}{\gamma}}\right)\left\|\mathbf{U}-{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\mathbf{U}\right\| Noting that the singular values of \mathbf{U}-{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\mathbf{U} are precisely the sines of the principal angles between \mathbf{U} and {\mathbf{U^{\star}}} , Lemma 17 implies that \displaystyle\left\|\left(\mathbf{U}-{\mathbf{U^{\star}}}{\mathbf{U^{\star}}}^{\top}\mathbf{U}\right)^{\!\top}\!\!\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}\right\|_{F} \displaystyle\leq C\sqrt{d}\left(\frac{{\lambda^{\star}_{1}}\log n}{\gamma}+\sqrt{\frac{{\lambda^{\star}_{1}}\log n}{\gamma}}\right)\left(\frac{\kappa\log n}{\gamma}+\sqrt{\frac{\kappa\log n}{\gamma{\lambda^{\star}_{d}}}}\right). Applying this to Equation ( 82 ), \displaystyle\left\|\boldsymbol{\Lambda}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}\right\|_{F} \displaystyle\leq C\sqrt{d}\left(\frac{{\lambda^{\star}_{1}}\log n}{\gamma}+\sqrt{\frac{{\lambda^{\star}_{1}}\log n}{\gamma}}\right)\left(\frac{\kappa\log n}{\gamma}+\sqrt{\frac{\kappa\log n}{\gamma{\lambda^{\star}_{d}}}}\right) \displaystyle+C\sqrt{d}{\lambda^{\star}_{1}}\left[\left(\frac{\kappa\log n}{\gamma}\right)^{2}+\frac{\kappa\log n}{\gamma{\lambda^{\star}_{d}}}\right]+C\left\|\mathbf{R^{\star}}\right\|_{F}\left(\frac{\log T}{\gamma}+\sqrt{\frac{\log T}{T\gamma}}\right). Recalling that \kappa={\lambda^{\star}_{1}}/{\lambda^{\star}_{d}} and rearranging, using the fact that \left(\sqrt{\frac{{\lambda^{\star}_{1}}\log n}{\gamma}}+1\right)^{2}\leq C\left(1+\frac{{\lambda^{\star}_{1}}\log n}{\gamma}\right), we have \displaystyle\left\|\boldsymbol{\Lambda}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}\right\|_{F} \displaystyle\leq\frac{C\sqrt{d}\kappa^{2}\log n}{\gamma}\left[\frac{{\lambda^{\star}_{1}}\log n}{\gamma}+1\right]+C\left\|\mathbf{R^{\star}}\right\|_{F}\left(\frac{\log T}{\gamma}+\sqrt{\frac{\log T}{T\gamma}}\right), as we set out to show. ∎ Lemma 20 . Suppose that Assumptions 1 and 2 hold. Then, with \mathbf{Q} as in Equation ( 78 ), \left\|\boldsymbol{\Lambda}^{-1/2}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{F}\leq C\kappa\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}\left[\kappa\sqrt{\frac{\log n}{\gamma}}\!\left(\frac{\kappa\log n}{\gamma}+\frac{1}{{\lambda^{\star}_{d}}}\!\right)+\!\left(\sqrt{\frac{\log T}{\gamma}}+\!\sqrt{\frac{1}{T}}\right)\right]. Proof. Expanding the Frobenius norm, \displaystyle\left\|\boldsymbol{\Lambda}^{-1/2}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{F}^{2} \displaystyle=\sum_{k=1}^{d}\sum_{\ell=1}^{d}\left(\frac{Q_{k,\ell}}{\sqrt{{\lambda_{k}}}}-\frac{Q_{k,\ell}}{\sqrt{{\lambda^{\star}_{\ell}}}}\right)^{2}=\sum_{k=1}^{d}\sum_{\ell=1}^{d}Q_{k,\ell}^{2}\left(\frac{\sqrt{{\lambda^{\star}_{\ell}}}-\sqrt{{\lambda_{k}}}}{\sqrt{{\lambda_{k}}}\sqrt{{\lambda^{\star}_{\ell}}}}\right)^{2} \displaystyle=\sum_{k=1}^{d}\sum_{\ell=1}^{d}\frac{\left(Q_{k,\ell}{\lambda^{\star}_{\ell}}-Q_{k,\ell}{\lambda_{k}}\right)^{2}}{{\lambda_{k}}{\lambda^{\star}_{\ell}}\left(\sqrt{{\lambda^{\star}_{\ell}}}+\sqrt{{\lambda_{k}}}\right)^{2}}. It follows that \left\|\boldsymbol{\Lambda}^{-1/2}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{F}^{2}\leq\frac{\left\|\boldsymbol{\Lambda}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}\right\|_{F}^{2}}{\left(\sqrt{{\lambda^{\star}_{d}}}+\sqrt{{\lambda_{d}}}\right)^{2}{\lambda^{\star}_{d}}{\lambda_{d}}}. Applying Lemma 13 along with Equations ( 28 ) and ( 27 ), \left\|\boldsymbol{\Lambda}^{-1/2}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{F}^{2}\leq\frac{C}{{\lambda^{\star}_{d}}^{3}}\left\|\boldsymbol{\Lambda}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}\right\|_{F}^{2}. Taking square roots and applying Lemma 19 , \left\|\boldsymbol{\Lambda}^{-1/2}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{F}\leq\frac{C}{{\lambda^{\star}_{d}}^{3/2}}\!\left[\frac{\sqrt{d}\kappa^{2}\log n}{\gamma}\!\left(\frac{{\lambda^{\star}_{1}}\log n}{\gamma}+1\!\right)+\left\|\mathbf{R^{\star}}\right\|_{F}\!\left(\frac{\log T}{\gamma}+\!\sqrt{\frac{\log T}{T\gamma}}\right)\right]. Simplifying and using our assumption that n=O(T) , \left\|\boldsymbol{\Lambda}^{-1/2}\mathbf{Q}-\mathbf{Q}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{F}\leq C\kappa\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}\left[\kappa\sqrt{\frac{\log n}{\gamma}}\!\left(\frac{\kappa\log n}{\gamma}+\frac{1}{{\lambda^{\star}_{d}}}\!\right)+\!\left(\sqrt{\frac{\log T}{\gamma}}+\!\sqrt{\frac{1}{T}}\right)\right], as we set out to show. ∎ Appendix F Proof of Main Result Using the supporting results established in Appendices C through E , we are ready to prove our main theorem. Proof of Theorem 1 . From the definitions in Equations ( 22 ) and ( 24 ), {\mathbf{\hat{X}}}=\mathbf{R}\mathbf{U}\boldsymbol{\Lambda}^{-1/2}~\text{ and }~{\mathbf{X^{\star}}}=\mathbf{R^{\star}}{\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}. Thus, recalling \mathbf{Q}\in\mathbb{O}_{d} from Equation ( 78 ), the triangle inequality implies \displaystyle\left\|{\mathbf{\hat{X}}}\mathbf{Q}-{\mathbf{X^{\star}}}\right\|_{{2,\infty}} \displaystyle\leq\left\|\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}+\left\|\mathbf{R}\mathbf{U}\mathbf{Q}\left(\mathbf{Q}^{\top}\boldsymbol{\Lambda}^{-1/2}\mathbf{Q}-{\mathbf{\Lambda}^{\star}}^{-1/2}\right)\right\|_{{2,\infty}} (83) \displaystyle+\left\|\mathbf{R}\left(\mathbf{U}\mathbf{Q}-{\mathbf{U^{\star}}}\right){\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} Applying Lemma 16 , \left\|\left(\mathbf{R}-\mathbf{R^{\star}}\right){\mathbf{U^{\star}}}{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq C\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}\left[1+\left(\sqrt{\frac{\log n}{\gamma}}+\sqrt{\frac{1}{T}}\right)\|\mathbf{R^{\star}}\|_{{2,\infty}}\right]. (84) Applying basic properties of the ({2,\infty}) -norm, \left\|\mathbf{R}\mathbf{U}\mathbf{Q}\left(\mathbf{Q}^{\top}\boldsymbol{\Lambda}^{-1/2}\mathbf{Q}-{\mathbf{\Lambda}^{\star}}^{-1/2}\right)\right\|_{{2,\infty}}\leq\left\|\mathbf{R}\right\|_{{2,\infty}}\left\|\mathbf{Q}^{\top}\boldsymbol{\Lambda}^{-1/2}\mathbf{Q}-{\mathbf{\Lambda}^{\star}}^{-1/2}\right\|. Applying Lemmas 12 and 20 , \displaystyle\left\|\mathbf{R}\mathbf{U}\mathbf{Q}\left(\mathbf{Q}^{\top}\boldsymbol{\Lambda}^{-1/2}\mathbf{Q}-{\mathbf{\Lambda}^{\star}}^{-1/2}\right)\right\|_{{2,\infty}} \displaystyle\leq C\kappa\left\|\mathbf{R^{\star}}\right\|_{{2,\infty}}\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}\left[\kappa\sqrt{\frac{\log n}{\gamma}}\!\left(\frac{\kappa\log n}{\gamma}+\frac{1}{{\lambda^{\star}_{d}}}\!\right)+\!\left(\sqrt{\frac{\log T}{\gamma}}+\!\sqrt{\frac{1}{T}}\right)\right]. Simplifying and using the assumptions in Equations ( 28 ) and ( 27 ), \displaystyle\left\|\mathbf{R}\mathbf{U}\mathbf{Q}\!\left(\mathbf{Q}^{\top}\!\boldsymbol{\Lambda}^{-1/2}\mathbf{Q}\!-{\mathbf{\Lambda}^{\star}}^{-1/2}\!\right)\right\|_{{2,\infty}}\!\leq C\kappa\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}\!\left(\kappa\sqrt{\frac{\log n}{\gamma}}+\sqrt{\frac{1}{T}}\right)\left\|\mathbf{R^{\star}}\right\|_{{2,\infty}}\!. (85) Recalling the definition of \mathbf{R} from Equation ( 8 ), \displaystyle\left\|\mathbf{R}\left(\mathbf{U}\mathbf{Q}-{\mathbf{U^{\star}}}\right){\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} \displaystyle=\left\|\mathbf{U}\boldsymbol{\Lambda}\left(\mathbf{Q}-\mathbf{U}^{\top}{\mathbf{U^{\star}}}\right){\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}} \displaystyle=\left\|\mathbf{U}\boldsymbol{\Lambda}\mathbf{U}^{\top}\mathbf{U}\left(\mathbf{Q}-\mathbf{U}^{\top}{\mathbf{U^{\star}}}\right){\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}. It follows that, by basic properties of the ({2,\infty}) -norm, \left\|\mathbf{R}\left(\mathbf{U}\mathbf{Q}-{\mathbf{U^{\star}}}\right){\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq\frac{\left\|\mathbf{R}\mathbf{U}\right\|_{{2,\infty}}}{\sqrt{{\lambda^{\star}_{d}}}}\left\|\mathbf{Q}-\mathbf{U}^{\top}{\mathbf{U^{\star}}}\right\|\leq\frac{\left\|\mathbf{R}\right\|_{{2,\infty}}}{\sqrt{{\lambda^{\star}_{d}}}}\left\|\mathbf{Q}-\mathbf{U}^{\top}{\mathbf{U^{\star}}}\right\|. Applying Lemmas 12 and 18 , \left\|\mathbf{R}\left(\mathbf{U}\mathbf{Q}-{\mathbf{U^{\star}}}\right){\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq\frac{C\left\|\mathbf{R^{\star}}\right\|_{{2,\infty}}}{\sqrt{{\lambda^{\star}_{d}}}}\frac{\kappa\log n}{\gamma}\left(\frac{\kappa\log n}{\gamma}+\frac{1}{{\lambda^{\star}_{d}}}\right). Simplifying, using the assumptions in Equations ( 28 ) and ( 27 ) and the trivial d\geq 1 , \left\|\mathbf{R}\left(\mathbf{U}\mathbf{Q}-{\mathbf{U^{\star}}}\right){\mathbf{\Lambda}^{\star}}^{-1/2}\right\|_{{2,\infty}}\leq C\kappa\sqrt{\frac{d\log n}{\gamma{\lambda^{\star}_{d}}}}\left\|\mathbf{R^{\star}}\right\|_{{2,\infty}}\sqrt{\frac{\log n}{\gamma}}. (86) Applying Equations ( 84 ), ( 85 ) and ( 86 ) to Equation ( 83 ), using our assumption that n=O(T) and simplifying, \displaystyle\left\|{\mathbf{\hat{X}}}\mathbf{Q}-{\mathbf{X^{\star}}}\right\|_{{2,\infty}} \displaystyle\leq C\sqrt{\frac{d\log T}{\gamma{\lambda^{\star}_{d}}}}\left[1+\kappa\left(\kappa\sqrt{\frac{\log n}{\gamma}}+\sqrt{\frac{1}{T}}\right)\|\mathbf{R^{\star}}\|_{{2,\infty}}\right], as we set out to show. ∎