Coherence-free Entrywise Estimation of Eigenvectors in Low-rank Signal-plus-noise Matrix Models

Authors: hao  yan
keith  levin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 21:23:50

Abstract: Spectral methods are widely used to estimate eigenvectors of a low-rank signal matrix subject to noise. These methods use the leading eigenspace of an observed matrix to estimate this low-rank signal. Typically, the entrywise estimation error of these methods depends on the coherence of the low-rank signal matrix with respect to the standard basis. In this work, we present a novel method for eigenvector estimation that avoids this dependence on coherence. Assuming a rank-one signal matrix, under mild technical conditions, the entrywise estimation error of our method provably has no dependence on the coherence under Gaussian noise (i.e., in the spiked Wigner model), and achieves the optimal estimation rate up to logarithmic factors. Simulations demonstrate that our method performs well under non-Gaussian noise and that an extension of our method to the case of a rank-$r$ signal matrix has little to no dependence on the coherence. In addition, we derive new metric entropy bounds for rank-$r$ singular subspaces under $\ell_{2,\infty}$ distance, which may be of independent interest. We use these new bounds to improve the best known lower bound for rank-$r$ eigenspace estimation under $\ell_{2,\infty}$ distance.

Main paper: 
 introduction: 
 Spectral methods are extensively used in contemporary data science and engineering [27] . The fundamental idea underlying these methods is that the eigenspace or singular subspace of an observed matrix reflects important structure present in the data from which it is derived. Spectral methods have been deployed successfully in a variety of tasks, including low-rank matrix denoising [30, 10] , factor analysis [21, 32, 3, 61, 11, 62] , community detection [49, 52, 1, 40, 50] , pairwise ranking [43, 25] and matrix completion [48, 24, 7] . The widespread use of spectral methods has driven extensive research into the theoretical properties of eigenspaces and singular subspaces, yielding normal approximation results [10, 11, 33, 58, 5] as well as perturbation bounds [60, 20, 22, 45] . For a more comprehensive recent review of spectral methods, see [27] .Consider an unknown symmetric matrix M ⋆ = U ⋆ Λ ⋆ U ⋆⊤ ∈ R n×n , where U ⋆ ∈ R n×r has orthonormal columns and Λ ⋆ ∈ R r×r is diagonal, containing the nonzero eigenvalues of M ⋆ ordered so that |λ⋆ 1 | ≥ |λ ⋆ 2 | ≥ • • • ≥ |λ ⋆ r | > 0.Our goal is to estimate U ⋆ from a noisy observationEQUATIONwhere W = [W ij ] 1≤i,j≤n is a symmetric random noise matrix with mean zero. We restrict our attention here to the symmetric case for the sake of simplicity, but we expect that our results can be extended to the asymmetric case using standard dilation arguments [53] .Throughout this paper, we assume that the entries of W are subgaussian. Assumption 1. The entries of W on and above the diagonal are independent and symmetric about zero with common variance σ 2 and common subgaussian parameter ν W .We remind the reader that the subgaussian parameter ν W serves as a "proxy" for the variance. Indeed, in the Gaussian case, we have σ 2 = ν W , while σ 2 ≤ ν W more generally [54, 56] .Spectral methods often estimate U ⋆ directly using the r leading eigenvectors U of Y . As a result, the entrywise and row-wise behavior of U has attracted considerable attention [31, 22, 41, 2, 4, 14] .Given an estimator U ∈ R n×r , the estimation error is measured in terms of the ℓ 2,∞ distanceEQUATIONwhere the presence of Γ is to resolve rotational non-identifiability. In the rank-one case, this reduces to the ℓ ∞ distance,EQUATIONfor u ⋆ ∈ R n and a given estimator u ∈ R n . Estimation error bounds in ℓ ∞ or ℓ 2,∞ distance typically rely on the incoherence parameter µ of U ⋆ , defined asµ = n r ∥U ⋆ ∥ 2 2,∞ ∈ [1, n/r].In the rank-one case with Gaussian noise, if the leading eigenvalue λ ⋆ of M ⋆ satisfies |λ ⋆ | = Ω(σ √ n), Theorem 4.1 of [27] shows that with probability at least 1-O(n -8 ), the leading eigenvectorEQUATIONWhen σ √ n ≲ |λ ⋆ | ≲ σ √ n log n, a regime of most interest (no ploynomial-time algorithm is known when |λ ⋆ | ≪ σ √ n [6] , and estimation is easy when |λ ⋆ | ≫ σ √ n log n), we show in Lemma 1 that Equation ( 4) is not improvable up to log-factors , as a result of the Baik-Ben Arous-Péché (BBP) phase transition [8] (see [12, 38, 34] for BBP-style phase transitions in the setting of this paper).Lemma 1. Under Equation (1) with Gaussian noise, let M ⋆ = λ ⋆ u ⋆ u ⋆⊤ . If both limits lim n→∞ λ ⋆ /(σ √ n) > 1 and lim n→∞ µ/n exist, then for any µ ∈ [1, n], there exists u ⋆ ∈ S n-1 such that almost surely,EQUATIONEquation (5) shows that the spectral estimate u has an intrinsic dependence on µ, with especially bad performance when µ is large and |λ ⋆ | = Θ(σ √ n log n). In this large-µ regime, beyond lowrankedness, M ⋆ exhibits additional structure (e.g., sparsity) that is not fully utilized by the spectral estimator. This suggests that the dependence on µ in Equations ( 4) and ( 5) is a shortcoming of the spectral estimator. In Algorithm 1, we present a new estimator designed to remove this dependence on µ. Theorem 1 shows that up to log-factors, it matches the minimax lower bound discussed below (see Equation (9) in Section 1.2). Experiments in Section 5 further support our theoretical results.In the rank-r case with Gaussian noise, Theorem 4.2 in [27] shows that when |λ ⋆ r | ≳ σEQUATIONwith probability at least 1 -O(n -8 ), where κ = |λ ⋆ 1 |/|λ ⋆ r | is the condition number of M ⋆ . Here again, the estimation error depends on µ, and we conjecture that this dependence is also sub-optimal. Algorithm 2 extends our rank-1 estimation algorithm to this more general rank-r case. Experiments in Section 5 show that Algorithm 2 outperforms the naïve spectral method in the general rank-r case, with little to no sensitivity to the coherence µ. We note in passing that the dependence on κ in Equation (6) can likely be removed [3, 62, 57] , though we do not pursue this here.Minimax lower bounds have been established for a variety of subspace estimation problems, including sparse PCA [21, 55] , matrix denoising [20] , structural matrix estimation [19] , network estimation [35, 63] and estimating linear functions of eigenvectors [42, 28] . Most of these studies focus on minimax lower bounds under the Frobenius or operator norm, derived using the packing numbers of Grassmann manifolds [46, 13] . In the matrix denoising literature, it is well-known that for r ≥ 1, minEQUATIONholds in a minimax sense (see Theorem 3 in [28] or Theorem 4 in [63] ). Far fewer papers have considered lower bounds under d 2,∞ [18, 4] , and these results are derived via the trivial lower boundEQUATIONwhich holds for any U , U ⋆ ∈ R n×r . Applying the lower bounds in Equations ( 7) and ( 8), we have supEQUATIONholds for any estimator U ∈ R n×r . When U ⋆ is incoherent, meaning that µ = O(1), this lower bound is achieved by the spectral estimation rate in Equation ( 6) when |λ ⋆ r | = Ω(σ √ n log n), and is achieved trivially by U = 0 n,r when |λ ⋆ r | = o(σ √ n). On the other hand, when U ⋆ is coherent, in the sense that µ = ω(1), and |λ ⋆ r | = Ω(σ √ n log n), our discussion above in Section (1.1) (including our new results in Theorem 1) suggests that the rate in Equation ( 9) can be achieved up to log-factors. This leaves open the question of the minimax rate when µ = ω(1) and |λ ⋆ r | = o(σ √ n). In this case, the lower bound in Equation ( 9) cannot exceed r/n. This seems suboptimal, as we expect some dependence on ∥U ⋆ ∥ 2,∞ (for example, consider the extreme case when λ ⋆ is very near zero). This suboptimality arises from the naïve lower bound in Equation (8) . In Theorem 2, we improve this lower bound, removing the r/n dependence in Equation (9) . This improved lower bound makes use of novel metric entropy bounds for singular subspaces, which may be of independent interest.We use C to denote a constant whose precise values may change from line to line. For a positive integer n, we write [n] = {1, 2, . . . , n}. |A| denotes the cardinality of a set A. For real numbers a and b, we write a ∨ b = max{a, b} and a ∧ b = min{a, b}. For a vector v = (v 1 , v 2 , . . . , v n )⊤ ∈ R n , we use the norms ∥v∥ 2 = n i=1 v 2 i and ∥v∥ ∞ = max i |v i |. We let e i ∈ R n , i ∈ [n] denote the standard basis vectors of R n . S n-1 = {u ∈ R n : ∥u∥ 2 = 1} denotes the unit sphere. For a matrix M ∈ R n×n , M i,• denotes its i-th row as a row vector, ∥M ∥ denotes its operator norm and ∥M ∥ 2,∞ = max i∈[n] ∥M i,• ∥ 2 indicates the maximum row-wise ℓ 2 norm. I n ∈ R n denotes the nby-n identity matrix. O r denotes the r-dimensional orthogonal group. We use both standard Landau notation and asymptotic notation: for positive functions f (n) and g(n), we writef (n) ≫ g(n), f (n) = ω(g(n)) or g(n) = o(f (n)) if f (n)/g(n) → ∞ as n → ∞. We write f (n) ≳ g(n), f (n) = Ω(g(n)) or g(n) = O(f (n))if for some constant C > 0, we have f (n)/g(n) ≥ C for all sufficiently large n. We writef (n) = Θ(g(n)) if both f (n) = O(g(n)) and g(n) = O(f (n)).The remainder of the paper is organized as follows. In Section 2, we study the eigenspace estimation problem for rank-one matrices and propose a new algorithm that achieves the minimax optimal error rate up to logarithmic factors in the growth regime where |λ ⋆ | = Ω(σ √ n log n) (Theorem 1). In Section 3, we extend this algorithm to rank-r eigenspace estimation. In Section 4, we present theoretical results for the metric entropy of subspaces under d ∞ and d 2,∞ and improve Equation (9) under the growth regime where |λ ⋆ | = O(σ √ n) (Theorem 2). Numerical results are provided in Section 5. We conclude in Section 6 with a discussion of the limitations of our study and directions for future work. Detailed proofs of all lemmas and theorems can be found in the appendix.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: the abstract and introduction give overviews of our two main results: 1) a new method for estimating the eigenvectors in signal-plus-noise matrix models and 2) a new lower bound for eigenvector estimation in the small-eigenvalue regime. These results are expanded upon (including a thorough discussion of assumptions and limitations) in Sections 2, 3 4 and 6. Our experiments in Section 5 illustrate which of our assumptions can likely be relaxed or removed entirely.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
rank-one matrix eigenspace estimation: 
 In this section, we study the model in Equation (1) when M ⋆ is rank-one with eigendecomposition M ⋆ = λ ⋆ u ⋆ u ⋆⊤ , where λ ⋆ ∈ R and u ⋆ ∈ S n-1 . As discussed in Section 1, spectral methods may have sub-optimal dependence on µ compared to the lower bound in Equation (9) . We show that a better estimator is possible by working with a carefully selected subset of entries of Y . We start with a key observation in Lemma 2, which states that any unit vector contains a subset of large entries, and this subset has a sufficiently large cardinality. This subset is the key to our new estimator. Lemma 2. Let A ⊂ [0, 1] be the setEQUATION)where L is given by L = log(2n) log log n .For n sufficiently large, for every v ∈ S n-1 , there exists α 0 ∈ A such thatEQUATION)To motivate Algorithm 1, suppose u ⋆ is entrywise positive. For α 0 ∈ A, denote the set in Equation ( 12) by I α0 . By Equation ( 12), the sum of entries M ⋆ ij with i, j ∈ I α0 grows as Ω(|λ ⋆ ||I α0 | log -2 n), while the sum of the corresponding entries of W grows as O(σ|I α0 | √ log n). That is, when |λ ⋆ | is sufficiently large, the signal contained in the entries i, j ∈ I α0 dominates the noise. If we knew I α0 , utilizing the entries in I α0 would reduce the estimation error incurred by small entries of u ⋆ . In practice, we do not know I α0 and must estimate such a subset. To ensure that this is possible, we impose a technical assumption on u ⋆ . We discuss this assumption below in Remark 2. Assumption 2. There exists an α 0 ∈ A satisfying Equation (12) and a constant 0 < ϵ 0 ≤ 1 such that for all sufficiently large n,{i : |u ⋆ i | ∈ [(1 -ϵ 0 )α 0 , (1 + ϵ 0 )α 0 ]} = ∅.We pause to give a few examples to illustrate Assumption 2. First, consider u ⋆ = c 1 e 1 + c 2 n -1/2 1 n , with c 1 , c 2 = Θ(1) chosen so that ∥u ⋆ ∥ 2 = 1. We note that c 1 , c 2 both depend on n, but are bounded away from zero as n grows, and one can verify that Assumption 2 holds with α 0 = log -1/2 n and ϵ 0 = 1/2. As another example, consider u ⋆ = n -1/2 1 n ∈ R n . One may verify that taking α 0 = (log n) -L/2 = 1/ √ 2n and ϵ 0 = 0.4 satisfies the conditions in Assumption 2.As an example of a setting that violates Assumption 2, consider u ⋆ obtained by renormalizing a vector of i.i.d. Gaussians. This results in u ⋆ being Haar-distributed on S n-1 and Assumption 2 is violated with high probability. To see this, note that u ⋆ ≈ g/ √ n where g ∼ N (0, I n ) (see Theorem 3.4.6 in [54] ). Since with high probability ∥g∥ ∞ = O( √ log n), Equation ( 12) holds only whenα 0 ≈ 1/ √ n.For Assumption 2 to hold, there must be a gap of Θ(1) between the entries of g, which fails with high probability.It is tempting to conclude from the counter-example just given that renormalizing a vector of i.i.d. entries must necessarily result in a u ⋆ that violates Assumption 2, but this is not always the case. If the entrywise distribution has suitable structure, u ⋆ may still obey Assumption 2. As an illustration, suppose that u ⋆ is obtained by renormalizing a vector g = (g 1 , g 2 , . . . , g n ) ⊤ ∈ R n with i.i.d. entries from a distribution with variance 1, so that u ⋆ ≈ g/ √ n. If the g i are drawn by taking g i = a with probability p and g i = b with probability 1 -p, then each entry of u ⋆ is either approximately ap/ √ n or approximately b(1 -p)/ √ n. Choosing a, b and p appropriately, we can ensure a gap between the entries of u ⋆ of size O(n -1/2 ), and we can takeα 0 = (log n) -L ≈ n -1/2 .Our new estimator of u ⋆ is a refinement based on the leading eigenvector and eigenvalue of Y . For the spectral estimator to provide a useful initialization, we make Assumption 3 on λ ⋆ . Assumption 3. There exists a constant C 1 > 2400/ϵ 0 , where ϵ 0 is as in Assumption 2, such that the leading eigenvalue λ ⋆ of M ⋆ satisfiesEQUATION)Remark 1. The dependence on ϵ 0 in Assumption 3 is for technical reasons discussed in Remark 2.In our proofs, we do not optimize the dependence on C 1 and assume that C 1 > 2400/ϵ 0 . As demonstrated in our experiments in Section 5, |λ ⋆ | ≥ √ ν W n log n appears sufficient in practice. When |λ ⋆ | ≤ √ ν W n, the spectral estimator fails to provide any useful initial estimate and it is believed that no polynomial-time algorithm can succeed. We provide more discussion on this matter in Remark 6.The final ingredient required for Algorithm 1 is a leading eigenvalue estimate λ that recovers the true signal eigenvalue λ ⋆ suitably well.Assumption 4. Under Assumption 3, λ is such that with probability at least [27] ). This is because λ [47] or Theorem 2.3 in [23] ; see also [26, 51, 17] ). Luckily, in our setting, the bias-corrected estimate1 -O(n -8 log n), λ -λ ⋆ ≤ C 2 √ ν W log= λ ⋆ +nσ 2 /λ ⋆ +O( √ ν W log n) (seeEQUATION)does satisfy Assumption 4 [26] . Another estimator, which falls naturally out of Algorithm 1, also satisfies Assumption 4. We find that it performs similarly to the debiased estimator λ c empirically, and so we do not explore it here. Theoretical results for this estimator are in the appendix.With the above assumptions in hand, we propose a new method given in Algorithm 1. We note that the main computational bottleneck of Algorithm 1 is to find the leading eigenvector u of Y , and thus the runtime is essentially the same as for standard spectral methods (see, e.g., [37] ).Input: Observed matrix Y ∈ R n×n ; leading eigenvalue estimate λ; parameter β > 0.Output: u ∈ R n 1: If λ < 0, set Y = -Y . Obtain the top eigenvector u ∈ S n-1 of Y . 2: Pick any α ∈ A such that the set Î = {i : |u i | ≥ α} satisfies | Î| ≥ 1 α 2 log 2 n, and{iEQUATION: Let Q ∈ R n×n be diagonal with Q kk = sgn (u k ) if k ∈ Î 1 if k ∈ Îc and let Y = QY Q. 4: Set S = j,k∈ Î Y jk and let v j = k∈ Î Y jk S λ for j ∈ [n]. 5: For each j ∈ [n], set u j = u j if |u j | ≤ σ/ λ log n, and u j = Q jj v j otherwise.Remark 2. In our proofs, we set β = ϵ 0 /2. Equation (16), Assumption 2 and the ϵ 0 -dependence in Assumption 3 are technical requirements to ensure that with high probability, Î is one of a few deterministic sets, avoiding the complicated dependence between Î and W . Empirically, Algorithm 1 works well even without these technical conditions. We conjecture that Assumption 2 as well as the ϵ 0 -dependence in Assumption 3 can be removed. See Section 5 for further discussion.As alluded to above, the intuition behind Algorithm 1 is that we aim to concentrate our efforts on estimating the large entries of u ⋆ . Consider an entry of Y given by λ ⋆ u ⋆ i u ⋆ j + W ij . Intuitively, locations corresponding to small entries of u ⋆ produce small u ⋆ i u ⋆ j . These entries of Y have a small signal to noise ratio compared to those arising from products of large entries of u ⋆ . If we knew the locations of the large entries of u ⋆ , we could use them to obtain more accurate estimates of u ⋆ . Essentially, both Algorithm 1 above and Algorithm 2 presented below consist of two parts: finding the large locations, and using those locations to improve our initial spectral estimate of u ⋆ . Algorithm 1 assumes that the entrywise variance σ 2 of W is known. Of course, in practice, this is not the case, and we must estimate σ 2 . There are several well-established methods for this estimation task. For example, when W is asymmetric, [36] introduces an estimator based on the median singular value of Y . In our case, it suffices to estimate σ 2 using a simple plug-in estimatorEQUATIONwhere M = λuu ⊤ ∈ R n×n . In general, if M ⋆ has rank r, then we set M = U ΛU ⊤ , where Λ is the leading r eigenvalues of Y (sorted by non-increasing magnitude) and U ∈ R n×r contains the corresponding r leading orthonormal eigenvectors as its columns. Lemma 3 controls the estimation error of the plug-in estimator σ 2 for a general rank-r signal matrix.Lemma 3. Under the model given in Equation (1), let M ⋆ = U ⋆ Λ ⋆ U ⋆⊤ be a rank-r matrix with r ≥ 1, where Λ ⋆ = diag (λ ⋆ 1 , λ ⋆ 2 , . . . , λ ⋆ r ) such that |λ ⋆ 1 | ≥ • • • ≥ |λ ⋆ r |.σ 2 -σ 2 ≤ 400ν W r n + 4ν W √ log n cn + 200ν W r √ log n n 3/2 (18)where c > 0 is a universal constant. Remark 3. We use the plug-in estimator σ in the debiased estimator λ c in Equation ( 14) and to construct u in Step 5 of Algorithm 1. Lemma 3 shows that this only introduces an extra log-factor to the error bound, which does not affect the estimation error rate of either λ ⋆ or u ⋆ .Our main result, Theorem 1, controls the estimation error of Algorithm 1, as measured under ℓ ∞ . Theorem 1. Under the model in Equation (1), suppose that Assumptions 1, 2, 3 and 4 hold. Then for n sufficiently large, the estimate u ∈ R n produced by Algorithm 1 satisfiesd ∞ ( u, u ⋆ ) ≤ C √ ν W (log n) 5/2 |λ ⋆ |with probability at least 1 -O(n -8 log n), where C > 0 is a universal constant. Remark 4. Under Gaussian noise, in the regime |λ ⋆ | = Ω(σ √ n log n), our upper bound is minimax rate-optimal up to log-factors compared to the lower bound in Equation (9) . In particular, the rate obtained in Theorem 1 does not depend on the coherence parameter µ. A more careful analysis might be able to remove some of the log-factors in Theorem 1, but we leave this matter for future work.√ 1 -a 2 S n-2 . 3. Set u ⋆ k = I n -U ⋆ •,1:(k-1) U ⋆⊤ •,1:(k-1) v, normalize u ⋆ k to have unit ℓ 2 norm, and set U ⋆ •,k = u ⋆ k . If k = 1, then we take U ⋆ •,1:(k-1) U ⋆⊤ •,1:(k-1)to be the zero matrix. Under this procedure, each u ⋆ k has coherence approximately a 2 n. Since the large entries of the u ⋆ k are unlikely to appear in the same rows, U ⋆ also has coherence a 2 n. We take r = 2 here. Having generated Y = M ⋆ +W , we obtain estimates via the naïve spectral method and Algorithm 2. and measure their estimation error under d ∞ . We vary n from 100 to 15100 in increments of 1000 and report the mean of 20 independent trials for each combination of n, a and noise distribution.The results are summarized in Figure 2 , showing the error for u ⋆ k , k ∈ {1, 2} using the spectral estimate (blue/purple) and Algorithm 2 (orange/red), under Gaussian (left), Rademacher (middle) and Laplacian (right) noise. Shaded bands indicate 95% bootstrap CIs. In all settings, Algorithm 2 improves markedly on the spectral estimator. Algorithm 2 shows no visible dependence on µ under Gaussian noise. Under Rademacher noise, its µ-dependence is the reverse of the spectral estimator. Under Laplacian noise, it shows slight dependence on µ, which we again expect to be asymptotically smaller than the rate in Theorem 1. In the appendix, we consider r = 3 and measure error under d 2,∞ , and we again find that Algorithm 2 outperforms spectral estimators and is far less sensitive to µ.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Our main assumptions, the reasons for needing them, and their implications are discussed in Sections 1 through 4. In particular, see Remarks 1, 2 and 6. Our experiments in Section 5 explore which of our assumptions might be relaxed or removed. A broad, albeit short, overview of limitations and areas for future work is also given in Section 6, titled "Discussion, limitations and conclusion". Computational costs and efficiency are addressed just before Algorithm 1.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
rank-r matrix eigenspace estimation: 
 To handle the more general case in which the signal matrix M ⋆ is rank r, we propose Algorithm 2, which yields an estimate of U ⋆ . This is achieved by estimating the r leading eigenvectors separately, then combining them into an estimate U ∈ R n×r . We explore the empirical performance of Algorithm 2 via simulation in Section 5.2 and leave its theoretical analysis to future work. Algorithm 2 requires the observed matrix Y and an estimate of the k-th leading eigenvalue λ ⋆ k of M ⋆ as input. Similar to the rank-one case, the top-r leading eigenvalues λ 1 , λ 2 , . . . , λ r of Y are biased [47] . We again use a debiased estimator λ k,c for k ∈ [r] as input to Algorithm 2, given byEQUATION)Algorithm 2 is a natural extension of Algorithm 1. Essentially, it converts the problem of estimating u ⋆ k into an eigenvector estimation problem under a rank-one signal-plus-noise model given byY = λ ⋆ k u ⋆ k u ⋆⊤ k + (M ⋆ -k + W ) = λ ⋆ k u ⋆ k u ⋆⊤ k + M ⋆ -λ ⋆ k u ⋆ k u ⋆⊤ k + W , where M ⋆ -k = M ⋆ -λ ⋆ k u ⋆ k u ⋆⊤ k .There are two differences between Algorithms 1 and 2. First, we remove Equation ( 16) from Algorithm 1, as this is mainly a technical requirement (see Remark 2). More importantly, in Algorithm 2, we conjugate Y by a random orthogonal matrix H ∈ O n . The (r -1) leading eigenvectors of HM ⋆ -k H ⊤ form a random subspace of R n×(r-1) , which allows us to treat HM ⋆ -k H ⊤ as a noise matrix. By way of illustration, consider the rank-2 case with M⋆ -1 = λ ⋆ 2 u ⋆ 2 u ⋆⊤ 2 .Hu ⋆ 2 behaves similarly to a random vector drawn uniformly from S n-1 . Therefore, one would expect Hu ⋆ 2 u ⋆⊤ 2 H to behave similarly to a noise matrix n -1 gg ⊤ , where g ∼ N (0, I n ) (see Chapter 3 of [54] ). As in the discussion after Lemma 2, we can find a set of indices I α0 such that the signal in the corresponding entries of Hu ⋆ 1 dominates the noise.Algorithm 2 Coherent optimal eigenvector estimation algorithmInput: Observed matrix Y ∈ R n×n ; k-th leading eigenvalue estimate λ k . If λ k < 0, set Y = -Y . Output: u k ∈ R n 1: Obtain the top-r eigenvectors U of HY H ⊤ , where H ∈ O n is Haar-distributed. 2: Set Q = diag sgn U •,k and set Y = QHY H ⊤ Q. 3: Pick an α 0 ∈ A such that for Î := i : | U i,k | ≥ α 0 , | Î| ≥ 1/α 2 0 log 2 n. 4: Set S = j,ℓ∈ Î Y jℓ 1/2 and set v j = ℓ∈ Î Y jℓ S λ k for j ∈ [n]. 5: Let U = H ⊤ U . For j ∈ [n], set u k,j =    U k,j if |U k,j | ≤ σ | λ k | log n H ⊤ Q v j otherwise.As mentioned above, our experiments in Section 5.2 indicate that Algorithm 2 performs well. A proof of its performance, however, is more complicated than Theorem 1. The main difficulty arises from the fact that in Algorithm 2, we conjugate by a random orthogonal transformation. This ensures that when considering the large entries of one signal eigenvector, the other signal eigenvectors are ignorable. Unfortunately, this random orthogonal transformation breaks Assumption 2 and introduces complicated dependency structure, requiring a more careful analysis that we leave for future work.4 Estimation lower bounds under ℓ 2,∞ distance Theorem 1 demonstrates that for a rank-one signal, dependence of the estimation rate on µ can be removed when |λ ⋆ | = Ω(σ √ n log n). In this regime, our result matches the lower bound in Equation ( 9) up to log-factors, making this the minimax lower bound under Assumption 2. As discussed in Remark 2, we expect Assumption 2 can be removed via a more careful analysis, rendering the lower bound in Equation ( 9) optimal under |λ ⋆ | = Ω(σ √ n log n). On the other hand, as discussed in Section 1.2, the lower bound in Equation ( 9) is sub-optimal in the regime where|λ ⋆ | = O(σ √ n).In what follows, we aim to improve upon Equation ( 9) by deriving metric entropy bounds [54] for rank-r singular subspaces under the ℓ 2,∞ distance when|λ ⋆ | = O(σ √ n).Recall that for a semi-metric ρ defined on a set K, we may define the δ-packing number M(K, ρ, δ) of K under ρ (see Chapter 15 in [56] ). The packing δ-entropy, log M(K, ρ, δ), captures the complexity of the space K, and a lower bound on the δ-entropy can be translated into a lower bound on the minimax estimation error rate. For a given r ∈ [n] and 1 ≤ µ ≤ n/r, we consider the parameter setEQUATIONBelow, we write K r,µ for K(n, r, µr/n). Lemma 4 lower bounds log M(K r,µ , d 2,∞ , δ). We focus on the range r/n ≲ δ 2 ≲ µr/n, as the lower bound in Equation (9) shows that δ 2 ≪ r/n is not achievable when |λ ⋆ | = O(σ √ n) and δ 2 ≫ µr/n is achieved by the trivial all-zeros estimate. Lemma 4. Suppose that n/µ ≥ max{4, r} and µ ≥ 12 log(12n), and let δ > 0 be such thatEQUATIONwhere c 0 > 0 is a universal constant. Then when n is sufficiently large,EQUATIONRemark 5. Lemma 4 applies when log n ≲ µ ≲ n/r. A more careful analysis might relax the lower bound, but when µ ≲ log n, any U ∈ K r,µ is nearly incoherent and Equation (9) is nearly optimal. An upper bound matching Lemma 4 up to log-factors can be found in the appendix.Lemma 4 implies an improved lower bound compared to Equation (9) . Consider the parameter spaceΩ(λ ⋆ , µ, r) = {(Λ ⋆ , U ⋆ ) : Λ ⋆ = λ ⋆ I r , U ⋆ ∈ K r,µ } .Using the Yang-Barron method [59] , we obtain a lower bound for eigenspace estimation in the rank-r signal-plus-noise model for|λ ⋆ | = O(σ √ n).A detailed proof can be found in the appendix.Theorem 2. Under Assumption 1 and the conditions of Lemma 4, for any 0 < λ ⋆ ≤ (6√ C 0 ) -1 σ √ n, where C 0 > 0 is a universal constant related to covering numbers of Grassmann manifolds, there is a universal constant c > 0 such that for all sufficiently large n,inf U ∈R n×r sup (Λ ⋆ ,U ⋆ )∈Ω(λ ⋆ ,µ,r) E Λ ⋆ ,U ⋆ d 2,∞ U , U ⋆ ≥ c σ √ r λ ⋆ ∧ µr n log(n/µ) .Remark 6. Theorem 2 removes the upper limit r/n from Equation (9), suggesting that µ only comes to bear when λ ⋆ ≤ σ √ n. This regime is not well studied, as the BBP transition [8] implies that spectral methods fail, but other algorithms might achieve our lower bound. For example, signal detection is possible if structure is present [6] . Unfortunately, any such algorithm is likely to be computationally expensive, given the general belief that no polynomial-time algorithm can succeed when λ ⋆ ≤ σ √ n [39, 9] . We leave further exploration of this small-λ ⋆ regime to future work. Remark 7. The parameter space Ω(λ ⋆ , µ, r) considered in Theorem 2 contains only signal matrices with condition number κ = 1. In recent work, the authors have established lower bounds akin to Theorem 2 that show the role of condition number. A full accounting of the interplay between condition number and coherence is a promising area for future work.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: Our main technical assumptions, Assumptions 1, 2, 3 and 4 are prominently laid out and explained in Sections 1 and 2. The necessity of these assumptions and the potential to relax or remove them are discussed in those sections, as well as in Section 6. All theorems and lemmas are stated with their necessary additional assumptions (e.g., growth rates and relations between parameters), and all are numbered, cross-referenced and have working hyperlinks. Full proofs are given in the supplementary materials. We have provided thorough background and intuition surrounding these proofs, though proof sketches have largely been removed due to space constraints. We are committed to including proof sketches in a camera-ready version using the allotted extra page, should the reviewers request them. Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experimental result reproducibility: 
 Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: Algorithms are described in the text, including details regarding how hyperparameters were selected and minor changes made to Algorithms 1 and 2 "as written" as opposed to "as run on the cluster". Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 7. Experiment Statistical Significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: all experiment plots include error bars denoting 95% bootstrap confidence intervals. This is discussed in Section 5. It is clearly stated in the text that the randomness in the error bars comes from independent repetitions of the same experimental setup. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). Justification: This paper concerns a theoretical/methodological question regarding estimation of eigenvectors from noisy matrices. Given the theoretical nature of this work, it is hard to foresee direct social impacts, either positive or negative, from this work. Positive impacts of eigenvector estimation methods (e.g., PCA, matrix denoising, etc) are ubiquitous (see, for example, medical image processing, to name just one application area). These positive impacts are alluded to in the introduction. Of course, the abuse or misuse of statistical methods and models has frequently resulted in negative societal impacts and inequitable outcomes for underrepresented groups. We acknowledge these possible negative outcomes, albeit briefly, in Section 6. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
numerical experiments: 
 We turn to a brief experimental exploration of our theoretical results. All experiments were run in a distributed environment on commodity hardware without GPUs. In total, the experiments reported below used 3425 compute-hours. Mean memory usage was 3.5 GB, with a maximum of 11 GB.We begin with the rank-one setting considered in Algorithm 1, in which we observeY = M ⋆ + W = λ ⋆ u ⋆ u ⋆⊤ + W ,and wish to recover u ⋆ ∈ S n-1 . We take λ ⋆ = √ n log n in all experiments, matching the rate in Remark 1. We consider three distributions for the entries of W : Gaussian, Laplacian and Rademacher, all scaled to have variance σ 2 = 1. We consider two approaches to generating u ⋆ . In either case, we set a random entry of u ⋆ to be a ∈ {0.3, 0.55, 0.8}, then generate the remaining entries by either 1. drawing uniformly from √ 1 -a 2 S n-2 , or 2. drawing uniformly from {±1} n-1 then normalizing these to haveℓ 2 norm √ 1 -a 2 .In both cases, ∥u ⋆ ∥ ∞ =a and µ = a 2 n with high probability. We take a=Θ(1), since in finite samples, Cn -1/2 log n (which is nearly incoherent) is hard to discern from a constant (e.g., when n = 20000, 4n -1/2 log n ≈ 0.28, nearly matching a = 0.3). Having generated Y = M ⋆ + W , we estimate u ⋆ using both the spectral estimate u and Algorithm 1 and measure their estimation error under d ∞ . We report the mean of 20 independent trials for each combination of problem size n, magnitude a and methods for generating u ⋆ and W . We vary n from 100 to 15100 in increments of 1000.When running Algorithm 1, we use the debiased estimate λ c from Equation (14) . This requires an estimate of σ, for which we use the plug-in estimator in Equation (17) . We set β = 0, eliminating Equation (16) . Similar to Algorithm 2, we conjugate Y by a random orthogonal matrix H ∈ O n . We expect the top eigenvector u of HY H ⊤ to be approximately uniformly distributed on S n-1 , as it is close to Hu ⋆ (see Theorem 2.1 in [44] ). Thus, the median of the absolute values of u should be Θ(n -1/2 ). Instead of selecting α 0 according to Equation (15) , we set α 0 to be this median. The requirement in Equation ( 15) is then fulfilled, since there are roughly n/2 entries larger than the median. After obtaining u from Algorithm 1, we return H ⊤ u as our estimate of u ⋆ . We note that this random rotation further serves to illustrate that Assumption 2 is merely a technical requirement: after a random rotation, with high probability, Hu ⋆ does not satisfy Assumption 2.Figure 1 compares the accuracy in estimating u ⋆ using the leading eigenvector of Y (blue) and Algorithm 1 (orange) under the three noise settings and two generating procedures for u ⋆ . Shaded bands indicate 95% bootstrap confidence intervals (CIs). Across settings, Algorithm 1 recovers u ⋆ with a much smaller estimation error under d ∞ compared to the naïve spectral estimate, especially when ∥u ⋆ ∥ ∞ (i.e., the coherence µ) is large. The spectral method degrades noticeably as coherence increases, while Algorithm 1 has far less dependence on µ. Indeed, under Gaussian noise (the first column of Figure 1 ), it has no visible dependence on µ. Under Rademacher noise (middle column of Figure 1 ), the dependence of Algorithm 1 on µ appears slightly reversed from that of the spectral estimator. Under Laplacian noise (right column of Figure 1 ), there seems to be a slight dependence on µ. Further examination in the appendix suggests that this is due to estimating the entries other than the largest element of u ⋆ , and is likely asymptotically smaller than the rate in Theorem 1.For the rank-r setting, we have a signal matrix with eigenvalues|λ ⋆ 1 | ≥ . . . ≥ |λ ⋆ r |. We observe Y = M ⋆ + W = U ⋆ Λ ⋆ U ⋆ + W , where Λ ⋆ = diag(λ ⋆ 1 , . . . , λ ⋆ r), and we wish to recover U ⋆ ∈ R n×r . We take σ = 1 and λ ⋆ r = √ n log n. Recovering each column of U ⋆ separately requires an eigengap, defined for k ∈ [r] as∆ k := |λ ⋆ k -λ ⋆ k+1 | and ∆ 0 = ∞.Typically, the estimation error of the k-th eigenvector has a O(min{∆ k , ∆ k-1 } -1 ) dependence on the eigengaps [57] . Here, we set ∆ k = 0.5√ n log n, so λ ⋆ k = 0.5(r -k + 2) √ n log n for all k ∈ [r].As in the rank-one case, we generate entries of W from Gaussian, Laplacian and Rademacher distributions, all scaled to have unit variance. The true eigenvectors U ⋆ are generated by repeating the following procedure for k ∈ [r]:1. Randomly select an element of v ∈ R n and set it to be a ∈ {0.3, 0.55, 0.8}.To the best of our knowledge, we are the first paper to consider the task of non-spectral entrywise eigenvector estimation. The nearest obvious competing method might be based on approximate message passing (AMP; see [34] for an overview). Such a comparison is included in the appendix, where our experiments indicate that while AMP performs well in recovering the signal eigenvectors as measured by ℓ 2 error, our method as specified in Algorithms 1 and 2 perform better under entrywise and ℓ 2,∞ error. Experimental details and further discussion can be found in the appendix. 
discussion, limitations and conclusion: 
 We have presented new methods for eigenvector estimation in signal-plus-noise matrix models and new lower bounds for estimation rates in these models. The entrywise estimation error of our method has no dependence on the coherence µ for rank-one signal matrices, and achieves the optimal estimation rate up to log-factors. Simulations show that our method tolerates non-Gaussian noise and its extension to rank-r signal matrices has little dependence on µ. One limitation of our method is that it assumes homoscedastic noise. Future work will aim to relax this assumption and the technical condition in Assumption 2. In the rank-r case, Algorithm 2 estimates each eigenvector separately, requiring an eigengap. Future work will avoid this by simultaneously or iteratively estimating multiple eigenvectors. We note in closing that inequitable social impacts from abuse or misuse of models and methods are common, but we see no particular such impacts in the present work.A Proof of Lemma 1Proof. Let θ = lim n→∞ (σ √ n) -1 λ ⋆ . For any u ⋆ ∈ S n-1, by the Baik-Ben Arous-Péché (BBP) phase transition ( [8] ; see also Theorem 2 in [38] ), the top eigenvector u of Y obeysEQUATION)Let s = ⌈n/µ⌉, and considerEQUATION)Without loss of generality, we assume that d ∞ (u, u ⋆ ) = ∥u -u ⋆ ∥ ∞ , since otherwise we can repeat the following argument with -u instead of u. We haveEQUATION)Expanding the term inside the square root,EQUATIONwhere the last equality follows from the construction of u ⋆ in Equation (24) . By the Cauchy-Schwarz inequality, we haveEQUATIONwhere the last equality follows from the construction of u ⋆ in Equation (24) . Plugging Equation ( 27) into Equation ( 26), we obtains i=1 |u i -u ⋆ i | 2 ≥ ⟨u ⋆ , u⟩ 2 + 1 -2⟨u ⋆ , u⟩ = 1 -⟨u ⋆ , u⟩ 2 .When θ > 1, applying Equation ( 23) yields thatEQUATIONholds almost surely. Again using the fact that θ > 1, we haveEQUATION)Combining Equations ( 25), ( 28) and ( 29), it holds almost surely thatlim inf n→∞ d ∞ (u, u ⋆ ) ≥ lim inf n→∞ 1 √ s |u i -u ⋆ i | 2 1/2 ≥ lim n→∞ 1 2θ 2 • 1 1 + n/µ ,where the last inequality follows from s = ⌈n/µ⌉. Since µ ≤ n, it follows thatlim inf n→∞ d ∞ (u, u ⋆ ) ≥ lim n→∞ 1 2θ 2 • µ µ + n ≥ lim n→∞ 1 2 √ 2 θ 2 • µ nalmost surely. By the definition of θ, we havelim inf n→∞ d ∞ (u, u ⋆ ) ≥ lim n→∞ σ 2 n 2 √ 2|λ ⋆ | 2 µ n = lim n→∞ σ 2 √ nµ 2 √ 2|λ ⋆ | 2 ,completing the proof. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: This paper concerns a theoretical question surrounding minimax estimation rates and includes no models or data with risk of misuse, to the best of our knowledge. 
 
 Appendix: Proof. The upper bound|{i : |v i | ≥ α 0 }| ≤ 1 α 2 0follows trivially from the fact that ∥v∥ 2 = 1.To prove the lower bound, we consider the disjoint intervalsEQUATIONRecall the definition of L from Equation ( 11),L = log(2n) log log n .Rearranging terms, we have- L 2 log log n = - 1 2 log(2n).Exponentiating both sides of the above display,log -L/2 n = 1 √ 2n .Noting that by Equation ( 30),⌈L⌉-1 ℓ=0 I ℓ = log -L/2 n, 1 = 1 √ 2n , 1 , for any i ∈ [n] such that |v i | / ∈ ∪ ⌈L⌉-1 ℓ=0 I ℓ , we have |v i | < log -L/2 n = 1 √ 2n ,and therefore, summing over all i ∈EQUATION) Let x ℓ = |{i : |v i | ∈ I ℓ }| for all ℓ ∈ {0, 1, . . . , ⌈L⌉ -1}. We have i:|vi|∈I ℓ v 2 i ≤ x ℓ max i:|vi|∈I ℓ v 2 i ≤ x ℓ log ℓ n ,where the last inequality follows from the definition of I ℓ in Equation (30) . Summing over all ℓ ∈ {0, 1, . . . , ⌈L⌉ -1} on both sides , we have⌈L⌉-1 ℓ=0 x ℓ log ℓ n ≥ i:|vi|∈ ⌈L⌉-1 ℓ=0 I ℓ v 2 i = 1 - i:|vi| / ∈ ⌈L⌉-1 ℓ=0 I ℓ v 2 i > 1 2 ,where the last inequality follows from Equation (31) . The above further implies that⌈L⌉ • max ℓ∈{0,1,••• ,⌈L⌉-1} x ℓ log ℓ n ≥ ⌈L⌉-1 ℓ=0 x ℓ log ℓ n > 1 2 .Hence, rearranging, there exists anℓ 0 ∈ {0, 1, • • • , ⌈L⌉ -1} such that x ℓ0 > log ℓ0 n 2⌈L⌉ > log ℓ0-1 n = log ℓ0+1 n log 2 n ,where the second inequality holds for suitably large n by the definition of L given in Equation (11) .Finally, note that for all i ∈[n] such that |v i | ∈ I ℓ0 , we have |v i | ≥ log -(ℓ0+1)/2n by the definition of I ℓ0 in Equation (30) . Takingα 0 = log -(ℓ0+1)/2 n if ℓ 0 ∈ {0, 1, • • • , ⌈L⌉ -2} log -L/2 n if ℓ 0 = ⌈L⌉ -1 yields that |{i : |v i | ≥ α 0 }| ≥ x ℓ0 > 1 α 2 0 log 2 n .We complete the proof by noting that α 0 is in A, where A is defined in Equation (10) .Proof. Expanding the right hand side of Equation ( 17), we haveσ 2 = 2 n(n + 1) 1≤i≤j≤n M ⋆ ij -M ij + W ij 2 = 2 n(n + 1) 1≤i≤j≤n M ⋆ ij -M ij 2 + 2 n(n + 1) 1≤i≤j≤n W 2 ij + 4 n(n + 1) 1≤i≤j≤n W ij M ⋆ ij -M ij .Subtracting σ 2 on both sides and applying the triangle inequality, we haveEQUATIONWe proceed to bound each term in the last inequality of Equation ( 32) separately.For the first term in Equation (32) , by an argument analogous to that of Equation (3.15) in [27] ,2 n(n + 1) M -M ⋆ 2 F ≤ 8r n(n + 1) ∥W ∥ 2 .By standard matrix concentration inequalities [53, 54] , with probability at least 1 -O(n -8 ),EQUATIONCombining the above two displays, we obtain an analogue of Equation (3.16 ) in [27] , namely that with probability at leastEQUATION)For the second term in Equation ( 32), applying standard concentation inequalities for subexponential random variables (see, e.g., Chapter 2 in [54] ),P   1≤i≤j≤n W 2 ij -σ 2 ≥ t   ≤ 2 exp -c 2 min 2t 2 n(n + 1)ν 2 W , t ν W ,where c > 0 is an absolute constant. Taking t = 2ν W n(n + 1) log n/c and dividing through by n(n + 1)/2, it holds with probability at least 1 -O(n -8 ) thatEQUATION)For the third term in Equation ( 32), using the matrix Hölder inequality (see Corollary IV.2.6 in [15] ), we havetr W M ⋆ -M ≤ ∥W ∥∥M ⋆ -M ∥ * ,where ∥ • ∥ * denotes the nuclear norm, defined to be the sum of the singular values. Using the fact that M ⋆ -M has at most rank 2r, we havetr W M ⋆ -M ≤ 2r∥W ∥∥M ⋆ -M ∥.Applying Equation (33) and following an argument analogous to that in Equations (3.12) and (3.15) in [27] , we have that with probability at least 1 -O(n -8 ),∥W ∥ ≤ 5 √ ν W n and ∥M ⋆ -M ∥ ≤ 10 √ ν W n.It follows that with probability at leastEQUATION)For the fourth term in Equation ( 32), we haveEQUATION)Applying Equations ( 34), ( 35), ( 36) and (37) to Equation (32) , with probability at least1 -O(n -8 ), | σ 2 -σ 2 | ≤ 400ν W r n + 4ν W √ log n cn + 200ν W r √ log n n 3/2 ,as we set out to show.Without loss of generality, we derive our results under the assumption thatd ∞ (u, u ⋆ ) = ∥u -u ⋆ ∥ ∞ .Otherwise, we can replace u with -u and obtain the same results. We remind the reader that we use c and C to denote constants with respect to n, whose precise value might change from line to line. To prove Theorem 1, we first state and prove a few technical lemmas. that for all ℓ ∈ [n],EQUATION)Proof. We largely follow the proof of Theorem 4.1 in [27] , albeit with a slightly more careful analysis. In particular, we note that the proof of Theorem 4.1 in [27] is written for the case where W has Gaussian entries. It is straightforward to extend this argument to subgaussian entries by applying standard subgaussian concentration inequalities and truncation arguments [54, 56] , in essence replacing all appearances of σ 2 in their results with the subgaussian parameter (i.e., "variance proxy") ν W . Here, we only sketch out a few key points and refer the reader to Section 4.1.4 of [27] for a full argument. For each ℓ ∈ [n], we construct a leave-one-out copy Y (ℓ) asY (ℓ) = λ ⋆ u ⋆ u ⋆⊤ + W (ℓ) ,whereW (ℓ) ij = W ij , if ℓ ̸ ∈ {i, j} 0 otherwise.For each ℓ ∈ [n], let λ (ℓ) and u (ℓ) denote, respectively, the largest-magnitude eigenvalue of Y (ℓ) and its corresponding eigenvector. Without loss of generality, flipping signs if necessary, we assume thatd ∞ (u, u ⋆ ) = ∥u -u ⋆ ∥ ∞ .By Equation (4.20) in [27] , with probability at least 1 -O n -8 we haveEQUATIONBy Equation (4.15) in [27] , we haveu -u (ℓ) 2 ≤ 4 Y -Y (ℓ) u (ℓ) 2 |λ ⋆ | .Following the argument just after Equation (4.18) in [27] , replacing the Gaussian concentration inequalities with subgaussian concentration inequalities, one can show thatY -Y (ℓ) u (ℓ) 2 ≤ 5 ν W log n + 5 √ ν W n |u ℓ | + 5 √ ν W n u -u (ℓ) 2, with probability at least 1 -O n -8 . Combining the above two displays and rearranging slightly,EQUATION)Combining the triangle inequality with the trivial upper bound ∥u -u (ℓ) ∥ ∞ ≤ ∥u -u (ℓ) ∥ 2 , we have for any ℓ ∈ [n], |u ℓ -u ⋆ ℓ | ≤ u ⋆ ℓ -u (ℓ) ℓ + u -u (ℓ) 2 .Applying Equations ( 39) and ( 40), it holds with probability at least1 -O(n -8 ) that |u ℓ -u ⋆ ℓ | ≤ 20 √ ν W n |λ ⋆ | |u ⋆ ℓ | + 40 √ ν W log n + 40 √ ν W n |u ℓ | |λ ⋆ | ≤ 20 √ ν W n |λ ⋆ | |u ⋆ ℓ | + 40 √ ν W log n + 40 √ ν W n|u ⋆ ℓ | + 40 √ ν W n |u ℓ -u ⋆ ℓ | |λ ⋆ | ,where the second inequality follows from the triangle inequality. After rearranging terms and using the fact that |λ ⋆ | ≥ 80 √ ν W n, we obtain the desired bound|u ℓ -u ⋆ ℓ | ≤ 80 √ ν W log n + 120 √ ν W n|u ⋆ ℓ | |λ ⋆ | ,for all ℓ ∈ [n], completing the proof.Lemma 6, which controls the behavior of the index set Î in Algorithm 1, follows from an application of Lemma 5.Lemma 6. Under the model in Equation (1) with M ⋆ = λ ⋆ u ⋆ u ⋆⊤ , suppose that Assumption 1 holds and Assumption 3 holds with constant C 1 > 2400/ϵ 0 , where ϵ 0 ∈ (0, 1) is fixed. For α ∈ A, defineÎα = {i : |u i | ≥ α} ,where u is the leading eigenvector of Y , as in Step 1 of Algorithm 1. For all sufficiently large n, the following all hold with probability at least 1 -O(n -8 log n):EQUATION{iEQUATION{i :EQUATIONand {i :EQUATIONProof. Fix α ∈ A. For any i ∈ Îα , we have |u i | ≥ α by definition. We haveEQUATION)where the first inequality follows from the fact that |u i | ≥ α for i ∈ Îα , the second inequality follows from set inclusion, and the last inequality follows from combining the triangle inequality with Lemma 5. IfEQUATION)and we take C 1 > 2400/ϵ 0 in Assumption 3, then we have|u ⋆ i | ≥ α - 80ϵ 0 √ ν W log n 2400 √ ν W n log n - 120ϵ 0 √ ν W n 2400 √ ν W n log n |u ⋆ i | ≥ α - ϵ 0 30 1 n - ϵ 0 20 √ log n |u ⋆ i |.Since α ≥ 1/2n, after rearranging terms,EQUATIONwhere the last inequality holds for all i ∈ [n] satisfying Equation (46) (i.e., all i ∈ Îα ) when n is sufficiently large. Thus, we conclude that, applying a union bound followed by Equation (45) ,EQUATION)Following a similar argument, we can show that Equation (44) holds with probability at least 1 -O(n -8 ), and that, also with probability at leastEQUATION)On the other hand, combining the triangle inequality with the bound in Equation (38) in Lemma 5, it holds with probability at least1 -O(n -8 ) that for all i ∈ [n] satisfying |u ⋆ i | ≥ (1 + ϵ 0 /2)α, |u i | ≥ |u ⋆ i | -|u i -u ⋆ i | ≥ 1 + ϵ 0 2 α - ϵ 0 30 √ n - ϵ 0 (1 + ϵ 0 /2)α 20 √ log n > α,where the last inequality holds when n is sufficiently large. It follows thatEQUATIONFollowing the same argument, we have that Equation (43) holds with probability at least 1 -O(n -8 ) and that {i :EQUATIONalso with probability at least 1 -O(n -8 ).Combining Equation (48) and Equation ( 50) yields that Equation (41) holds with probability at least 1 -O(n -8 ). Similarly, combining Equations ( 49) and ( 51) implies that Equation (42) holds with probability at least 1 -O(n -8 ). A union bound over all α ∈ A yields that Equations ( 41), (42) ( 43) and ( 44) hold simultaneously for all α ∈ A with probability at least 1 -O(|A|n -8 ). Recalling from Equation ( 10) that |A| = O(log n) completes the proof.The results in Lemma 6 lead to Lemma 7. Lemma 7. Consider the model in Equation (1) with M ⋆ = λ ⋆ u ⋆ u ⋆⊤ and suppose that Assumptions 1, 2 and 3 hold. For each α ∈ A, letEQUATIONand define the setEQUATION)where A is as defined in Equation (10) . Let Î be the set constructed in Step 2 of Algorithm 1 with β = ϵ 0 /2. With probability at least 1 -O(n -8 log n), there exists an α ∈ A 0 such that Î = I α .Proof. We first show that with probability at least 1 -O(n -8 log n), for any α ∈ A satisfying Equations ( 15) and ( 16), we have α ∈ A 0 and Îα = I α , where Îα is as defined in Lemma 6. We then prove that there exists at least one α ∈ A 0 ⊆ A such that both Equations ( 15) and ( 16) hold. Having established this, the value α ∈ A chosen in Step 2 of Algorithm 1, which satisfies Equations ( 15) and ( 16) by definition, must be an element of A 0 ⊆ A. Since Î = Î α by definition, we must have Î = I α with probability at least 1 -O(n -8 log n), which will complete the proof.Suppose that α ∈ A satisfies Equations ( 15) and (16) . Trivially, by the definition of A 0 in Equation (53) , Equation (15) implies that α ∈ A 0 . By Lemma 6, with probability at least 1-O(n -8 log n), Equations ( 43) and ( 44) hold for all elements of A. Thus, in particular, {i : 16) and the choice β = ϵ 0 /2 in Algorithm 1,|u i | ≥ (1 + ϵ 0 /2) α} ⊆ {i : |u ⋆ i | ≥ α} ⊆ {i : |u i | > (1 -ϵ 0 /2) α} . By Equation (Îα = {i : |u i | > (1 -ϵ 0 /2)α} = {i : |u i | ≥ (1 + ϵ 0 /2)α} ,from which it follows that Îα = I α with probability at least 1 -O(n -8 log n).We now establish the existence of at least one α ∈ A 0 ⊆ A satisfying Equations ( 15) and (16) . By Assumption 2, for sufficiently large n, there exists α ∈ A such that Equation ( 12) holds, from which α ∈ A 0 immediately. Also by Assumption 2, there are no i ∈ [n] for which (41) holds with probability at least 1 -O(n -8 log n) for all elements of A 0 ⊆ A, and thus Îα = I α . Therefore, we have(1 -ϵ 0 )α ≤ |u ⋆ i | ≤ (1 + ϵ 0 )α. By Lemma 6, Equation| Îα | = |I α | ≥ (α 2 log 2 n) -1, where the lowerbound follows from Equation (12) . As a result, any such α guaranteed by Assumption 2 satisfies Equation (15) . By Equation (42) in Lemma 6 and the fact that α satisfies Assumption 2, with probability at least1 -O(n -8 log n) we have {i : (1 -ϵ 0 /2)α < |u i | < (1 + ϵ 0 /2)α} = ∅.Thus, with β = ϵ 0 /2, this particular α also satisfies Equation ( 16) and we conclude that with probability at least 1 -O(n -8 log n), there exists at least one α ∈ A 0 such that both Equations ( 15) and ( 16) hold.Our argument above ensures that with probability at least 1 -O(n -8 log n), there exists α ∈ A 0 satisfying Equations ( 15) and ( 16). Thus, α ∈ A 0 as constructed in Step 2 exists, and our argument above ensures that Î as constructed in Step 2 satisfies Î = Î α = I α , completing the proof. Lemma 8. Under Assumptions 1 and 3, with probability at least1 -O(n -8 ) it holds for all i ∈ [n] that |u ⋆ i | ≥ 1 24 √ n implies sgn (u i ) = sgn (u ⋆ i ) .Proof of Lemma 8. Let i ∈ [n] and suppose that |u ⋆ i | ≥ 1/24 √ n with u ⋆ i ≥ 0. The case for u ⋆ i < 0 follows by an analogous argument and details are omitted. By Equation (38) in Lemma 5, it holds with probability at least 1 -O(n -8 ) that for all i ∈ [n] such that u ⋆ i ≥ 0,u i ≥ u ⋆ i -|u i -u ⋆ i | ≥ 1 - 120 √ ν W n |λ ⋆ | u ⋆ i - 80 √ ν W log n |λ ⋆ | .By Assumption 3, it follows that when|λ ⋆ | ≥ 2400 √ ν W n u i ≥ 19 20 u ⋆ i - 80 √ ν W log n |λ ⋆ | . Since u ⋆ i ≥ 1/24√ n by assumption, it follows that when |λ ⋆ | ≥ 2400 √ ν W n, we haveu ⋆ i ≥ 100 √ ν W log n |λ ⋆ | ,from which we have u i > 0 and therefore sgn (u i ) = sgn (u ⋆ i ). Lemma 9. Fix α ∈ A and s ∈ {±1} n . For a random noise matrix W ∈ R n×n satisfying Assumption 1, it holds with probability at least 1 -O(n -8 ) that j,k∈IαEQUATIONandEQUATIONProof. Since s ∈ {±1} n is fixed and the entries of W are symmetric about zero, we assume without loss of generality that s is a vector of all 1's. By standard concentration inequalities [54] , we have that for any t > 0,P   j,k∈Iα W jk ≥ t   ≤ 2 exp -t 2 2|I α | 2 ν W .Setting t = C|I α | √ ν W log n for suitably-chosen C > 0, Equation ( 54) holds with probability at least 1 -O(n -8 ). Similarly, by standard subgaussian concentration inequalities [54] and a union bound over j ∈ [n], it holds for all t > 0 thatP max j∈[n] k∈Iα W jk > t ≤ 2n exp -t 2 2|I α |ν W .Taking t 2 = C|I α |ν W log n for C > 0 chosen suitably large, Equation (55) holds with probability at least 1 -O(n -8 ), completing the proof.Proof. In this proof, we control the estimation error of u under d ∞ . There are two types of entries of u, as stated in Step 5 of Algorithm 1. One type is derived from v constructed in Step 4 of Algorithm 1, and corresponds to large entries of u ⋆ . The other type is given by the top eigenvector u of Y , corresponding to small entries of u ⋆ . We handle these two types of entries separately. In Part I of the proof, we control the estimation error corresponding to the first type of entries, derived from v. In Part II of the proof, we control the estimation error corresponding to the second type of entries, derived from u. Combining these two parts, we obtain a high probability bound for the estimation error d ∞ ( u, u ⋆ ).Part I. Estimation error related to v.We define the event E 1 according toEQUATIONOn event E 1 , if λ ⋆ > 0, then by the triangle inequality, we haveEQUATIONwhere the second inequality holds for all sufficiently large n by Assumption 3. Similarly, for all sufficiently large n we have λ < 0 if λ ⋆ < 0. In other words, for all sufficiently large n, we havesgn λ = sgn (λ ⋆ )on event E 1 . Hence, Step 1 in Algorithm 1 guarantees that we work with the original Y when λ ⋆ > 0, or with -Y when λ ⋆ < 0. In either case, the algorithm proceeds with a signal matrix that has a positive leading eigenvalue on E 1 . Without loss of generality, we assume that λ ⋆ > 0.On event E 1 , we haveEQUATION)where the second inequality holds for all sufficiently large n by Assumption 3. Similarly, for n sufficiently large, following Equation (58) , event E 1 also impliesEQUATION)Recalling the set A 0 from Equation ( 53) and I α from Equation ( 52) above, for each α ∈ A 0 , define the events E 2,α and E 3,α according toEQUATION)where Î is as constructed in Step 2 of Algorithm 1, andEQUATIONDefine s ∈ {±1} n according toEQUATIONand for each α ∈ A 0 , define the event E 4,α asEQUATION)For S given in Step 4 of Algorithm 1, plugging in Y = QY Q and expanding, it follows that on the event E 2,α ∩ E 3,α ,EQUATION)On the event E 2,α ∩ E 3,α ∩ E 4,α , we can lower-bound this right-hand side, obtainingEQUATIONwhere the first inequality follows from the fact that event E 4,α holds and the second inequality follows from the definition of I α in Equation (52) . Using Equation ( 53) and the fact that α ∈ A 0 , we may further bound this byS 2 ≥ |I α | log 2 n λ ⋆ -C √ ν W log 5/2 n > 0,where the second inequality holds under Assumption 3 when n is sufficiently large. Thus, on the event E 2,α ∩ E 3,α ∩ E 4,α , we have j,k∈ Î Y jk > 0 and thus S is well-defined (i.e., it is the square root of a positive number).We now show that S is close to its population target. Rearranging the terms in Equation (64), we have that on the eventEQUATIONDividing both sides by S +EQUATIONwhere the second inequality follows from the fact that S > 0 and the last inequality follows from the definition of I α in Equation (52) . Dividing by √ λ ⋆ k∈Iα |u ⋆ k | on both sides (note that this quantity is positive by definition of I α and the fact that α ∈ A 0 ), it follows that on the eventEQUATION)where the second inequality follows from the definition of I α in Equation ( 52) and the last inequality follows from Equation (53) .We move on to Step 4 of Algorithm 1, from which we recall, for ease of reference, thatEQUATIONNote that by Equation ( 57), the square root of λ is well-defined on E 1 . Rearranging the definition of v j in Equation ( 69), plugging in Y = QY Q and expanding, we have for j ∈ [n],v j S √ λ ⋆ = λ ⋆ λ Q jj u ⋆ j k∈ Î Q kk u ⋆ k + k∈ Î Q jj Q kk W jk λλ ⋆ .Rearranging terms and adding v j k∈ Î Q kk u ⋆ k to both sides, we have for any j ∈ [n]v j -Q jj u ⋆ j k∈ Î Q kk u ⋆ k = v j   k∈ Î Q kk u ⋆ k - S √ λ ⋆   + λ ⋆ λ -1 Q jj u ⋆ j k∈ Î Q kk u ⋆ k + k∈ Î Q jj Q kk W jk λλ ⋆ .Dividing by k∈ Î Q kk u ⋆ k on both sides, again noting that this quantity is positive on the eventEQUATIONTaking absolute values in Equation ( 70) and applying the triangle inequality,v j -Q jj u ⋆ j ≤ | v j | 1 - S √ λ ⋆ k∈ Î Q kk u ⋆ k + λ ⋆ λ -1 Q jj u ⋆ j + k∈ Î Q jj Q kk W jk λλ ⋆ k∈ Î Q kk u ⋆ k .Trivially, |Q jj u ⋆ j | ≤ 1. Further, on the event E 2,α ∩ E 3,α , we have Î = I α and Q jj = sgn u ⋆ j = s j for all j ∈ I α . Thus, we may writeEQUATIONOn the event E 1 , applying Equations ( 58) and ( 59) yields thatEQUATION)Applying this bound in Equation ( 71), on the eventE 1 ∩ E 2,α ∩ E 3,α , we have v j -Q jj u ⋆ j ≤ | v j | 1 - S √ λ ⋆ k∈Iα |u ⋆ k | + C √ ν W log 5/2 n λ ⋆ + k∈Iα s j s k W jk λ ⋆ k∈Iα |u ⋆ k | λ ⋆ λ .We remind the reader that in the proof, constant C may change its precise value from line to line. Another application of Equation (72) and using Assumption 3 yields 68) holds and we havev j -Q jj u ⋆ j ≤ | v j | 1 - S √ λ ⋆ k∈Iα |u ⋆ k | + C √ ν W log 5/2 n λ ⋆ + C k∈Iα s j s k W jk λ ⋆ k∈Iα |u ⋆ k | . On the event E 1 ∩ E 2,α ∩ E 3,α ∩ E 4,α , Equation (EQUATION)Define the eventEQUATIONUnder the event E 1 ∩ E 2,α ∩ E 3,α ∩ E 4,α ∩ E 5,α , we can further bound Equation (73) byv j -Q jj u ⋆ j ≤ | v j | C √ ν W log 5/2 n λ ⋆ + C √ ν W log 5/2 n λ ⋆ + C |I α |ν W log n λ ⋆ |I α |α .Applying the definition of A 0 in Equation ( 53), on the eventEQUATION)Applying the triangle inequality and using the fact that |Q jj u ⋆ j | ≤ 1 by definition,(| v j | + 1) C √ ν W log 5/2 n λ ⋆ ≤ | v j -Q jj u ⋆ j | C √ ν W log 5/2 n λ ⋆ + |Q jj u ⋆ j | + 1 C √ ν W log 5/2 n λ ⋆ ≤ | v j -Q jj u ⋆ j | C √ ν W log 5/2 n λ ⋆ + C √ ν W log 5/2 n λ ⋆ .Applying this bound to Equation (75),v j -Q jj u ⋆ j ≤ | v j -Q jj u ⋆ j | C √ ν W (log n) 5/2 λ ⋆ + C √ ν W (log n) 5/2 λ ⋆ .Rearranging the terms, under Assumption 3 for n sufficiently large and when the eventEQUATIONRecall from Step 5 of Algorithm 1 that we set u j = Q jj v j for all j ∈ [n] such that |u j | > (σ/ λ) log n.For any such j, on the event E 1 ∩ E 2,α ∩ E 3,α ∩ E 4,α ∩ E 5,α , Equation (76) holds, and we haveEQUATION)Consider the eventE = ∥Q v -u ⋆ ∥ ∞ ≤ C √ ν W log 5/2 n λ ⋆ .Recalling the events E 1 , E 2,α , E 3,α , E 4,α and E 5,α defined in Equations (56) (60) (61) ( 63) and (74), respectively, we haveEQUATIONwhere the last equality holds because for any α ∈ A 0 , the event E is implied by the eventE 1 ∩ E 2,α ∩ E 3,α ∩ E 4,α ∩ E 5,α, which is a fact established in the proof of Equations ( 76) and (77).Since by the definition in Equation ( 60), {E 2,α } α∈A0 are disjoint, it follows from Equation (78) thatEQUATIONBy the union bound and basic set inclusions,P (E 1 ∩ E 2,α ∩ (E 3,α ∩ E 4,α ∩ E 5,α ) c ) = P E 1 ∩ E 2,α ∩ E c 3,α ∪ E c 4,α ∪ E 5,α ) c ≤ P E 1 ∩ E 2,α ∩ E c 3,α + P E 1 ∩ E 2,α ∩ E c 4,α + P E 1 ∩ E 2,α ∩ E c 5,α ≤ P E 2,α ∩ E c 3,α + P E c 4,α + P E c 5,α .Applying this bound in Equation (79),EQUATIONThe terms P(E c 4,α ) and P(E c 5,α ) are bounded in Lemma 9 asEQUATIONFor the term P(E 2,α ∩ E c 3,α ), we haveP(E 2,α ∩ E c 3,α ) = P   k∈Iα Q kk ̸ = sgn (u ⋆ k ) , Î = I α ∪ k∈I c α Q kk ̸ = 1, Î = I α   .By Step 3 in Algorithm 1, we must havek∈I c α Q kk ̸ = 1, Î = I α = k∈ Îc Q kk ̸ = 1, Î = I α = ∅.It follows thatEQUATIONFor any k ∈ I α , by the construction of A in Equation ( 10), we must have |u ⋆ k | ≥ α ≥ 1/ √ 2n. Thus, by Lemma 8, we can further bound Equation (82) asEQUATIONApplying Equations ( 81) and (83) to Equation (80), we haveP(E) ≥ α∈A0 P (E 1 ∩ E 2,α ) -O(|A 0 |n -8 ) = 1 -P E c 1 ∪ α∈A0 E c 2,α -O(|A 0 |n -8 ) ≥ 1 -P(E c 1 ) -P α∈A0 Î ̸ = I α -O(|A 0 |n -8 ).Under Assumption 4, we have P(E c 1 ) ≤ O(n -8 log n), and it follows thatP(E) ≥ 1 -O(n -8 log n) -P α∈A0 Î ̸ = I α -O(|A 0 |n -8 ).Applying Lemma 7 to the right hand side yields thatP(E) ≥ 1 -O(n -8 log n) -O(n -8 ) -O(|A 0 |n -8 ) ≥ 1 -O(n -8 log n),where the last inequality follows from the fact that |A 0 | ≤ |A| and |A| = O(log n) by Equation (10) .At this stage, we have shown that with probability at least 1 -O(n -8 log n),EQUATION)Part II. Estimation error related to u.Step 5 in Algorithm 1 further refines v to adjust the estimates of small entries of u ⋆ . In the remainder of the proof, we show that this refinement does not affect our bound in Equation (84). By Lemma 5, it holds with probability at least 1 -O(n -8 ) that for all j ∈ [n],|u j -u ⋆ j | ≤ 80 √ ν W log n + 120 √ ν W n u ⋆ j λ ⋆ ≤ 80 √ ν W log n λ ⋆ + 120 √ ν W n λ ⋆ |u j | + u j -u ⋆ j ,where the second line follows from the triangle inequality. Rearranging terms and noting that λ ⋆ > 240 √ ν W n log n under Assumption 3, we have that with probability at least 1 -O(n -8 ), it holds for all j ∈ [n] that|u j -u ⋆ j | ≤ 1 1 -120 √ ν W n/λ ⋆ 80 √ ν W log n λ ⋆ + 120 √ ν W n λ ⋆ |u j | ≤ 160 √ ν W log n λ ⋆ + |u j | √ log n .That is, defining the eventEQUATIONwe haveEQUATIONNote that by Equation ( 58) and Assumption 3, when E 1 holds, we have |λ ⋆ / λ| ≤ 2 for sufficiently large n. It follows that when E 1 holds, for all j ∈ [n] such that |u j | ≤ ( √ ν W / λ) log n, we haveEQUATION)where the inequality follows from Equation (58) . Define the set Ĵ = {j : |u j | ≤ ( √ ν W / λ) log n}.We haveP   j∈ Ĵ |u j -u ⋆ j | > 162 √ ν W log n λ ⋆   ≤ P   j∈ Ĵ |u j -u ⋆ j | > 162 √ ν W log n λ ⋆ ∩ E 1   + P(E c 1 ) ≤ P   j∈ Ĵ |u j -u ⋆ j | > 160 √ ν W log n λ ⋆ + |u j | √ log n ∩ E 1   + O(n -8 ),where the second inequality follows from Equation (87) and Assumption 4. Recalling the definition of E 6 in Equation (85) and using the fact that Ĵ ⊆ [n], we have that the set in the last inequality of the above display is a subset of E c 6 . Following the above bound and basic set inclusions, we haveP   j∈ Ĵ |u j -u ⋆ j | > 162 √ ν W log n λ ⋆   ≤ P(E c 6 ) + O(n -8 ) ≤ O(n -8 ).Combining this with Equation (84) and recalling the definition of u in Step 5, we have that with probability at least 1 -O(n -8 ), d ∞ ( u, u ⋆ ) ≤ C √ ν W logEQUATIONProof. Since s ∈ {±1} n is fixed and the entries of W are symmetric about zero, without loss of generality, we assume that s is a vector of all 1's. Reindexing if necessary, we assume without loss of generality that I α = [K], where K = |I α | > 0. We have K > 0 since α ∈ A 0 and by the definition of A 0 in Equation (53) ,EQUATIONwhereγ 1 := n j=K+1 K k=1 W 2 jk + K k=1 W 2 kk + 2 1≤j<k≤K W 2 jk -nKσ 2 , γ 2 := 2 n j=K+1 1≤k<ℓ≤KW jk W jℓ andγ 3 := K j=1 1≤k̸ =ℓ≤K W jk W jℓ .We will bound these three quantities separately.We begin by bounding γ 1 in Equation (90). For ease of notation, define N = K(n -K/2 + 1/2). γ 1 is a sum of N independent sub-exponential random variables. By Equation (2.18) in [56] , for any t ∈ (0, 2),P |γ 1 | N ≥ ν W t ≤ 2e -N t 2 /32 .Taking t = 16 N -1 log n yields that for all suitably large n, with probability at least 1 -O(n -8 ),EQUATIONwhere the second inequality follows from the trivial bound N ≤ Kn.Turning to γ 2 in Equation (90), defineA = 1 K 1 ⊤ K -I K ∈ R K×K, where 1 K ∈ R K is a vector of all 1's and I K is the K × K identity matrix. It follows thatγ 2 = n j=K+1 1≤k̸ =ℓ≤K W jk W jℓ = n j=K+1 1≤k,ℓ≤K W jk A kℓ W jℓ .By the Hanson-Wright inequality (see Theorem 6.2.1 in [54] ), for t ≥ 0, we haveP   n j=K+1 1≤k,ℓ≤K W jk A kℓ W jℓ ≥ t   ≤ 2 exp -c min t 2 (n -K)ν 2 W ∥A∥ 2 F , t √ n -Kν W ∥A∥ F ,where c > 0 is a universal constant. We note that ∥A∥ F ≤ K 2 by construction. Taking t = (8ν W /c)K √ n -K log n, with probability at least 1 -O(n -8 ) we haveEQUATIONFinally, to bound γ 3 in Equation (90), we definew = vech([W ij ] 1≤i,j≤K ) ∈ R K(K+1)/2 ,where vech(•) is the half-vectorization operator that vectorizes the upper triangular part (including the diagonal) of a given matrix.We identify the elements of w with the elements ofJ K = {(i 1 , i 2 ) : 1 ≤ i 1 ≤ i 2 ≤ K} , that is, pairs (i 1 , i 2 ) satisfying 1 ≤ i 1 ≤ i 2 ≤ K.We note that γ 3 is a sum of products of the form w (i1,i2) w (j1,j2) such that (i 1 , i 2 ), (j 1 , j 2 ) ∈ J K and one element of (i 1 , i 2 ) agrees with one element of (j 1 , j 2 ), while the others disagree. For (i 1 , i 2 ) ∈ J K with i 1 < i 2 , there are 2(K -1) other pairs (j 1 , j 2 ) ∈ J K satisfying this requirement, while for (i 1 , i 2 ) ∈ J K with i 1 = i 2 , there are (K -1) other elements of J K satisfying the requirement. In total, there are K 2 (K -1) such pairs, which agrees with the number of terms in γ 3 . We define matrix B ∈ R K(K+1)/2×K(K+1)/2 by identifying its rows and columns with elements of J K and settingB (i1,i2),(j1,j2) = max {δ i1j1 (1 -δ i2j2 ), δ i1j2 (1 -δ i2j1 ), δ i2j1 (1 -δ i1j2 ), δ i2j2 (1 -δ i1j2 )} for (i 1 , i 2 ), (j 1 , j 2 ) ∈ J K , where δ ij = 1 if i = j, 0 otherwise.There are K 2 (K -1) entries in B that are equal to 1, while all others are equal to zero. Thus, we have∥B∥ F = K √ K -1 ≤ K 3/2. By construction, one can verify thatw ⊤ Bw = (i1,i2)∈J (j1,j2)∈J w (i1,i2) B (i1,i2),(j1,j2) w (j1,j2) = K j=1 1≤k̸ =ℓ≤K W jk W jℓ = γ 3 .Again, by the Hanson-Wright inequality, for every t ≥ 0, we haveP w ⊤ Bw ≥ t ≤ 2 exp -c min t 2 ν 2 W ∥B∥ 2 F , t ν W ∥B∥ F ,where c > 0 is a universal constant. Taking t = (8ν W /c)∥B∥ F log n yields that with probability at least 1 -O(n -8 ),EQUATIONwhere the second inequality follows from our bound on ∥B∥ F .Finally, plugging the bounds in Equations (91) (92) and (93) into Equation (90), we have that with probability at least 1 -O(n -8 ), Equation (89) holds, as we set out to show.Lemma 11. Under Assumption 1, for any fixed s ∈ {±1} n and any fixed u ⋆ ∈ S n-1 , for any α ∈ A, it holds with probability at least1 -O(n -8 ) that k∈Iα n j=1 u ⋆ j s k W jk ≤ 4 2ν W |I α | log n.Proof. Since s ∈ {±1} n is fixed and the entries of W are symmetric about zero, without loss of generality, we assume that s is a vector of all 1's. Reindexing if necessary, we again assume that I α = [K] without loss of generality, where K = |I α |. Rearranging sums, we haveK k=1 n j=1 u ⋆ j s k W jk = K k=1 n j=1 u ⋆ j W jk = K j=1 K k=j+1 (u ⋆ j + u ⋆ k )W jk + K j=1 u ⋆ j W jj + K k=1 n j=K+1 u ⋆ j W jk .By standard subgaussian concentration inequalities [54, 56] , using the fact that u ⋆ is unit-norm,P   K k=1 n j=1 u ⋆ j s k W jk ≥ 4 ν W 2K log n   ≤ O(n -8 ),completing the proof.Proof. Similar to the proof of Theorem 1, we assume that λ ⋆ > 0 without loss of generality. Recalling the quantity S as defined in Step 4 of Algorithm 1 and the fact that S > 0 from Equation (65), we defineEQUATIONwhere we recall that Î is the set given in Step 2 of Algorithm 1 and Q ∈ R n×n is a diagonal matrix given in Step 3 of Algorithm 1.Plugging in Y = QY Q and expanding the right hand side of Equation ( 88), we haveλ = 1 S 2    n j=1   λ ⋆ Q jj u ⋆ j k∈ Î Q kk u ⋆ k + k∈ Î Q jj Q kk W jk   2    - n| Î|σ 2 S 2 = 1 S 2 n j=1 (λ ⋆ u ⋆ j ) 2   k∈ Î Q kk u ⋆ k   2 + 1 S 2 n j=1   k∈ Î Q kk W jk   2 + 2λ ⋆ S 2 n j=1   u ⋆ j k∈ Î Q kk u ⋆ k ℓ∈ Î Q ℓℓ W jℓ   - n| Î|σ 2 S 2 .Applying the definition of R Î in Equation ( 94) and rearranging terms,EQUATION)To control the term R Î in Equation ( 95), we proceed to bound a related term R α for all α ∈ A 0 , defined asR α = √ λ ⋆ k∈Iα |u ⋆ k | S .We recall the events E 2,α , E 3,α and E 4,α for all α ∈ A 0 as defined in Equations ( 60), ( 61) and ( 63) in the proof of Theorem 1. For any α ∈ A 0 , to control the term R α , we divide S on both sides of Equation ( 67) stated in the proof of Theorem 1. It follows from Equation (67) that|R α -1| = √ λ ⋆ k∈Iα |u ⋆ k | S -1 ≤ C √ ν W log n α √ λ ⋆ S holds on the event E 2,α ∩ E 3,α ∩ E 4,α .Following the previous bound, on the event E 2,α ∩ E 3,α ∩ E 4,α , we have that|R α -1| ≤ C √ ν W log n α √ λ ⋆ S ≤ C √ ν W log n αλ ⋆ k∈Iα |u ⋆ k | -α √ λ ⋆ S - √ λ ⋆ k∈Iα |u ⋆ k | ≤ C √ ν W log n λ ⋆ |I α |α 2 -C √ ν W log n ≤ C √ ν W log 5/2 n λ ⋆ -C √ ν W log 5/2 n ,where the second inequality holds by the triangle inequality, the third inequality follows from Equations ( 66) and ( 52), the last inequality holds by Equation (53) . We remind the reader that we allow constant C to change its precise value from line to line in the proof. Under Assumption 3, it follows from the previous bound that for n sufficiently large, we have on the eventEQUATION)By Equation (96) and Assumption 3, for n sufficiently large, we have1/2 ≤ R α ≤ 2 (97) on the event E 2,α ∩ E 3,α ∩ E 4,α .Recall s ∈ {±1} n as defined in Equation ( 62). On the event E 2,α ∩ E 3,α ∩ E 4,α , we find that, using Equation (95) to substitute for λ and applying the triangle inequality,λ -λ ⋆ ≤ λ ⋆ R 2 α -1 + R 2 α n j=1 k∈Iα s k W jk 2 -n|I α |σ 2 √ λ ⋆ k∈Iα |u ⋆ k | 2 + 2R 2 α n j=1 u ⋆ j k∈Iα s k W jk k∈Iα |u ⋆ k |, where we substitute R Î by R α using the fact that on E 2,α , we have Î = I α . Continuing from the previous bound, it follows from Equation (96) thatλ -λ ⋆ ≤ λ ⋆ • C √ ν W log 5/2 n λ ⋆ • |R α + 1| + R 2 α n j=1 k∈Iα s k W jk 2 -n|I α |σ 2 √ λ ⋆ k∈Iα |u ⋆ k | 2 + 2R 2 α n j=1 u ⋆ j k∈Iα s k W jk k∈Iα |u ⋆ k | .Applying Equation (97) to R α in the above display, we haveEQUATION)For all α ∈ A 0 , define the eventsEQUATION)On the eventE 2,α ∩ E 3,α ∩ E 4,α ∩ G 1,α ∩ G 2,α, we can further bound Equation ( 98) according toλ -λ ⋆ ≤ C √ ν W log 5/2 n + Cν W |I α | √ n log n √ λ ⋆ k∈Iα |u ⋆ k | 2 + C ν W |I α | log n k∈Iα |u ⋆ k |, following the definition of G 1,α and G 2,α in Equation ( 99). By the definition of I α in Equation ( 52), it follows thatEQUATIONholds on the event E 2,α ∩E 3,α ∩E 4,α ∩G 1,α ∩G 2,α , where the last inequality holds under Assumption 3 when n is sufficiently large.Consider the eventG = λ -λ ⋆ ≤ C √ ν W log 5/2 n .By the proof leading to Equation (100), we have for allα ∈ A 0 , E 2,α ∩ E 3,α ∩ E 4,α ∩ G 1,α ∩ G 2,α ⊆ G. It follows that P(G) ≥ P α∈A0 E 2,α ∩ E 3,α ∩ E 4,α ∩ G 1,α ∩ G 2,α = α∈A0 P (E 2,α ∩ E 3,α ∩ E 4,α ∩ G 1,α ∩ G 2,α ) ,where the first inequality follows from set inclusion and the last equality follows from the fact that {E 2,α } α∈A0 are disjoint events according to Equation (60) . By basic set inclusions, it follows thatP(G) ≥ α∈A0   P(E 2,α ) -P(E 2,α ∩ E c 3,α ) -P(E c 4,α ) - 2 j=1 P(G c j,α )   .Applying Lemma 9, Equations (83), Lemma 10 and Lemma 11 to the above display yields thatP(G) ≥ α∈A0 P(E 2,α ) -O(|A 0 |n -8 ) = 1 -P α∈A0 Î ̸ = I α -O(|A 0 |n -8 ).Applying Lemma 7 and using the fact that |A 0 | ≤ |A| and |A| = O(log n) by its definition in Equation ( 10), we haveP(G) ≥ 1 -O(n -8 ) -O(|A 0 |n -8 ) ≥ 1 -O(n -8 log n), completing the proof.To prove Lemma 4, we first state a few technical lemmas.For a semi-metric ρ defined over a set K, we let N (K, ρ, δ) denote the δ-covering number of K under ρ (see Chapter 15 in [56] ). The collection of all linear subspaces of fixed dimension r of the Euclidean space R n forms the Grassmann manifold G n,r , also termed the Grassmannian. For points on the Grassmannian, we adopt the projector perspective [13] : a subspace U ∈ G n,r is identified with the (unique) orthogonal projector P ∈ R n×n onto U, which in turn is uniquely represented by P = U U T , where U ∈ R n×r whose columns form an orthonormal basis of U. For any matrix A ∈ R m×n with singular values denoted by σ i (A) for 1 ≤ i ≤ min{m, n}, the Schatten-q norm ∥ • ∥ Sq is defined for any1 ≤ q ≤ ∞ ∥A∥ Sq :=   min{m,n} i=1 σ q i (A)   1/q .For a pair of subspaces U 1 , U 2 ∈ G n,r identified with projectorsEQUATION)Lemma 12 controls the covering number of G n,r under d Sq .Lemma 12 ([46] Proposition 8). For any integer 1 ≤ r ≤ n such that 2r ≤ n, any q such that 1 ≤ q ≤ ∞ and any δ > 0, we havec 0 δ r(n-r) ≤ N (G n,r , d Sq , δr 1/q ) ≤ C 0 δ r(n-r)where c 0 , C 0 > 0 are universal constants, d Sq is the distance defined in Equation (101) induced by the Schatten-q norm.Let V n,r := {U ∈ R n×r : U ⊤ U = I r } be the n × r Stiefel manifold [16] . The distance d Sq (•, •) can also be viewed as a distance defined on V n,r . For a pair of orthogonal matricesU 1 , U 2 ∈ V n,r , we let d Sq (U 1 , U 2 ) := ∥U 1 U ⊤ 1 -U 2 U ⊤ 2 ∥ Sq . When q = 2, the Schatten-q norm coincides with the Frobenius norm, and we haveEQUATION)Lemma 13 controls the covering number of V n,r under d F , which follows immediately from Lemma 12. Lemma 13. For any integer 1 ≤ r ≤ n/2 and for every δ > 0, we havec 0 √ r δ r(n-r) ≤ N (V n,r , d F , δ) ≤ C 0 √ 2r δ r(n-r), where c 0 , C 0 > 0 are universal constants and d F is the Proof of Lemma 13. We identify each element U of V n,r with the element U U ⊤ in G n,r and apply Lemma 12 to V n,r under d F . By the fact that (see Lemma 2.6 in [27] )1 √ 2 U 1 U ⊤ 1 -U 2 U ⊤ 2 F ≤ d F (U 1 , U 2 ) ≤ U 1 U ⊤ 1 -U 2 U ⊤ 2 F, we haveN (V n,r , d S2 , δ) ≤ N (V n,r , d F , δ) ≤ N V n,r , d S2 , δ √ 2 and it follows from Lemma 12 that c 0 √ r δ r(n-r) ≤ N (V s,r , d F , δ) ≤ C 0 √ 2r δ r(n-r), completing the proof.For any s ≥ r, Lemma 14 relates the packing number of any subset K ⊆ V s,r to its Haar measure and the covering number of V s,r . Recall that the Haar measure on V s,r is the invariant measure under both left-and right-orthogonal transformation [29] . In other words, for any subset K ⊆ V s,r and orthogonal matrices Γ 1 ∈ O s and Γ 2 ∈ O r , we haveξ H (Γ 1 • K) = ξ H (K) and ξ H (K • Γ 2 ) = ξ H (K) ,whereΓ 1 • K := {Γ 1 U : U ∈ K} and K • Γ 2 := {U Γ 2 : U ∈ K} .For any norm |||•||| defined over a set K, we also use the notation M(K, |||•|||, δ) and N (K, |||•|||, δ) to denote the δ-packing number and δ-covering number of K under the distance induced by |||•|||, respectively. With the above setup, we state Lemma 14 below. Lemma 14. For 1 ≤ r ≤ s, let ξ H denote the Haar measure on V s,r . For 1 ≤ r ≤ s and any K ⊆ V s,r such that ξ H (K) ≥ γ > 0, for any unitarily invariant norm |||•||| on R s×r , we haveEQUATIONandEQUATION)Proof of Lemma 14. The bound in Equation (104) follows from the fact that K ⊆ V s,r , and (see Exercise 4.2.10 in [54] ),M K, |||•|||, δ 2 ≤ N K, |||•|||, δ 4 ≤ N V s,r , |||•|||, δ 8 .To establish the bound in Equation ( 103), suppose that V s,r has a δ-packing setP = {U (i) } M i=1 under |||•|||, then M i=1 B U (i) , |||•|||, δ 2 ⊆ V s,rwhereB U (i) , |||•|||, δ 2 := U ∈ V s,r : U -U (i) ≤ δ/2 .Since P is a δ-packing set, the sets B U (i) , |||•|||, δ/2 for i = 1, 2, . . . , M are disjoint and we haveEQUATION)For any U , U ∈ V s,r , there existsΓ ∈ O s such that ΓU = U . Since |||•||| is invariant under O s , we have Γ • B U , |||•|||, δ 2 = B ΓU , |||•|||, δ 2 = B U , |||•|||, δ 2 .Since ξ H is invariant under left-orthogonal transformation, it follows thatξ H B U , |||•|||, δ 2 = ξ H Γ • B U , |||•|||, δ 2 = ξ H B U , |||•|||, δ 2 . Since L = r i=1 U ∈ V s,r : ∥U •,i ∥ ∞ ≥ µ n , it follows that ξ H (L) ≤ r ξ H U ∈ V s,r : ∥U •,1 ∥ ∞ ≥ µ n .Since U is distributed according to the Haar measure on V s,r , the column U •,1 ∈ R s is uniformly distribution on S s-1 . As a result, we haveξ H U ∈ V s,r : ∥U •,1 ∥ ∞ ≥ µ n = P ∥g∥ ∞ ∥g∥ 2 ≥ µ n ,where g ∼ N (0, I s ) (see Lemma 10.1 in [44] ). Combining the above two displays,EQUATIONWe introduce two eventsE 0,1 := ∥g∥ 2 2 ≥ 3n µ log s and E 0,2 := ∥g∥ ∞ ≤ 3 log s .By Lemma 10.2 in [44] , we have for all t > 0P ∥g∥ 2 2 ≤ s -2 √ st ≤ exp (-t) .Taking t = 2 log s yields thatP ∥g∥ 2 2 ≤ s -2 2s log s ≤ 1 s 2 . When n ≥ 4µ and s ≥ (12n/µ) log (12n/µ), one can verify that s -2 2s log s ≥ s/2 ≥ 3n µ log s.Thus, it follows thatEQUATION)By standard Gaussian concentration inequalities and the union bound, we haveEQUATION)On the event E 0,1 ∩ E 0,2 , one has∥g∥ ∞ ∥g∥ 2 ≤ √ 3 log s 3n log s/µ = µ n .Combining Equations (108) and Equations (109), it follows thatP ∥g∥ ∞ ∥g∥ 2 ≥ µ n ≤ P E c 0,1 ∪ E c 0,2 ≤ 3 s 2 .Applying this bound to Equation (107), we obtainEQUATION)By the assumption that n/µ ≥ max{4, r}, for any r ≥ 1 we have s ≥ (12n/µ) log(12n/µ) > 12r > √ 6r. Combining the above bound with Equation (110), we haveξ H (L) ≤ 1 2 .Finally, applying this upper bound to Equation (106), we haveξ H (K(s, r, µr/n)) ≥ 1 -ξ H (L) ≥ 1 2 ,as desired.Proof. Set s = c 2 0 r/8e 2 δ 2 . Under our upper bound assumption on δ in Equation ( 21) and n/µ ≥ max{4, r}, we haveEQUATIONso that we always haveEQUATION)Note that owing to our assumptions that µ ≥ 12 log(12n) and δ 2 ≥ c 2 0 r/8e 2 n, we have s ≤ n. Consider the subsetK s (n, r, µr/n) := {U ∈ K r,µ : U i,• = 0, for s + 1 ≤ i ≤ n} ,which is a subset related (but different) to K(s, r, µr/n) previously considered in Lemma 15. Our lower bound relies on the key observation thatEQUATIONwhere the first inequality follows from Exercise 4.2.10 in [54] , and the second inequality follows from the fact that for any U 1 , U 2 ∈ K s (n, r, µr/n), we haved 2,∞ (U 1 , U 2 ) ≥ 1 √ s d F (U 1 , U 2 ).Starting from Equation (113), we proceed to obtain a √ sδ-packing for K s (n, r, µr/n) under d F . Since any U ∈ K s (n, r, µr/n) can be uniquely identified with an element in K(s, r, µr/n) by restricting it to its first s rows. By the assumption that n/µ ≥ max{4, r} and the lower bound on s in Equation ( 111), we verify that the conditions of Lemma 15 are all satisfied. Thus, following directly from the lower bound of ξ H (K(s, r, µr/n)) in Lemma 15 and Lemma 14, we haveM K s (n, r, µr/n), d F , 2 √ sδ ≥ 1 2 N V s,r , d F , 4 √ sδ .Applying the lower bound in Lemma 13 to the right hand side of the above bound, we haveEQUATIONUnder our upper bound assumption on δ in Equation ( 21) and n/µ ≥ max{4, r},c 2 0 r 384e 2 δ 2 ≥ c 2 0 r 384e 2 • 96e 2 n log(12n/µ) c 2 0 µr = n 4µ log(12n/µ) ≥ 1,from our choice of s, it follows thats ≤ c 2 0 r 8e 2 δ 2 + 1 ≤ c 2 0 r 8e 2 δ 2 + c 2 0 r 384e 2 δ 2 ≤ c 2 0 r 7e 2 δ 2 , which implies √ sδ ≤ ( √ 7e) -1 c 0 √ r. Thus, it follows from Equation (114) that M K s (n, r, µr/n), d F , 2 √ sδ ≥ 1 2 √ 7e 4 r(s-r) ≥ 1 2 √ 7e 4 rs 2, where the last inequality follows from Equation (111). Noting that √ 7e/4 ≥ √ e, we haveEQUATIONApplying Equation (113) followed by Equation (112), we obtainEQUATION)Taking the logarithm on both sides of the above display yields Equation (22) .To provide a complete picture, Lemma 16 establishes an upper bound on the packing δ-entropy of K r,µ under d 2,∞ that matches the lower bound in Lemma 4 up to log-factors when δ satisfies Equation (21) . Lemma 16. Assume that n ≥ µr for r ∈ [n] and µ > 0. For all n sufficiently large and any 4/(n -1) < δ < µr/n, we haveEQUATIONProof of Lemma 16. We obtain an upper bound of M(K r,µ , d 2,∞ , δ) by finding an upper bound ofN (K r,µ , d 2,∞ , δ). Since for any U 1 and U 2 ∈ R n×r , d 2,∞ (U 1 , U 2 ) ≤ ∥U 1 -U 2 ∥ 2,∞ , we have N (K r,µ , d 2,∞ , δ) ≤ N (K r,µ , ∥ • ∥ 2,∞ , δ) .(117) Thus, it suffices to obtain an upper bound forEQUATIONFor any U ∈ K r,µ , noting that µr/n ≤ 1, we define a mapping h : K r,µ → T given byh(U ) := (∥U 1,• ∥ 2 , ∥U 2,• ∥ 2 , • • • , ∥U n,• ∥ 2 ) ⊤ . Indeed, h(U ) ∈ T since by definition, we have h(U ) ≥ 0, ∥h(U )∥ 2 = √ r and ∥h(U )∥ ∞ ≤ 1.We pause to give a roadmap of our proof. Recall that for a set K, its exterior δ-covering is a δ-covering, except that the exterior δ-covering allows elements not in K to form the covering (see Exercise 4.2.9 in [54] ). To obtain N (K r,µ , ∥ • ∥ 2,∞ , δ), we will explicitly construct an exterior δ-covering of K r,µ under ∥ • ∥ 2,∞ . To do so, we proceed in three steps. In the first step, we construct an exterior δ-covering C of T under ∥ • ∥ ∞ . In the second step, we divide the set K r,µ into separate subsets {U v } v∈T via the mapping h : K r,µ → T. In this way, each element v in T is associated with a subset U v ⊆ K r,µ . For every v ∈ C (the exterior (δ/2)-covering set of T), we construct an exterior(δ/2)-covering C v of U v under ∥ • ∥ 2,∞ .In the last step, we take the union of C v over v ∈ C to form a set C K , and show this set is an exterior δ-covering set for K r,µ under ∥ • ∥ 2,∞ . Finally, we control the cardinality of C K to obtain an upper bound of N (K r,µ , ∥ • ∥ 2,∞ , δ), which in turn will yield our desired upper bound on M(K r,µ , d 2,∞ , δ).Step 1. Construct an exterior (δ/2)-covering set of T under ∥ • ∥ ∞ .Recall that T is given in Equation (118). Let s = ⌈4/δ 2 ⌉. Under the assumption that δ > 4/(n -1), we have s ≤ n. We consider the nonnegative integer solutions to the indeterminate equationEQUATIONEQUATIONBy Lemma 17, we have C forms an exterior δ/2-covering set of T under ∥ • ∥ ∞ . Since without the constraint ∥z∥ ∞ ≤ s + 1, Equation (119) has n+rs-1 rs solutions, we haveEQUATION)Step 2. Construct an exterior (δ/2)-covering set ofU v under ∥ • ∥ 2,∞ .For a given v ∈ C , consider the subsetEQUATIONour next step is to construct an exterior (δ/2)-covering set under ∥ • ∥ 2,∞ for U v . For every i ∈ [n], consider a (δ/2)-covering set C vi of v i S r-1 under the ℓ 2 norm. By Corollary 4.2.13 in [54] ,EQUATIONConsider the setEQUATIONWe claim that C v is an exterior (δ/2)-covering set for U v under ∥ • ∥ 2,∞ . To see this, note that for any U ∈ U v and any i ∈[n], since U ⊤ i,• ∈ v i S r-1 and C vi is a (δ/2)-covering of v i S r-1 under the ℓ 2 norm, there exists a θ i ∈ C vi such that θ i -U ⊤ i,• 2 ≤ δ 2 , for all i ∈ [n]. Let Θ = (θ 1 , θ 2 , . . . , θ n ) ⊤ ∈ C v . It follows that ∥Θ -U ∥ 2,∞ = max i∈[n] ≤ θ i -U ⊤ i,• 2 ≤ δ 2 .Since v ∈ C , from Equation (119), we haveEQUATIONas any solution z to Equation (119) has at most rs nonzero entries. By Equations ( 119) and (120), we also haveEQUATIONBy Equations ( 123) and (124),|C v | ≤ n i=1 6v i δ r = i:vi>0 6v i δ r ≤ 12 δ sr 2.where the last inequality follows from Equations ( 125) and (126). By the choice of s = ⌈4/δ 2 ⌉, we haveEQUATION)Step 3. Construct an exterior δ-covering set for K r,µ under ∥ • ∥ 2,∞ .Consider the setEQUATIONwe claim that this set forms an exterior δ-covering set for K r,µ under ∥ • ∥ 2,∞ .For anyU ∈ K r,µ , since C is an exterior (δ/2)-covering of T under ∥ • ∥ ∞ , we can find v ∈ C such that ∥h(U ) -v∥ ∞ ≤ δ/2.Consider a matrix U ∈ R n×r with rows given byU i,• = v i U i,• /h i (U ) if h i (U ) > 0, θ ⊤ i if h i (U ) = 0, for all i ∈ [n], where θ i is an arbitrary element of C vi . Recall the definition of U v from Equation (122). By construction, U ∈ U v , which implies that there existsΘ ∈ C v ⊆ C K such that Θ -U 2,∞ ≤ δ 2 ,where we use the fact that C v defined in Equation ( 124) is an exteriorEQUATIONProof. The inequality 1/ √ s ≤ δ/2 in Equation ( 130) follows directly from s = 4/δ 2 . To construct a v ∈ C satisfying Equation (130), we first construct a ζ ∈ R n and then make a slight modification to ζ to obtain v.To construct ζ, we set ζ 2 1 to be either h 2 1 s /s or h 2 1 s /s, and follow the recursive procedure to obtain an entrywise positive ζ ≥ 0:EQUATIONfor 2 ≤ i ≤ n. The construction given in Equation ( 131) guarantees thatEQUATIONwhere the last inequality follows from the fact that √ a -√ b ≤ √ a -b for any a ≥ b > 0. Now we show that following the procedure in Equation ( 131), we haveEQUATIONfor all k ∈ [n]. We prove the above bound by induction on k ∈ [n]. When k = 1, we trivially haveζ 2 1 -h 2 1 ≤ 1 s .For the inductive step, suppose that for k > 1, we havek-1 i=1 h 2 i - k-1 i=1 ζ 2 i ≤ 1 s .By definition in Equation ( 131), ifEQUATION- 1 s ≤ k-1 i=1 h 2 i - k-1 i=1 ζ 2 i + h 2 k - h 2 k s s ≤ 1 s . Thus, ζ 2 k = h 2 k s /s satisfies k i=1 h 2 i - k i=1 ζ 2 i ≤ 1 s .If, contrary to Equation (134), we have EQUATION⌈h 2 i s⌉ ≤ s + 1,where the last inequality follows from ∥h∥ ∞ ≤ 1 for all h ∈ T, we see that v ∈ C .In this section, we use the Yang-Barron method [59] along with a Fano lower bound (see Proposition 15.12 and Lemma 15.21 in [56] ) to prove the minimax lower bound for eigenspace estimation stated in Theorem 2. We follow the notation used in [56] . Given a class of distributions P, we let θ denote a functional on the space P, that is, a mapping from a distribution P to a parameter θ(P) taking values in some space Ω. We let ρ : Ω × Ω → [0, ∞) be a semi-metric. Proposition 2 states the Fano lower bound (Proposition 15.12 in [56] ). Proposition 2 (Fano lower bound). Let {θ 1 , θ 2 , . . . , θ M } ⊆ Ω be a 2δ-separated set under the ρ semimetric, and suppose that J is uniformly distributed over the index set [M ], and (Z | J = j) ∼ P θj . Then for any increasing function Φ : [0, ∞) → [0, ∞), the minimax risk is lower bounded asinf θ sup P∈P E P Φ ρ θ, θ(P) ≥ Φ(δ) 1 - I(Z; J) + log 2 log M ,where the infimum is over all estimators θ and I(Z; J) is the mutual information between Z and J.The Yang-Barron method gives an upper bound for the mutual information I(Z; J). Lemma 18 (Yang-Barron method [59] ). Let N KL (ε; P) denote the ε-covering number of P in the square-root KL-divergence. Then the mutual information is upper bounded asI(Z; J) ≤ inf ε>0 log N KL (ε; P) + ε 2 .Proof of Theorem 2. To each (Λ ⋆ , U ⋆ ) ∈ Ω(λ ⋆ , µ, r), we associate a probability distribution P Λ ⋆ ,U ⋆ on R n×n with density given byf Λ ⋆ ,U ⋆ (W ) = 1≤i≤j≤n g (W -U ⋆ Λ ⋆ U ⋆⊤ ) ij σ ,where g(•) denotes the density of a standard normal. We define the class of distributionsP = {P Λ ⋆ ,U ⋆ : (Λ ⋆ , U ⋆ ) ∈ Ω(λ ⋆ , µ, r)} .For µ 1 , µ 2 ∈ R n and a pair of normal distributions N (µ 1 , σ 2 I n ) and N (µ 2 , σ 2 I n ), their KLdivergence is given by (see Example 15.13 in [56] )KL N (µ 1 , σ 2 I n ) N (µ 2 , σ 2 I n ) = 1 2σ 2 ∥µ 2 -µ 1 ∥ 2 2 .It follows that for any P Λ ⋆ ,U ⋆ 1 P Λ ⋆ ,U ⋆ 2 ∈ P,KL P Λ ⋆ ,U ⋆ 1 P Λ ⋆ ,U ⋆ 2 ≤ λ ⋆2 2σ 2 U ⋆ 1 U ⋆⊤ 1 -U ⋆ 2 U ⋆⊤ 2 2 Fand thus, taking square roots,EQUATIONwhere the second inequality holds from Lemma 2.6 in [27] .To apply the Yang-Barron method, we follow a two-step procedure (see Chapter 15 of [56] ):1. Pick the smallest ε such that ε 2 ≥ log N KL (P, ε).2. Choose the largest δ that we can find a δ-packing that satisfies the lower boundlog M(K r,µ , d 2,∞ , δ) ≥ 4ε 2 + 2 log 2.Then it follows from Lemma 18 and Proposition 2 that the minimax risk is lower bounded by δ/2.For the first step, noting that by Equation (136), a (σε/λ ⋆ )-covering set for V n,r under d F yields an ε-covering set for the √ KLdivergence, we haveN KL (P, ε) ≤ N (V n,r , d F , ε/λ ⋆ ) ≤ C 0 λ ⋆ √ 2r σε r(n-r), where the last inequality follows from Lemma 13. Thus, in order to have ε 2 ≥ log N KL (P, ε), it suffices to haveε 2 ≥ r(n -r) log C 0 λ ⋆ √ 2r σε which holds if we set ε = C 0 λ ⋆ √ 2r/σ.With this choice of ε, we then follow the second step of the Yang-Barron method and pick a δ to satisfyEQUATION)By Equation (115) in the proof of Lemma 4, we haveEQUATIONfor δ satisfying Eqaution (21) . Combining Equations ( 137) and (138), our goal is to find a δ, such thatEQUATION)We pick δ to beEQUATION)One can verify that δ satisfies Equation ( 21) under the assumption λ ⋆ ≤ (6√ C 0 ) -1 σ √ n.To see that the δ given by Equation (140) satisfies Equation (139), we separate our discussion into two cases, one for large λ ⋆ , and the other for small λ ⋆ . WhenEQUATIONby Equation (140) we haveδ = c 0 σ √ r 12eλ ⋆ √ 2C 0 (142)and therefore, Equation (139) follows fromc 2 0 r 2 32e 2 δ 2 = 9C 0 rλ ⋆2 σ 2 ≥ 8C 0 rλ ⋆2 σ 2 + 3 log 2,where the first equality holds from Equation (142) and the last inequality follows from Equation (141) for all n sufficiently large.On the other hand, whenEQUATIONby Equation ( 140) we haveEQUATIONand therefore, Equation (139) follows fromc 2 0 r 2 32e 2 δ 2 = 3rn log(12n/µ) µ ≥ 8rn log(12n/µ) µ + 3 log 2 ≥ 8C 0 rλ ⋆2 σ 2 + 3 log 2,where the first equality follows from Equation (144), the next inequality holds for all n sufficiently large, and the last inequality holds from Equation (143). Thus, we conclude that the choice of δ given in Equation (140) satisfies Equation ( 139), completing the second step of the Yang-Barron method.Finally, combining Proposition 2 and Lemma 18, we conclude that for a universal constant c > 0,inf U sup (Λ ⋆ ,U ⋆ )∈Ω(λ ⋆ ,µ,r) E Λ ⋆ ,U ⋆ d 2,∞ U , U ⋆ ≥ δ 2 ≥ c σ √ r λ ⋆ ∧ µr n log(n/µ) ,completing the proof.Here we collect additional experiments to complement our simulations in Section 5.We provide additional details for the experiments previously discussed in Section 5.1. Recall that we observeY = M ⋆ + W = λ ⋆ u ⋆ u ⋆⊤ + W ,and wish to recover u ⋆ ∈ S n-1 . We refer the reader to Section 5.1 for the details of how λ ⋆ , u ⋆ and W are generated and how we run Algorithm 1.In Section 5.1 we mentioned that under Laplacian noise, as shown in the third column of Figure 1 , the estimator u given by Algorithm 1 seems to have a slight dependence on the coherence parameter µ. We give a close examination of the estimation error of the largest entry of u ⋆ in Figure 3 , with shaded bands indicating 95% bootstrap confidence intervals. Figure 3 shows that the estimation error of the largest entry of u ⋆ for u is seen to be much smaller than 10 -2 , while in the third column of Figures 1, the estimation error d ∞ ( u, u ⋆ ) is well above 10 -2 . This indicates that the dependence on µ observed in the right-hand subplot of Figure 1 comes not from estimating the largest entry of u ⋆ , but rather from estimating the other entries. In our experiment, the other entries are all nearly incoherent (that is, they have a magnitude at most O( log n/n)), whence their estimation errors are expected to have no dependence on µ asymptotically. Thus, the slight dependence on µ exhibited Figure 1 is most likely to be a small order dependence compared to the error rate stated in Theorem 1, and should not affect the asymptotic error rate. We provide additional details for the experiments previously discussed in Section 5.2. Recall that we observeY = M ⋆ + W = U ⋆ Λ ⋆ U ⋆⊤ + W ,and wish to recover U ⋆ ∈ R n×r . In addition to the rank-2 setting discussed in Section 5.2, we include experimental results for the case when M ⋆ has rank 3. We also provide estimation error under d 2,∞ for our estimate U in Algorithm 2 and the spectral estimate U , to complement our results under d ∞ reported in Section 5.2. The experiments follow the same setup outlined Section 5.2, and we refer the readers there for details regarding running Algorithm 2 the generation of Λ ⋆ , U ⋆ and W .We first provide more details as to how we obtain the estimation error under d 2,∞ . Normally, sinced 2,∞ ( U , U ⋆ ) = min Γ∈Or U Γ -U ⋆ 2,∞, obtaining the d 2,∞ estimation error requires finding an orthogonal matrix that minimizes a nonsmooth function, which is hard to achieve. In our simulation, however, since we have sufficiently large eigengaps between the eigenvalues, we know how each column of U corresponds to the columns of U ⋆ . Thus, we merely need to resolve the ambiguity in the sign of each column of U , rather than searching over all Γ ∈ O r . By assigning each column of U the sign of the corresponding column in U ⋆ , we resolve this ambiguity and can obtain the d 2,∞ estimation error. of Figure 2 , the dependence on µ again appears slightly reversed from that of the spectral estimator. For Laplacian noise, as in the third plot of Figure 2 , there again seems to be a slight dependence on µ. For the same reason discussed in Sections 5.1 and 5.2, we expect such dependence to be of smaller order than the rate in Theorem 1 and should not affect the asymptotic error rate.As mentioned in the main text, to the best of our knowledge, we are the first paper to consider the problem of non-spectral entrywise eigenvector estimation. The nearest obvious method to serve as a comparison point, if we were to insist upon one, would likely be one based on approximate message passing (AMP; see [34] for an overview). AMP methods make no explicit coherence assumptions, but the underlying mechanism essentially requires incoherence: inherent to AMP-based eigenvector recovery methods is that the eigenvector is modeled as having its entries drawn i.i.d. according to a common distribution. Specifically, AMP methods typically make a mean field assumption whereby the empirical distribution of the entries of u ⋆ converges in ℓ 2 to some distribution π. Since Figure 6 : Estimation error under d ∞ as a function of size n, by approximate message passing (AMP; green), the leading eigenvector (blue) and Algorithm 1 (orange) for √ n∥u ⋆ ∥ ∞ equal to 3n 1/3 (solid lines), 3n 1/4 (dashed lines) or 3n 1/5 (dotted lines) under Gaussian noise. Each data point is the mean of 30 independent trials. AMP-based methods are tailored to ℓ 2 -recovery, they are suboptimal for entrywise recovery problems: small ℓ 2 error does not necessary imply small entrywise error.The unsuitability of typical AMP methods notwithstanding, we include here a comparison against our Algorithm 1 for the sake of completeness. The experimental setup mirrors that of Figure 1 , but now includes estimation error for an AMP-based method, as well. We generate u ⋆ according to the following procedure: set a random entry of u ⋆ to be a ∈ {3n 1/3 / √ n, 3n 1/4 / √ n, 3n 1/5 / √ n}, then generate the remaining entries by drawing uniformly from {±1} n-1 and normalizing these to have ℓ 2 norm √ 1 -a 2 . This way, ∥u ⋆ ∥ ∞ = a and the coherence is µ = a 2 n. We choose this setting to ensure that the limiting prior distribution satisfies the assumptions required by AMP, and thus we can apply the update procedures using Equations (22) (34) and the example after Equation (35) in [34] .Having generated Y = M ⋆ + W , we estimate u ⋆ using the spectral estimate u, the AMP method and our method as described in Section 5 and measure the estimation error under d ∞ . We report the mean of 30 independent trials for each combination of conditions (i.e., each combination of problem size n and magnitude a). We vary the matrix size n from 3000 to 22000 in increments of 1000.Figure 6 compares the entrywise estimation error of the AMP method (green), the leading eigenvector of Y (blue) and our Algorithm 1 (orange). Across settings, Algorithm 1 recovers u ⋆ with a much smaller error under d ∞ compared to the other two estimates, and shows an error rate with no visible dependence on the coherence. Both the spectral method and the AMP-based method exhibit different estimation error rates as the coherence increases. In particular, the AMP method performs much worse due to the fact that it is a mean field approximation method and not well-suited for our setting. Adapting AMP-based methods to target entrywise recovery rather than ℓ 2 recovery, in hopes of rectifying the poor performance exhibited in Figure 6 , is a promising direction for future work.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: The overall evaluation by the reviewers concludes this to be a technically solid theory paper making a novel contribution in terms of a spectral algorithm for eigenvector estimation for a low-rank matrix estimation and its analysis. The paper's interest is theoretical, its implications and interest for a broader NeurIPS audience are limited. I recommend acceptance as a poster.

Reviews: review: paper_summary: paper_summary: This paper mainly studies the problem of eigenvector estimation in low-rank signal-plus-noise matrix models and some new lower bounds for estimation rates in such models are derived. Specifically, the entrywise estimation error of the proposed procedure has no dependence on the coherence $\mu$ for the rank-one signal matrices, and could achieve the optimal estimation rate up to log-factors.
strength_weakness: strength_weakness: 1. The theoretical  results presented in this paper only fit for the scenarios where the low-rank signal matrix is symmetric, thereby limiting its practical use. 
2. Assumption 2 seems to be confusing, according to the following comments. 

a)  Firstly, in the first example given by the authors, and $c_1$ and $c_2$ that satisfy condition $\|u^*\|_2=1$ are related to $n$, while the authors state that they are constants (line 125). 

b) Secondly, $\alpha_0$ is related to $n$, meaning $u^*$ is related to $n$. Therefore, under Assumption 2, considering the influence of $\alpha_0$, what will happen to the coherence? For example, will it no longer be related to $n$? In other words, Assumption 2 and the coherence condition are coupled together, making it difficult to determine whether the disappearance of coherence in the proposed method is due to the careful design of the algorithm or the existence of Assumption 2.

3. The lower bound derived in this paper does not seem to align with the environmental conditions. In other words, the upper bound is given under the assumption that Assumptions 1 through 4 are satisfied. When constructing a bad instance to prove the lower bound, this bad instance should also satisfy such assumptions. Additionally, the selection of $\lambda^*$ does not conform to Assumption 3.

4. The work lacks experimental validation on real-world datasets.
questions: questions: 1. The description of Algorithm 1 is too brief. Could you provide a more in-depth discussion?
2. The paper mentions that the computation of the simulation requires 3425 hours, which seems to be very very time-consuming. Do the classical spectral algorithms or other related algorithms also need  this high kind of computational cost?
limitations: limitations: See points 1 and 4 in the weaknesses part above.
paper_summary: paper_summary: This paper proposes an algorithm to estimate the eigenvector of a low-rank matrix under Gaussian noise. The algorithm provides a $\ell_{\infty}$ guarantee that is coherence free for rank-one matrices, at the cost of worsening the dependence on $\log n$ and some technical assumptions. The main idea is to utilize the low-rank structure and relies more on the "stronger" entries that are much larger than the noise rather than "weaker" entries. Empirical evidence shows that the algorithm continues to work for general low-rank matrices.
strength_weakness: strength_weakness: The main weakness is Assumption 2 and Assumption 3, which are a bit weird and could significantly worsen the bound in some cases. Also, the upper bound is only proved for rank-one matrices.
questions: questions: I have no particular questions that may change my evaluation.
limitations: limitations: n/a
paper_summary: paper_summary: The paper studies the low rank matrix estimation problem. It aims to find an estimator that is good with respect to the $\ell_{2,\infty}$ norm. In general, such errors depend on incoherence parameters. The authors propose and prove a spectral algorithm that does not depend on the coherence parameters when the top eigenvalue of the signal is of order $\sqrt{n \log n}$. Furthermore, the paper proves estimation lower bounds with respect to the $\ell_{2,\infty}$ distance when the operator norm of the signal is on the same scale as the noise.
strength_weakness: strength_weakness: 1) The authors are able to prove a nice rate of convergence for the algorithm. Unfortunately, the proof relies on some technical assumptions to simplify the proof. For instance, the application of Lemma 9 relies crucially on the fact that $s$ and $I_\alpha$ are independent of $W$. This technical obstruction is dealt with quite creatively by introducing non-random sets $I_\alpha$, albeit at the cost of additional assumptions on the model.
2) An algorithm for finite rank spikes are proposed, but the generalization of Theorem 1 to the finite rank case has not been proven. 
3) Theorem 2 is stated when $\lambda$ is a constant multiple of the identity, so it is slightly more restrictive than in equation 9.
4) Assumption 2 seems slightly limiting. It appears like a difficult condition to verify in practice.
questions: questions: 1) Assumption 2 is slightly hard to parse. It seems like it is quite easy to violate Assumption 2 by introducing some randomness in the generation of $u^\star$. Is it true that if $u^\star$ was generated by normalizing a vector with i.i.d entries that assumption 2 will be violated?  
2) The subscripts of the expected value in Theorem 2 is mysterious. It appears that the $\Lambda_\star$ and $U_\star$ are non random, and the only randomness is in $W$. Perhaps some notational clarification is needed here?
3) Is it possible to extend Theorem 2 to general $\Lambda$ which are not necessarily constant multiples of the identity? 
4) Perhaps proving an uniform bound in Lemma 9, will allow us to do a proof without assumption 2, since we can handle cases when $\hat I$ and $W$ are dependent. However, we will likely lose the $\sqrt{\log n}$ bound if we wanted something uniform.

Typos:
1) Line 449: A $\sum_{i}$ is missing 
2) Line 673: It should be $\mathcal{E}_{5,\alpha}^c$ and the complement outside of the bracket should not be there.
3) Line 954: an extra $\leq$ appears
4) Line: 1046: it should be $\mathbb{K}_{r,\mu}$
limitations: limitations: The limitations of the assumptions are clearly stated in remarks.
paper_summary: paper_summary: The authors consider the spiked Gaussian Wigner matrices, where the main goal is to estimate the (low-rank) spike. Since the known performance of the spectral method for the estimation (of the spike) deteriorates as the maximal entry of the spike (more precisely, the incoherence parameter) increases, the authors propose a new algorithm that does not depend on the incoherence parameter. Roughly, the main idea of the proposed algorithm is that under several assumptions the entries of the noisy data corresponding to the large entries of the spike are dominated by the spike, and thus those entries themselves can be used to approximate the spike instead of the eigenvectors of the data matrix. Mathematical analysis and numerical experiments for the algorithm are presented.
strength_weakness: strength_weakness: - Non-spectral methods are not discussed. Since the proposed algorithm is not entirely spectral, I think its performance should be compared with other non-spectral methods as well.
- Assumption 2 is strange and cannot hold in many important cases. For example, if the spike $u^*$ contains many entries of the size $n^{-\alpha}$, then Assumption 2 may not hold due to a similar reason as it does not hold when $u^*$ is drawn uniformly from $S^{n-1}$.
- Several claims are not rigorous in the sense that they are cited from references in which assumptions are different from those in the current manuscript.  (See Questions.)
questions: questions: Below, I collected several previous results used in the current paper that are not directly applicable since the assumptions in the original papers are different from those in the current paper.
- In line 44, the results in [6] assume that all entries of the spike $u^*$ are $O(1/\sqrt{N})$.
- In line 46, the original BBP transition in [8] is not for the signal-plus-noise matrix models. (It was for a Gaussian matrix where the spike is contained in the covariance matrix.)
- In line 52, the case $|\lambda^*| \gg \sqrt{n}$ is not considered in [8] and thus it is unclear whether the results in Lemma 1 can be applied to this case. Moreover, strictly speaking, when $|\lambda^*| = \Theta(\sqrt{n \log n})$, Lemma 1 only says that $\liminf_{n \to \infty} d_{\infty} (u, u^*) \geq 0$, not about the asymptotic bound for $d_{\infty} (u, u^*)$.
- In line 144, the result in [22] is under the assumption that $|\lambda^*| = \Theta(\sqrt{n})$ and the result in [45] is under the assumption that the noise matrix is GOE. (The noise matrix $W$ in the current paper is not a GOE matrix since the variance of the diagonal entries is the same as that of the off-diagonal entries.)
- In the inequality below line 491, since the probability estimate on $\max |W_{ii}|$ is basically a union bound, with the coefficient $4$, it seems to hold only with probability $1-O(n^{-7})$.
limitations: limitations: The work does not seem to have potential negative societal impact.
paper_summary: paper_summary: The authors propose a new method for coherence free entrywise estimation of eigenvectors in signal plus noise model. Namely, entrywise estimation error usually depends on incoherence of the underlying matrix and can significantly increase error bounds for coherent matrix estimation. In this work, authors show that in suitable regime, entrywise error for recovery of rank-1 matrices scales provably as $\\tilde{O}(\\sigma/\\vert \\lambda^\\star \\vert)$ w.h.p. This is achieved by reestimating eigenvector entries with high amplitude. Moreover, authors propose general rank-$r$ algorithm that they empirically validate. Finally, authors prove a new lower bound on minimax eigenvectors estimation in $\Vert \cdot \Vert_{2\to\infty}$.
strength_weakness: strength_weakness: 1) The main theorem is proven only in rank-$1$ setting, and rank-$r$ setting is only empirically tested.

2) Gaussianity assumption is restricting. If your results hold under less restrictive assumptions (you mention Assumption 1 in Chen et al. 2021), I would prefer having at least a statement of an analogue of Theorem 1 in the most general setting you can have. 

3) Bounds might be improvable in log terms.
questions: questions: 1) You consider only symmetric matrices in the paper. Are all results easily transferable to asymmetric case (for example, by symmetrization trick)?

2) In rank-$r$ case when you split matrix $Y$ into $\\lambda_k^{\\star} u_k^{\\star} {u_k^\\star}^\\top$ and the remaining terms that you consider as noise, how would you mitigate the fact that this new noise containing all non-$k$ eigenvectors is dependent on signal i.e. on $k$-th eigenvector? Is this an issue at all?

3) Could you please give some more precise hints why is rank-$r$ case more difficult than rank-$1$ case?

4) Are there any other entrywise lower bounds in the literature that are not simple corollaries of Frobenius lower bounds? 

5) How does your method compare with other coherence free methods? For example, using leverage scores for sampling more the entries with high coherence (effectively reducing noise on those entries)? I agree that your model is not the same, but if you could comment on high level differences between the two methods.
limitations: limitations: The authors have addressed limitations adequately.

Comments: comment: I think the authors have well addressed my comments. I shall raise my rating to 6.
Thank you for the answers. I have checked the responses.
Thank you for the detailed response. I have no further questions, and will maintain my original score.
Thank you for your response. I think the paper contains some interesting new ideas but awaits future work to provide a more complete analysis, e.g. relaxing the assumptions. Therefore, I elect to maintain my score.
Thank you for your reply. I acknowledge reading the rebuttal and will maintain my initial score.