Coherence-free Entrywise Estimation of Eigenvectors in Low-rank Signal-plus-noise Matrix Models
Authors: Hao Yan
Keith Levin
Venue: NeurIPS 2024 poster (2024)
Keywords: eigenvector estimation
spiked Wigner models
low-rank signal-plus-noise matrix models
subspace estimation
minimax theory
Primary area: probabilistic_methods

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.

Coherence-free Entrywise Estimation of Eigenvectors in Low-rank Signal-plus-noise Matrix Models
Hao Yan
Keith Levin
Department of Statistics University of Wisconsin Madiisn
Department of Statistics University of Wisconsin Wisconsin-Madison
Madison, WI 53706
Madison, WI 53706
United States of America hyan840wisc. edu
United States of America kdlevin@wisc. edu
Abstract
Spectral methods are widely used to estimate eigenvectors of low-rank signal matrix subject noise. These methods the leading eigenspace of an observed matrix to estimate this low-rank signal. Typically, the entrywise estimation error of these methods depends 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 rank-one signal matrix, under mild technical conditions, the entrywise estimation error of our method provably has 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- non-Gaussian noise and that an extension of our method to the case of 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 &2 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 82,00 distance.
Introduction
Spectral methods are extensively used in contemporary data science and engineering fundamental idea underlying these methods is that the eigenspace or singular subspace of an observed
27 The
matrix reflects important structure present in the data from which is derived. Spectral methods have been deployed successfully in a variety of tasks, including low-rank matrix denoising [30] 10 factor
analysis [2]
61
62] community detection [49 52 [] 40 (50), pairwise ranking 43 25 and
matrix completion 48
24
The widespread use of spectral methods has driven extensive research
into the theoretical properties of eigenspaces and singular subspaces, yielding normal approximation
results 10
as well as perturbation bounds 60 20
45
For more comprehensive
recent review of spectral methods, see (27).
1.1 Eigenspace estimation in low-rank matrix models
Consider an unknown symmetric matrix M* U'A'U* Rxx" where U E Raxr has orthonormal columns and A" E I is diagonal, containing the nonzero eigenvalues of M
ordered so that [X] 2 [A]] 2 ... Z ael 0. Our goal estimate U* from a noisy observation
Y M W
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

where W = [Walissssn is 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 o² and common subgaussian parameter vw-
We remind the reader that the subgaussian parameter pw serves as a "proxy" for the variance. Indeed, in the Gaussian case, we have o² lw, while o² 5 vw more generally [54] [66.
Spectral methods often estimate U directly using the r leading eigenvectors U Yf As a result, the entrywise and row- row-wise behavior of U has attracted considerable attention B21 22244
Given an estimator Ü _RaxT, the estimation error measured in terms of the 62,0 distance
02 (U,U*)
min || - ÜT 2,00
rec.
where the presence of T is to resolve rotational non-identiffabiiity. In the rank-one case, this reduces to the &o distance.
(3) for u E R and a given estimator û E TR.. Estimation error bounds in loo or f2,00 distance typically rely on the incoherence parameter μa of U*, defined as
d u." min {I|=* - ü olloc I|ue + ko|1o
P 1 E [L,nrr].
In the rank-one case with Gaussian noise, if the leading eigenvalue A of M* satisfies |사*| M( /n), Theorem 4.1 of (27) shows that with probability at least (n $), the leading eigenvector of Y satisfies
a (Vlgg n + vullu*l)o) ovlog + oV |*+
do (u, u²) S
|*+
When o /nn S | σ oo log a regime of most interest (no ploynomial-time algorithm is known when | < Vvvn [6). and estimation is easy when [X| >> / log n), we show in Lemma I that Equation 4 is not improvable up to log-facte oog-factors as a result of the Baik- Ben Arous- Péché (BBP)
phase transition 8 (see [12
38 34
for BtP-style phase transitions in the setting of this paper).
Lemma 1. Under Equation I with Gaussian noise, let M Xuuuut T If both limits lim X+ (a >> 1 and som p/n exist, then for any E [1, n), there exists u² E S such
that almost surely,
o² Vnp
lim doo (u, u²) ) 2 lim 40000
(5)
+20 2 2
Equation (5) shows that the spectral estimate u has an intrinsic dependence on μe, with especially bad performance when j is large and | = O(a ((a/// log n.) In this large-j regime, beyond low- rankedness, M cxhibits additional structure (c.g., sparsity) that is not fully utilized by the spectral μ in Equations 4 and (5) is a shortcoming of the
estimator. This suggests that the dependence spectral estimator. In Algorithm we present a new estimator designed to remove this dependence on μ.. Theorem shows that up log-factors, it matches the minimax lower bound discussed below (see Equation in Section [.2). Experiments in Section 5 further support our theoretical results.
(9
In the rank-r case with Gaussian noise, Theorem 4.2 in (27 shows that when |XZ| Z a a logn,
(U, σ (RVer + V)
[A;
with probability least - On where K | the condition number of M Here again, the estimation error depends μ., 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 show that Algorithm?? 2 outperforms the naïve spectral method in the general rank-r case, with little to no sensitivity to the coherence J. We note in passing that the dependence on k in Equation ( can likely be removed 3 62 57], though we do not pursue this here.

---

1.2 Minimax lower bounds for subspace estimation
Minimax lower bounds have been established for variety of subspace estimation problems, including sparse PCA [1 matrix denoising [20), structural matrix estimation [19], network estimation
335 63 and estimating linear functions of cigenvectors 442 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 2 1,
oo Tovr nr |
min PEC.
U
min
holds in a minimax sense (see Theorem [28 Theorem in 66 Far fewer papers have considered lower bounds under d2
[8 4
and these results are derived via the trivial lower bound
02 (,,*)
min /nc.c.
ÜT U
(8)
which holds for any U,U* Raxr,
Applying the lower bounds in Equations
and ( we have
lovi F
sup 02.00 (Ū,0*) 2 min U U.ER"XT.U* =I
holds for any estimator Ò Raxr When U is incoherent, meaning that μ O()), this lower bound is achieved by the spectral estimation rate Equation (6) when | = (( (0(o/// n log nt), and is
achieved trivially by Ū = On,r when |Λ;1 = vn). On the other hand, when U is coherent, in the sense that w1). and Xx; = ( log n.), our discussion above in Section [1.1 (including our new results in Theorem [ suggests that the rate in Equation 4 can be achieved up log-factors.
This leaves open the question of the minimax rate when /L = (1) and [A;] = o(avn)) ) In this case, the lower bound in Equation (9) cannot exceed vr/n. n.. This seems suboptimal, as we expect some dependence on ||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 @ 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.
1.3 Notation and roadmap
We use C' denote a constant whose precise values may change from line to line. For positive integer n, we write [r]] = 2,,,, ........... n.). |A| denotes the cardinality of a set A. For real numbers and b, write a b max(a, b) and a/b min(a, b). For vector v (V1, U2,..., un E R", we use the norms || = v -=' uf and |/|| = max, /os]. We let e; E R RR, [v] denote the standard basis vectors of I 5 {u E R ||u]|2 = 1} denotes the unit sphere. For a matrix M E R M,,. denotes its i-th row as row vector, |M denotes its operator norm and || max,g || a.-llll indicates the maximum row-wise & norm. I, E R" denotes the n- by-n identity matrix. O, denotes the r-dimensional orthogonal group. We use both standard Landau notation and asymptotic notation: for positive functions f((n) and g(n), we write f(n) >> g(n),
f(n) (n())) g(n) (n)) if ((m)//(n) + 00 as + DO. We write f(n) 2 g(n), f(n = (gg(n) or g(n) = (()()) for some constant C > O, we have f(n)/g(n) > C for all sufficiently large n. We write f(n) O(g(n)) 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 new algorithm that achieves the minimax optimal error rate up logarithmic factors the growth regime where | = 2
(Theorem
In Section 3 we extend this algorithm to rank-r eigenspace estimation. In Section we present theoretical results for the metric entropy of subspaces under d.g and d2, and improve Equation ( under the growth regime where [X* = ((avn) (Theorem 2). Numerical results are provided in Section We conclude in Section 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.
3

---

2 Rank-on one matrix eigenspace estimation
In this section, we study the model in Equation (T) when M is rank-one with eigendecomposition M
where X E E and u" S As discussed in Section | spectral methods may have sub-optimal dependence on compared to the lower bound in Equation (9. We show that better estimator is possible by working with 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, be the
A
log _ n, ,,...,,oo log
[
n, log m
(10)
where L is given by For n sufficiently large, for every v E gm-1, there exists og A such that
L = log(2n)
(11)
log log
z 1i loal 2 oool
(12)
ag log n
To motivate Algorithm suppose ut is entrywise positive. For ag A, denote the set in Equation 12 by Ing. By Equation (12. the sum of entries Mi with i, E Ioo grows as 2((A*I]/an log 2 n), while the sum of the corresponding entries of W grows as (aolTaolvoo n). That is, when | is sufficiently large, the signal contained in the entries i,j E Ioo dominates the noise. If we knew Lav, utilizing the entries in lop would reduce the estimation error incurred by small entries of u". In practice, we do not know Icg 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 P
Assumption 2. There exists an as A satisfying Equation that for all sufficiently large n.
12 and a constant 60 S such
{i |d:|ut] E [(1 co)oo. (1 + co aol] = 0.
We pause to give a few examples to illustrate Assumption 2 First, consider u" e + c2n 1/2 with C1, C2 = (1) chosen so that || 2| 1. We note that C1, C2 both depend on n, but are bounded away from zero as grows, and one verify that Assumption holds with ap log 1/2 n and 60 1/2. As another example, consider ur n 11/21, E I One may verify that taking ag (log n) -- 1/v2n and e 0.4 satisfies the conditions in Assumption 2
As an example of setting that violates Assumption 2 consider 2² obtained by renormalizing a vector of i.i.d. Gaussians. This results in u* being Haar-distributer on S"-1 and Assumption
violated with high probability. To see this, note that u² s g/ / where g ~ N I,) (see Theorem
3.4.6 in [54)). Since with high probability || O log n). Equation (12) holds only when Og R 1/v For Assumption to hold, there must be gap of @(1) between the entries of g, which fails with high probability.
It is tempting conclude from the counter-example just given that renormalizing a vector of i..dd entries must necessarily result in u* that violates Assumption 2, but this is not always the case. the entrywise distribution has suitable structure, may still obey Assumption 2. As an illustration, suppose that u* is obtained by renormalizing vector from distribution with variance so that u* = g/ vn. If the g, are drawn by taking g: = a with probability p and 9; b with probability
(91. (91.92.... .......99....................... ...) < R" with i.i.d. entries
p, then each entry of ut is either approximately op/ vn or approximately b(1 p)/ /n. Choosing a, b and p appropriately, we can ensure a gap between the entries of u* of size (n (n--1/2) 1/2), and we can take ag = (log n) zs 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 useful initialization, make Assumption 3 on A
Assumption 3. There exists a constant C > 2400/ where is as in Assumption) 2 such that the leading eigenvalue X of M* satisfies
|*1 > C V Vww logn.
(13)

---

Remark 1. The dependence on co in Assumption ii is for technical reasons discussed in Remark 2 In our proofs, we do not optimize the dependence on C₁ and assume that C₁ 2400/ cg. As demonstrated in our experiments in Section 5 XX 2 vown log n. appears sufficient in practice. When [X*| S Vuwn, n, the spectral estimator fails to provide any useful initial estimate and it is believed that no polynomial-ting time algorithm can succeed. We provide more discussion on this matter in Remark
is a leading eigenvalue estimate À that recovers the true The final ingredient required for Algorithm 1 signal eigenvalue A suitably well.
Assumption 4. Under Assumption
X is such that with probability at least 1 - O(n log n),
X s C2//w 3/2 n..
Assumption 4 seems stringent at first. The top eigenvalue of Y achieves only (( error rate
(see Lemma 2.2 and Equation (3.12) in (27 ). This is because x= +no V log n) (see
47 or Theorem 2.3 in 23 see also 26 51 17). Luckily, in our setting, the bias-corrected estimate
A + -+ -no
(14)
2
26 Another estimator, which falls naturally out of Algorithm | also satisfies Assumption 4 We find that it performs similarly to the debiased estimator de empirically, and do not explore it here. Theoretical results for this estimator are in the appendix.
does satisfy Assumption 4
With the above assumptions in hand, we propose a new method given in Algorithm [] We note that the main computational bottleneck of Algorithm| iis 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]
Algorithm 1 Coherence--iie free eigenvector estimation algorithm
Input: Observed matrix Y RRax, leading eigenvalue estimate Ā; parameter B > Output: ū E R
1: If < 0, set Y = Y. Obtain the top eigenvector u E S of Y.
2: Pick any â E A such that the set
{i: |us
ā} satisfies
i 2 à² logg n
and
(15)
{:: 8)ā < |2:1 < (1 + B)a
(16)
3: Let Q E R be diagonal with QuA = sgn (ux)
if i
if E fo and let Ý = QYQ.
4: Set S VyJkel Yn and let ūg (Erel K5K)
(Bv for j [m].
5: For each j E [m], set ū. = uj |uyl S (a/2) log n, and ūj = Qiy otherwise.
Remark 2. In our proofs, we 3 co/2. Equation (6)). Assumption 2 and the cu-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 i and W. Empirically, Algorithm I works well even without these technical conditions. We conjecture that Assumption 2 as well as the co-dependence Assumption 3 can be removed. See Section for further discussion.
As alluded to above, the intuition behind Algorithm i that we aim to concentrate our efforts on estimating the large entries of u² Consider an entry of Y given by X X'u,u" + W.j. Intuitively, locations corresponding to small entries of u2 produce small u, u². These entries of Y have a small signal to noise ratio compared to those arising from products of large entries of "*. 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| [ above and A presented below consist of two parts: finding the large locations, and using those locations to improve our initial spectral estimate of u'.
5

---

measured under foo- Algorithm | assumes that the entrywise variance o² of W is known. Of course. in practice, this is the case, and we must estimate o². 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 estimate r² using a simple plug-in estimator
6²
2 n(n +1
E ISiSiSn
(u--M,) 2
(17)
where M Xur E RRxn, general, if M' has rank r, then we set M UAU wwhere A the leading eigenvalues of Y (sorted by non-increasing magnitude) and U E Roxr contains the corresponding leading orthonormal eigenvectors as its columns. Lemma 3 controls the estimation error of the plug-in estimator 0² for general rank-r signal matrix.
Lemma 3. Under the model given in Equation T.. let M = U'A be rank-r matrix with 2 where A diag (Λi, Xg.,,....., X,,)
such that [i]] 2 2 | Suppose that Assumption 7 holds and that x 2 20, then the estimator o² given in Equation (77 such that with
probability at least O(n 8)
6² 0²| 4000wr
4uw Vlogn
200vw r /og
(18)
n//2
where e >> O is a universal constant.
Remark 3. We use the plug-in in estimator ā in the debiased estimator de Equation (14) and to construct à in of Algorithm 7 Lemma 3 shows that this only introduces extra log-factor to the error bound, which does not affect the estimation ervor rate of either X or u²"
Our main result, Theorem 1 controls the estimation error of Algorithm
Theorem 1. Under the model in Equation (T), suppose that Assumptions 2 and hold. Then for n sufficiently large, the estimate IR" produced by Algorithm [
satisfies
dx (ū, u²) C CViw ()/g 5/2
[
with probability at least 1 - O(n logn), where C' > 0 is universal constant.
Remark 4. Under Gaussian noise, in the regime |^* (n log n),, our upper bound is minimax rate-optimal up to lag-factors compared to the lower bound in Equation (9). In particular, the rate obtained in Theorem 7 does not depend the coherence parameter μ.. A more careful analysis might be able to remove some of the log-factors Theorem but we leave this matter for future work.
3 Rank-r matrix eigenspace estimation
To handle the more general case in which the signal matrix M* is rank propose Algorithm 2 which yields an estimate of U* This achieved by estimating the r leading cigenvectors separately, then combining them into an estimate Ü E Rexr, We explore the empirical performance of Algorithm via simulation in Section leave its theoretical analysis to future work. Algorithm requires the observed matrix Y and an estimate of the k-th leading eigenvalue Λं of M as input. Similar to the rank-one case, the top-r leading eigenvalues λ1 A2,.... ...... A, of Y are biased 47] We
again use a debiased estimator AR.e for A: E [r] as input to Algorithm given by
de.c 1
X3
4ng
(19)
Algorithm is natural extension of Algorithm Essentially, it converts the problem of estimating u into an eigenvector estimation problem under a rank-one signal-plus-neg model given by
Y X uu u
(M* # + w) A + (M*
X Auuut W).
where M
M A There are two differences between Algorithms and remove Equation (16) from Algorithm [ as this is mainly technical requirement (see Remark 2).
First, we

---

More importantly, in Algorithm we conjugate Y by a random orthogonal matrix H E On. The (r (P-1) 1) leading eigenvectors of HM H form random subspace of R=x(r-1), which allows us to treat HM H as noise matrix. By way of illustration, consider the rank-2 case U behaves similarly to random vector drawn uniformly from Sa-1 Therefore, one would expect H u H to behave similarly to a noise matrix n "'gg" where [(, I.) (see Chapter 3 of (54]). As in the discussion after Lemma] 2 we can find set of indices lao such that the signal the corresponding entries of uuj dominates the noise.
with M = Yuuzu
Algorithm 2 Coherent optimal eigenvector estimation algorithm
Input: Observed matrix Y E RR k-th leading eigenvalue estimate Au. If A set Y=
Output: Uk E R
I: Obtain the top-r eigenvectors U of HYH",, where H E0,, is Haar-distributed.
2: Set Q diag sgn U . and set Y QHYH QQ
3: Pick or A such that for i = -{i (d: 2 on ). 17 2 1/a log" n.
4: Set S
EEieErVee) 1/2
and set ū. Exei ExeiVie/ (5 for j [n].
(Uks {(H Qū
if [Ukb s (o/1xel) log
5: Let U - For j E [n]. set un.
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 | 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 cigenvector, the other signal cigenvectors are ignorable. Unfortunately, this random orthogonal transformation breaks Assumption and introduces complicated dependency structure, requiring more careful analysis that we leave for future work.
4 Estimation lower bounds under 22,00 distance
Theorem I demonstrates that for a rank-one signal, dependence of the estimation rate on μ can be removed when | = // logn). n). In this regime, our result matches the lower bound in Equation ( up to log-factors, making this the minimax lower bound under Assumption 2 As discussed Remark 2 we expect Assumption 2 can be removed via a more careful analysis, rendering the lower bound in Equation (9) optimal under a 2(ar n). On the other hand, as discussed in Section 1.2] the lower bound in Equation (9) is sub-optimal in the regime where
|X+ = (n) In what follows, we aim improve upon Equation (9) by deriving metric entropy bounds (54] for rank-r singular subspaces under the f2.0 distance when | = O(avn).
Recall that for semi-metric p defined on set K, we may define the å-packing number M(K, p. 5) of K under p (see Chapter 15 in (56). The packing d-entropy, log M(K, p. d), captures the complexity of the space IK, and lower bound on the 8-entropy can be translated into a lower bound on the minimax estimation error rate. For a given r E [m] and S μ S n//, we consider the parameter set
K(n,r, V Vur/n) = U U Raxr :U I,, | S
ry n
(20)
Below, we write Kr, for K(n,r, V /ur/n). Lemma 4 lower bounds log M(Kr, 02.00 6). We focus on the range r/n S 8² < uu/n, as the lower bound in Equation (9) shows that 82 < r/n is not achievable when [^*| = Vn) and 8² > ur/n is achieved by the trivial all-zeros estimate. Lemma 4, Suppose that n/μ 2 max(4, (4. and μ 2 12log and let 8 > 0 be such that Luur
&r
82
(21)
Se2n
96e2n log (12n/u)'
where oo > 0 is a universal constant. Then when n is sufficiently large,
y2
log M (Krr,u d2 8) 2 82
(22)
7

---

Remark 5. Lemma applies when logn S S n/r. A more careful analysis might relax the lower bound, but when μ log n, any U Ky n 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 implies an improved lower bound compared to Equation ( Consider the parameter space
22X", [4, r) ((A"U*)) A = X 1
Using the Lang-Barron method [59] we obtain a lower bound for eigenspace estimation the rank-r Sggaa-ppus-noiie model for [X* O(avn). A detailed proof can be found in the appendix.
Theorem Under Assumption and the conditions of Lemma 4 for any 0 < X ovv where Co > 0 is a universal constant related to covering numbers of Grassmann manifolds, there is universal constant O such that for all sufficiently large n, (ovr
Pr V log(n//))) EA -2-,0-22,00 (Ú.V)) 2 X=
inf ÚERMXP
sup
(E)(A (p.))
Remark 6. Theorem removes the upper limit v from Equation (9) suggesting that p. only comes to bear when X ov/n. This regime is not well studied, the BBP transition (8] implies that spectral methods fail, but other algorithms might achieve our lower bound. For example, signal detection possible structure is present [6]. Unfortunaeely, any such algorithm is likely to be computationally expensive, given the general belief that no polynomial-ime algorithm can succeed when X / (39 Dj. We leave further exploration of this small-X" regime to futurr work.
Remark 7. The parameter space O(X*, r) considered in Theorem 2 contains only signal matrices with condition number к. =1. 1. 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.
Numerical experiments
We turn brief experimental exploration of our theoretical results. All experiments in distributed environment on commodity hardware without GPUs. In total, the experiments reported below used 3425 compute-houre Mean memory usage 3.5 GB, with maximum of 11 GB.
5.1 Simulations for rank-one eigenspace estimation
We begin with the rank-one setting considered in Algorithm I in which we observe
Y = M' + W = Xtu"u" WW
and wish recover u² E gn-1 We take X /n log in all experiments, matching the in |emark[[] We consider three distributions for the entries of W: Gaussian, Laplacian and Rademacher, We consider two approaches to generating u*. In either case, we
all scaled have variance o² set random entry of u² to be a E {0.3, 0.55, 0.8}, then generate the remaining entries by either
1. drawing uniformly from vI /1 -gn-2
2. drawing uniformly from [=1]==1 then normalizing these have & norm VI-a² a².
In both cases, ||=*||/==a and μ= am with high probability. We take @=)(1), since finite samples, On -1/2 log n (which is nearly incoherent) is hard to discern from constant (e.g., when n= 20000, 4n 1 n 0.28, nearly matching 0.3).. Having generated Y M + W. we estimate u* using both the spectral estimate u and Algorithm| 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 from 100 to 15100 in increments of 1000.
When running Algorithm we use the debiased estimate Xe from Equation (14 This requires an estimate of Ø, for which we use the plug-in estimator in Equation (7).. We set 5 O. eliminating Equation [6). Similar to Algorithm 2 we conjugate Y by random orthogonal matrix H E On, We expect the top eigenvector ū of HYH" to be approximately uniformly distributed on Sa-1, is close to Hu" (see Theorem 2.1 in 44 Thus, the median of the absolute values of should be 1122) Instead of selecting ag according Equation [5) we set ag be this median. The

---

Method
10-1
Spoctral
Our Method
Fox Error (Log Scale)
10-2
||u* sc
0.55
10-1
0.3
0.8
10-2
208
4483)
(844)
Stad
t0900
12000
1889
2000)
6680
Sogo
10000
12039)
1460)
2830
1000))
1300
1400
Figure I: Estimation error measured in de as function of dimension n, by the leading eigenvector (blue) and Algorithm 1 (orange), for || equal to 0.8, 0.55 and 0.3 (dotted, dashed and solid lines, respectively). We consider u* generated from the Bernoulli (top row) and Haar (bottom row) schemes, and we consider Gaussian (left), Rademacher (middle) and Laplacian (right) noise.
requirement Equation (15) is then fulfilled, since there are roughly n/2 entries larger than the median. After obtaining ù from Algorithm [ we return H as our estimate ut" We note that this random rotation further serves to illustrate that Assumption 2 is merely technical requirement: after a random rotation, with high probability, Hu" does not satisfy Assumption 2
Figure ! compares the accuracy in estimating u* using the leading eigenvector of Y (blue) and Algorithm|| [ (orange) under the three noise settings and two generating procedures for u*. Shaded bands indicate 95% bootstrap confidence intervals (CIs). Across settings, Algorithm| I recovers u with much smaller estimation eтror under de compared the naïve spectral estimate, especially when ||"" Iloc (i.e., the coherence μ4) is large. The spectral method degrades noticeably as coherence increases, while Algorithm [ has far less dependence on J.. Indeed, under Gaussian noise (the first column of Figure D.. it has no visible dependence
Under Rademacher noise (middle column of Figure []. the dependence of Algorithm [ on j1 appears slightly reversed from that of the spectral estimator. Under Laplacian noise (right column of Figure []. there seems to be slight dependence on μ. Further examination in the appendix suggests that this due to estimating the entries other than the largest element of u", and is likely asymptotically smaller than the rate in Theorem
5.2 Simulations for rank-r eigenvector estimation
For the rank-r setting, we have a signal matrix with eigenvalues |ii .... AA We observe M - U*A WW
where A diag(Aj ..., );), and we wish to recover U* E Rexr, We take a and A; /n log Recovering each column of U* separately requires eigengap, defined for & [r] as A == A/ - Ait1l and Ao = oc. Typically, the estimation error of the k-th eigenvector has a Ommin Ax, 1 dependence on the eigengaps (57). Here, we set A = 0.5 log n, so /n logn for all k E [r]. As in the rank-one case, 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 [r]:
X 0.5(r k
1. Randomly select an element of v E RR and set it to be a E {0.3, 0.55, 0.8}.
2. Generate the rest of v by drawing uniformly from vI a=m-=
3. Set oh
I U* -,1((-1))U" -11(k-1)) v. normalize u to have unit & norm, and set U u. l: = 1, then we take U ,, U* .1:(k-1) to be the zero matrix.
Under this procedure, each u has coherence approximately a'n. Since the large entries of the u unlikely to appear in the same rows, U* also has coherence ann. We take 2 here.

---

Spectral, N
| ll
0.55
Our Method,
10-1
Spectral, H
0.8
Our Method,
fox Error (Log Scale)
10-2
10000
15600
10K50
15000
16800
1
Figure 2: Estimation error under dos as a function size n, by the k-th eigenvector (blue/purple) and the estimator in Algorithm 2 (orange/red) for ||u*|| equal 0.8 (dotted lines), 0.55 (dashed lines) or 0.3 (solid lines) with Gaussian (left), Rademacher (center) or Laplacian (right) noise.
Having generated Y= M' W. we obtain estimates via the naïve spectral method and Algorithm and measure their estimation error under doa. We vary 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 E {1, using the spectral [orange/red), under Gaussian (left), Rademacher (middle) and Laplacian (right) noise. Shaded bands indicate 95% bootstrap Cls. In all settings, Algorithm improves markedly on the spectral estimator. Algorithm 2 shows no visible dependence on j under Gaussian noise. Under Rademacher noise, its j-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 I In the appendix, consider r=3 and measure error under d2, and we again find that Algorithm outperforms spectral estimators and is far less sensitive to μ.
estimate (blue/purple) and Algorithm 2
5.3 Comparison with other methods
To the best of our knowledge, we are the first paper to consider the task of non-spectral entry cigenvector estimation. The nearest obvious competing method might be based on approximate message passing (AMP; see (34] for an overview). Such comparison is included in the appendix, where our experiments indicate that while AMP performs well in recovering the signal eigenvectors as measured by ly error, our method specified in Algorithms [ and |
perform better under entrywise and 00 error. Experimental details and further discussion can be found in the appendix.
6 Discussion, limitations and conclusion
We have presented new methods for eigenvector estimation in signal-plus-noiss 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 non-Gaussian noise and its extension to rank-r signal matrices has little dependence on One limitation of our method is that it assumes homoscedastie noise. Future work will aim to relax this assumption and the technical condition in Assumption In the rank-r case, Algorithm essimaats 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 misuse of models and methods are common, but we see no particular such impacts in the present work.
Acknowledgments and Disclosure of Funding
The authors gratefully acknowledge the support of the United States National Science Foundation grants NSF DMS 2052918 and NSF DMS 2023239. KI. was additionally supported by the University of Wisconsin-Madien Office of the Vice Chancellor for Research and Graduate Education with funding from the Wisconsin Alumni Research Foundation.
10

---

References
E. Abbe. Community detection and stochastic block models: Recent developments. Journal Machine Learning Research, 18(177):1-86, 2018.
[2] E. Abbe, J. Fan, K. Wang, and Y. Zhong. Entrywise eigenvector analysis random matrices with low expected rank. Annals of Statistics, 48(3):1452, 2020.
[3] J. Agterberg and J. Sulam. Entrywise recovery guarantces for sparse PCA via sparsistent algorithms. In International Conference on Artificial Intelligence and Statistics, pages 6591-6629, PMLR, 2022.
[4] J. Agterberg and A. Zhang. Estimating higher-order mixed memberships via the 22 lensor perturbation bound. arXiv preprint urXiv:2212.0864. 2022.
J. Agterberg, Lubberts, and C. Priche. Entrywise estimation of singular vectors of low-rank matrices with heteroskedasticity and dependence. IEEE Transactions on Information Theory, 68(7):4618 4650, 2022.
[6] A. E. Alaoui, F. Krzakala, and M. Jordan. Fundamental limits of detection in the spiked Wigner model. Annals of Statistics, 48(2):863 - 885, 2020.
[7] S. Athey, M. Bayati, N. Doudchenko, G. Imbens, and K. Khosravi. Matrix completion methods for causal panel data models. Journal the American Statistical Association, 116(336)1116--7330 2021.
J. Baik, G. B. Arous, and S. Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probubility, 33(5):1643 1697, 2005.
[9] Banks, C. Moore, R. Vershynin, N. Verzelen, and J. Xu, information-theoree bounds and phase transitions in clustering, sparse PCA, and submatrix localization. IEEE Transactions on Information Theory, (4(7):4872-4988) 4894, 2018.
[10] Z. Bao, X. Ding.- and K. Wang. Singular vector and singular subspace distribution for the matrix denoising model. Annals of Statistics, 49(1):370-33 392, 2021.
[11] Z. Bao, X. Ding, J. Wang, and K. Wang. Statistical inference for principal components of spiked covariance matrices. Annals of Statistics, 50(2): 144 1169, 2022.
[12] F. Senaych-Georgge and R. Nadakuditi. eigenvalues and eigenvectors of finite, rank perturba- tions of large random matrices. Advances in Mathematics, 227(1):494-52) 2011. ISSN 0001-8708.
[13] T. Bendokat, R. Zimmermann, and P-A. Absil. A Grassmann manifold handbook: Basic geometry and computational aspects. Advances in Computational Mathematics, 50((1) 2024.
[14] A. Bhardwaj and V. Vu. Matrix perturbation: Davis-Kahan in the infinity norm. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 880-934. SIAM, 2024.
[15] R. Bhatia. Matrix Analysis, volume 169 of Graduate Texts Mathematics. Springer Science & Business Media, 2013.
[16] N. Boumal. An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, 2023.
[17] W. Bryc and J. W. Silverstein. Singular values of large non-central random matrices. Random Matrices: Theory and Applications, 9(04)2255001,, 2020.
[18] C. Cai, G. Li, Y. Chi, H. V. Poor, and Y. Chen. Subspace estimation from unbalanced and incomplete data matrices: 00 statistical guarantees. Annals of Statistics, 49(2):944 - 967, 2021.
[19] T. Cai, H. Li, and R. Ma. Optimal structured principal subspace estimation: Metric entropy and minimax rates. Journal of Machine Learning Research, 22(46): 45, 2021.
[20] T. T. Cai and A. Zhang. Rate-optimal perturbation bounds singular subspaces with applications to high-dimensional statistics. Annals of Statistics, 46(1))44 (6:10))0 - 89, 2018.
[21] T. T. Cai, Ma, and Y. Wu. Sparse PCA: Optimal rates and adaptive estimation. Annals of Statistics, 41 (6):3074 3110, 2013.
[22] J. Cape. M. Tang, and C. E. Priebe. The two-to-ine ton-tt-inffiitty norm and singular subspace geometry with applications nigh-dimensional statistics. Annols of Statistics, 47(5):2405 2439, 2019.
11

---

[23] M. Capitaine. C. Donati-Martin. and D. Féral. The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nomuniversality of the fluctuations. The Annals Probability, 37(1):1 47, 2009.
[24] S. Chatterjee. Matrix estimation by universal singular value thresholding. Annals of Statistics, 43(1):177 214, 2015.
[25] P. Chen, C. Gao, and Y. Zhang. Partial recovery for top-k ranking: optimality of MLE and suboptimality of the spectral method. Annals of Statistics, 50()):618-1155,, 2022.
[26] Y. Chen, C. Cheng, and J. Fan. Asymmetry helps: Eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices. Annals of Statistics, 49( (00[)):0 ):435, 2021.
[27] Y. Chen, Y. Chi. J. and C. Ma. Spectral methods for data science: A statistical perspective. Foundations and Trends in Machine Learning, 14(5):566 806, 2021.
[28] C. Cheng. Y. Wei, and Y. Chen. Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise. IEFE Transactions Information Theory, (777387770, 2021.
[29] Y. Chikuse, Statisticy on Special Manifolds, volume 174 of Lecture Notes Statistics. Springer Science Business Media, 2012.
[30] D. Donoho and M. Gavish. Minimax risk of matrix denoising by singular value thresholding. Annals of Statistics, 42(6))2413-2444 2014.
[31] J. Fan, W. Wang, and Y. Zhong. An &oo cigenvector perturbation bound and its application to robust covariance estimation. Journal of Machine Learning Research, 18(207): -2, 2018.
[32] J. Fan, K. Wang, Y. Zhong, and 7. 7hu. Robust high dimensional factor models with applications to statistical machine learning. Statistical Science: a review journal of the Institute of Mathematical Statistics, 36(2):303, 2021.
[33] Fan, Fan, Han, and J. Lv. Asymptotic theory of eigenvectors for random matrices with diverging spikes. Journal of the American Statistical Association, 1 117(538):996-0009 2022.
[34] O. Y. Feng, R. Venkataramanan, C. Rush, and R. J. Samworth. A unifying tutorial on approximate message passing. Foundations and Trends in Machine Learning, 15(4):335-55 536. 2022.
[35] C. Gao and Z. Ma. Minimax rates in network analysis: Graphon estimation, community detection and hypothesis testing, Statistical Science, 36(1):16 33, 2021. doi: 111214/19-ST7777
[36] Gavish D. L. Donoho. The optimal hard threshold for singular values 4/v3. JEEE Transactions on Information Theory, 60(8):0040-5000 505000555332200000 2014.
[37] G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, edition, 2013.
[38] F. Haddadi and A. Amini. Eigenvectors deformed Wigner random matrices. IEEE Transactions on Information Theory, 67()):1069-1079, 2021.
[39] F. Krzakala, J. Xu, and L. Zdeborová. Mutual information in rank-one matrix estimation. In 2016 IEEE Information Theory Workshop (ITW), pages 71-75, 2016.
[40] J. Lei and K. Z. Lin. Bias Bias- adjusted spectral clustering in multi- multi-layer stochastic block models. Journal of the American Statistical Association, pages 1-13, 2022.
[41] L. Lei. Unified 82- eigenspace perturbation thcory for symmetric random matrices, arXiv preprint Mxxi::999.04777 2019.
[42] G. Li, C. Cai, H. V. Poor, and Y. Chen. Minimax estimation of linear functions of eigenvectors in the face of small eigen-gaps. arXiv preprint 1oXiv:2104.032240 2021.
[43] S. Negahban. S. Oh, and Shah. Iterative ranking from pair pair-wise wise comparisons. In F. Pereira, C. Burges. L. Bottou, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[44] S. O'Rourke, V. Vu, and K. Wang. Eigenvectors of random matrices: a survey. Journal of Combinatorial Theory, Series A, 144:611-422 2016.
12

---

[45] S. O'Rourke, V. Vu, and K. Wang. Matrices with gaussian noise: optimal estimates for singular subspace perturbation. IEEE Transactions Information Theory, 2023.
[46] A. Pajor. Metric entropy of the Grassmann manifold. In Convex Geometric Analysis, pages 181-188. Cambridge University Press, 1998.
[47] M. Peng. Eigenvalues of deformed random matrices. arXiv preprint urXiv:1205.085 2012.
[48] B. Recht, A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011.
[49] K. Rohe, S. Chatterjee, and B. Yu. Spectral clustering and the high-dimensional stochastic blockmodel. Annals of Statistics, 39(4): 1878 - 1915, 2011.
[50] P. Rubin-Delanchy, Cape, M. Tang, and C. Priebe. statistical interpretation spectral embedding: the generalised random dot product graph. Journal of the Royal Statistical Society Series B: Statistical Methodooogy, 84(4):144611473 2022.
[51] J. W. Silverstein. The spectral radii and norms of large dimensional non-central random matrices. Stochastic Models, 10(3):225-532, 1994.
[52] D. L. Sussman, M. Tang, and C. E. Priebe. Consistent latent position estimation and vertex classification for random dot product graphs. IEEE Transactions Pattern Analysis and Machine Intelligence, 36(1): 48-57, 2013.
[53] J. A. Tropp. An introduction to matrix concentration incqualities. Foundations and Trends in Machine Learning, 8(1-2)11-33, 2015.
[54] R. Vershynin. Hfihh-Dimnssin Probability: An Introduction with Applications in Data Science. Cam- bridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[55] V. Vu and J. Lei. Minimax sparse principal subspace estimation in high dimensions. Annals of Statistics, (6):2905 2947, 2013.
[56] M. J. Wainwright, Hige-diiensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[57] K. Wang. Analysis of singular subspaces under random perturbations. arXiv preprint 27X1902403.09177 2024.
[58] D. Xia. Normal approximation and confidence region of singular subspaces. Electronic Journal of Statistics. (5())33798-388 2021.
[59] Y. Yang and A. Barron. Information ceermation-thhortiic determination of minimax rates of convergence. Annals of Staristics, pages 1564 1599. 1999.
[60] Y. Yu, T. Wang, and R. J. Samworth. A useful variant of the Biometrika, 102(2):315- 523,,,3332200 2014.
thcorem for statisticians.
[61] A. R. Zhang, T. Cai, and Y. Wu. Heteroskedastic PCA: Algorithm. optimality, and applications. Annals of Statistics, 50(1):33-80, 2022.
[62] Y. Zhou and Y. Chen. Detlated HeteroPCA: Overcoming the curse of ill-conditioning heteroskedastic PCA. arXiv preprint arXiv:2303.06199 2023.
[63] Z. Zhou, Zhou, Li. and C.-H. Zhang. Rate-optimal subspace estimation random graphs. In Ranzato, A. Beygelzimer, Dauphin, Liang. W. Vaughan. editors, Advances in Neural Information Processing Systems, volume 34, pages
Curran Associates, Inc., 2021.
13

---

A Proof of Lemmal 1
Proof. Let 0 lim (o Ax* For any u" sa-1, by the Baik-Ber Arous-Péché (BBP) phase transition (8): see also Theorem 2 in (88), the top eigenvector of Y obeys
if 1 if & 1
(u, 2²
(23)
0
Let = [n/p], and consider
u' 1 (1 T
E R.
(24)
Without loss of generality, assume that de (u, u²) = 1|ze u² bo since otherwise repeat the following argument with - u instead of u. We have
1/2
1
do (u, u')
max l uil RE
U1 u/?
(25)
Expanding the term inside the square root,
2
2 + 1 2(u", un)
(26)
1=1
where the last equality follows from the construction of Equation inequality, we have
24
By the Cauchy-Schwand
Σ
U1
V U4
1
(u" 2)²
(27)
where the last equality follows from the construction of u² in Equation (24) Plugging Equation 27 into Equation 26 we obtain
Σ
Uu up 1 (u", u)² + 2(ux,, u) = (1 - (u', u))
When 0 1, applying Equation 23 yields that
lim inf 2-000
U4
liminf (1 (1-("m" (u=, uz))²
(28)
n
holds almost surely. Again using the fact that 0 > 1. we have
1
)
(29)
g2
02
0
20²
Combining Equations
25
28
and
29
it holds almost surely that
/ (lu 104-4,3 ut u;12) 1/2 lim
lim inf doo (u, u²)
lim inf n-+00
20
V1 n/uu"
where the last inequality follows from s = [n/m]. Since μ S n, it follows that
lim inf doc (u, u lim
P
n-000
20
202
V # n
n00
2 02
almost surely. By the definition of 0, have
o lif d u²) 2 lim n
02 /2 n4
lim
2/
n-30
2
completing the proof.
14

---

B Proof of Lemma 2
Proof. The upper bound
1 aj
Ki: |u,l
auHl 5
follows trivially from the fact that ||l|| 1. To prove the lower bound, we consider the disjoint intervals
log 1/2 n,
i
It
log (2+1)/2 n, log 6/2 =/222)
if E (1.2...., 2/
(30)
log-L/2 4/2 n, log (121-1)/2 m
log
if [T] 1
Recall the definition of L from Equation
log 2m) log log n
L
Rearranging terms, we have
log log
log( (2n).
2
Exponentiating both sides of the above display,
log 1/2
v 2m
Noting that by Equation (30)
[21-1
U
ft [oog"
I./2
n,
2n
t=
for any i [ni] such that [ui]
$ U Fe, we have
-1
L/2 1
|n:| < log
V2n
and therefore, summing over all i [n] such that |oil $
-
It yields that
Σ
of
Σ
1
S
1
(31)
2n
2n
t:
St
Let x, [(i: |us| HeH for all l {0, 1,
[L]
1}.
We have
Σ
of <
24
max E.
log'
where the last inequality follows from the definition of Hf in Equation l E {0, 10 [Z] 1) on both sides, we have
Summing over all
11-1
It
Σ
2 =1
Σ
2
E=0
log
n
: 11
&
EP. 141-
2
where the last inequality follows from Equation (I). The above further implies that
Zt
Et
[
max 8Ef0,1,-
>
(E(0,1,--1[11111
log'
log !
8=
15

---

Hence, rearranging, there exists an to E {0, 1, ... [ 1 such that
> logoo-1 n log cu+1 n Ptg 2
log c0
log n
where the second inequality holds for suitably large by the definition of L given in Equation
Finally, that for all [n] such that |os| Ita we have [ys log (fo+1)/2 -lg+((++1) n by the definition
of It in Equation (30p. Taking
log
(fo+1)/2 n
if to {0, 1,.1..... ,[L] 2} if lo = [1] -1
a
log
1.22 m
yields that
{i:
|ual 2 aull 2 2t
aB log n
We complete the proof by noting that Org in A. where A is defined in Equation 10
C Proof of Lemma 3
Proof. Expanding the right hand side of Equation 17 have
02 2
Σ
My + Wes) (MG
n(n + 1)
IsisiEn
2
Mi Mir)
2
n(n + 1)
n(n + 1)
sj
IsisiSn
Isigišn
4
Σ
Wi MM.. -Mis)
n(n
Isisss
Subtracting 6² on both sides and applying the triangle inequality, we have
102 0²| S n(n + 1)
Σ Isisisn
MM
Mis) 2 +
2
Σ
W
0²
n(n + 1)
Isisisn
Σ
Wy (Mr. Miss
+
n(n + 1)
Isisisn
(32)
|M M
+
Σ isisisn
W3 o²
nnn + 1)
n(n 1)
a(n 11) tr W (M* (M'-N) M) (M-
2
2
Wa M NLu)
(n
1)
We proceed bound each term in the last inequality of Equation (32) separately.
For the first term in Equation by an argument analogous to that of Equation (3.15) in 27
2
8r
(n + M
M
<
n(n + 1)
By standard matrix concentration incqualitics [33 54 with probability at least O(n -).
W S 5 Vw n logn.
(33)
Combining the above two displays, we obtain an analogue of Equation (3.16) in [27], namely that with probability at least O(n )
M Mr
200e
<
(34)
n(n +
n +
16

---

For the second term in Equation 32 applying standard concentation inequalities for subexponential random variables (see, e.g., Chapter in (54).
s 2exp { - min { nnn + 1)u ? vw {
21a
Σ ISiSISh
(W3 02) 21
where e >> 0 is an absolute constant. Taking ( = 2uw /n(n + 1) log n/cc and dividing through by
(n + 1)/2, it holds with probability at least O(n 8) that
2
4vw Vlogn
W3 o²
(35)
n
en
IsiSisn
For the third term in Equation 332 using the matrix Hölder inequality (see Corollary IV.2.6 in [15
we have
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 most rank 2r, we have
tr W M M) S
W M'
M
Applying Equation (33 and following an argument analogous to that in Equations (3.12) and (3.15)
in [27] have that with probability least O(n +).
W 5Vwnn and ||M- M S 1
follows that with probability at least -((
2 W (M* M) S +
200
(36)
(n + 1)
For the fourth term in Equation
32). we have
Wi
M Mo.)
I max iE(n]
W I| - M
1=1
Σ
n
We (M
Ma)
2000wr 3/2
(37)
n(n 1)
Applying Equations
34
35
36
and
37
to Equation
32
with probability at least 1 Onn-5).
400ww
4ew / log n
200 10 Tog
0²
n
cn
3/22
out to show.
D Proof of Theorem 1
Without loss of generality, we derive our results under the assumption that
doc (u, u²) 1 u loe.
Otherwise, we can replace u with -u and obtain the same results. We remind the reader that we use e and C denote constants with respect to n, whose precise value might change from line line. To prove Theorem I we first state and prove few technical lemmas.
17

---

D.1 Technical lemmas
Lemma 5. !f| /wn, then under Assumption holds with probability least (n (8) that for all & E [n].
80v vw log + 120/mww
min flu - ubl, /uee + will 5
(38)
|
Proof. We largely follow the proof of Theorem 4.1 in 27 albeit with 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 o² in their results with the subgaussian parameter (i.e., "variance proxy") pw. Here, we only sketch out few key points and refer the reader to Section 4.1.4 of [2 for full argument. For each & [n], we construct leave-one-out copy Y (f) as
y X W(O
where
We:: 0
if (i,}}
otherwise.
For each 8 E [n], let X and (e) denote, respectively, the argest-magnitude eigenvalue of Y and its corresponding eigenvector. Without loss of generality, flipping signs if necessary, we assume that
doo (u, u²)
|| u
loo.
By Equation (4.20) in 27 with probability at least
(n=8)
we have
(E) ug
20 2ww
ub
1
12
(39)
|**1
By Equation (4.15) in 27 we have
4 Y ( (1)
u (
u
(0)
u
Following the argument just after Equation (4.18) [27], replacing the Gaussian concentration inequalities with subgaussian concentration inequalities, one can show that
y u (0) s 5 logn + 5/vwn luel + 5//wn 2 (t)
with probability at least - O (n +). Combining the above two displays and rearranging slightly,
[
5/Dwn |**
||u - 2 I 3V1 log + 5 luel
A
Since A 2 /0wnn by assumption, it follows that
/0//ww log n + 40 n uug
||u u 11 <
(40)
|
Combining the triangle inequality with the trivial upper bound have for any l [n]].
||u - 11) 1loc I |
(10 we
lue uil < ui 2 +
u (0)
Applying Equations 39 and 44 holds with probability least 1 O(n -8) that
20 Pw
40 log + /w /uel
ue 2/15 5
|+
|^1
20, T
40 vw logn n + /ww uF + 40 Pww Ue u
[ +
A**
18

---

where the second inequality follows from the triangle inequality. After rearranging terms and using the fact that | 2 /ww,, we obtain the desired bound
80yww logn 120 120//wnlae
me uil
|
for all & [m]. completing the proof.
Lemma which controls the behavior of the index set i in Algorithm follows from an application of Lemma 5
Lemma 6. Under the model in Equation 1 with M X* x suppose that Assumption hools
and Assumption holds with constant C > 2400/e0, where eo E (0, is fixed. For a E A, define
f. (i: [1122a).
where u is the leading eigenvector of as in Step 1 Algorithm following all hold with probability least O(n log n)::
! For all sufficiently large n, the
(i:lu: 2 (1 + co/ /2)a] _ fa S (i: | 2 (1 (-/oo//)a
(41)
(1=c2) < |41
(i:
utll < <(1 + co)a
(42)
{:: |u] 2 a)
(i: |4] > (1)
(43)
and
S {i |u5| 2 a}.
(44)
Proof.
Fix a E A. For any i E Ia. we have |us| 2 a by definition. We have
80 logn n + 120 /w <a-
}
P
U
|ufl
iel.
80 80/ww log + 120 Dw
IP
|ufl < |uul
(45)
|
80/ww logn n + 120 [wnluul }
PPP.
U sEim]
[ufl <
|uil
O(n
where the first inequality follows from the fact that |uy| 2 for i fas the second inequality follows from set inclusion, and the last inequality follows from combining the triangle incquality with Lemma If
u 2 a 80/vw logn + 120 uz]
(46)
|
and we take C₁ 2400/eg Assumption then we have
|u6| 2 80c0 / ww logn 120c0 /iwn
60
1
60
[u 2
2400 Vwn logn 2400 / logn
30
V
20
log
Since 2 1/2, after rearranging terms.
|u7| 2 1+
20 2l
Go
a
30
Co
2
1+
20
Vlo
Go
(1
15
Co
(47)
> (1 (1-60/1 (2)///))a,
19

---

where the last inequality holds for all E [n] satisfying Equation (46) (i.e., all i E [a) when n is sufficiently large. Thus, we conclude that, applying a union bound followed by Equation (45).
(n iif
(Ia (d:lup] 2 - c0/2)))))
[uug] 2 =002))a3
(48)
80 80 log +120 +120 /20/wml U <a
2 1-P
U iel.
2 1 - O(
Following a similar argument, we can show that Equation 1 (n 8), and that, also with probability least (O
44 holds with probability at least
{i: 2)/2) |ulB} fi: co)a < 1,51)-
(49)
On the other hand, combining the triangle inequality with the bound in Equation holds with probability at least
38 in Lemma 5
it
On that for all i E in] satisfying [u:] (o/2)a
uss 2 |u - lus
ut1 2 (1
60 2
eD
60 + 20/2)ax
20vlog > a
30
where the last inequality holds when n is sufficiently large. follows that
P PIn 2 (i: |u51 2 (1 + =22)aa)
=
n
{usl 2 a}]
(50)
2 21-08 O(
Following the same argument, we have that Equation (43 holds with probability least Onn
and that
{i: |u|| 2 (1 co)a) C {ú: Wa 2 (1 + 60/2)a
(51)
also with probability at least - On $)
Combining Equation 48 and Equation (50) yields that Equation 41 holds with probability at least
1 - O(n Similarly, combining Equations (49) and (51) implies that Equation (42) holds with
probability least 1 On- A union bound over all A yields that Equations (41 (42) (43)
and (44) hold simultaneously for all a E A with probability at least - O(IA[n Recalling from
Equation 110 that |A| (log n) completes the proof.
The results Lemma lead to Lemma
Lemma Consider the model in Equation tions] 2 and and3 hhold. For each a E A, let
with M Xtuuu" and suppose that Assump-
To = (i: |ui] 2 a}
(52)
and define the set
Ao fa A: Hal 2 (a² log" log²2) n)-1),
(53)
where A is as defined in Equation (TPp. Let be the set constructed in Step of Algorithm with 3 = co/2. With probability at least 1 O(n logn), there exists an E Ao such that
T...
Proof. We first show that with probability at least On n).. for any a A satisfying
Equations (15) and (16), we have Ag and f. = Ia. where f., as defined in Lemma We then prove that there exists at least one a E Ao C AA such that both Eguations (15) and (16) hold. Having A chosen Step of Algorithm which satisfies Equations 15] and
established this, the value
(16) by definition, must an element of Ao C A. Since = i by definition, we must have / la with probability at least O(n logn), which will complete the proof.
20

---

Suppose that E AA satisfies Equations (15) and (6). Trivially, by the definition of Ao in Equa-
tion (53), Equation (I5) implies that E An- By Lemma 6 with probability at least 1 (n llg....
Equations 43 and (44) hold for all elements of A. Thus, in particular,
{i: [4 2 (1 + =n/2)a - (i |ug| 2 a C { |u, (1 (o=o0/2)ā).
By Equation 16 and the choice B cu/2 in Algorithm
f. {i: |u,] (1 <o/2)a} {i: |u,] 2 (1 2))
from which it follows that i. = la with probability at least 1 0 logn).
We now establish the existence of at least one E Ao S A satisfying Equations (15) and (T)). By Assumption 2 for sufficiently large n, there exists a E A such that Equation (2) holds, from which Ao immediately. Also by Assumption 2 there are no i [n] for which
(1 6n) E |u & (1 + En)a.
By Lemma 6 Equation (4)) holds with probability least O(n logn) for all elements of
Ao S A. and thus la Ta. Therefore, we have | = |Ta 2 (a² log ") nn)-1, where the lower-
bound follows from Equation 12 As a result, any such a guaranteed by Assumption [ satisfies
Equation [5).
By Equation 42 in Lemma
6 and the fact that a satisfies Assumption 2 with probability at least
1- O(n
log n1) we have
fi: (1 - co/2aa < wua < (1 + ca/2)a} = 0.
Thus, with B = 2 this particular a also satisfies Equation (16) and we conclude that with probability at least 1 O(n log n), there exists at least one E Ao such that both Equations (15) and (T6 hold.
Our argument above ensures that with probability at least 1 - O( l). there exists a E Ao satisfying Equations (15) and (I6). Thus, Ao constructed in Step2exxstss and our argument above ensures that / as constructed in 2tep satisfies i = fa = Ta. completing the proof.
Lemma 8. Under Assumptions that
7 and with probability at least O( ((n=))
) it holds for all i [m]]
1
|u,1
implies sgn (u.) sgn (ut).
24
Proof of Lemmna 8 Let i [n]] and suppose that |uf] > n with of > 0. The case for ut < 0
follows by an analogous argument and details are omitted. By Equation (38) in Lemma [ holds
with probability at least On" -8) that for all i [mi] such that ut 2 0.
luu ut1 2 (1 120/vww [>-
80/ww log
Wi
m
[
By Assumption 3 follows that when |^*| > 2400 1400/WW Pwwn
19 " 80vew logn
u, 2
20
|
Since ut 2 1/24/m by assumption, it follows that when | Z 2400./2wh we have
up 100gtw log n
|A1
from which we have u, > and therefore sgn (wx) = sgn (u²).
Lemma 9. Fix E A and {+13". For a random noise matrix W E Raxn satisfying Assumption 1 it holds with probability at least 1 - O(n that
Σ j.kEla
8j8kWar jk
S Cla.l ww log
(54)
and
max JE(n
Σ
8jSk jk
SCV SCVTal logn.
(55)
kela
21

---

Proof. Since {+1}" is fixed and the entries of W are symmetric about zero, we assume without loss of generality that is vector of all I's. By standard concentration inequalities [54] we have that for any 1> 0,
P
Wie 21 J.RE
Σ
< 2exp
2T 2vw
Setting Co Vvw log for suitably-chosen C Equation (54) holds with probability at
least 1 - (n +). Similarly, by standard subgaussian concentration inequalities bound over E [n]. holds for all t that
[54] and a union
max JEIN
Σ kETa
W 211
expx 2n exp
2 p Pw
Taking f2 Ca lew log for C > 0 chosen suitably large, Equation (53) holds with probability at least 1 O(n )) completing the proof.
D.2 Proof of Theorem 1
Proof. In this proof, we control the estimation error of under d There are two types entries of û, as stated in Step 5 of Algorithm [ One type is derived from i constructed in Step 4 of Algorithm[] [ and corresponds to large entries of u² The other type is given by the top eigenvector u of Y. corresponding to small entries of uz. We handle these two types of entries separately. In Part of the proof, we control the estimation error corresponding to the first type of entries, derived from G. 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 de (ū, u*).
Part Estimation error related to
We define the event & according to
& {[ X C2v/w log 1og n}.
(56)
On event & if X 0, then by the triangle inequality, we have
R 2 - - - C2v/w 5/2 0,
(57)
where the second inequality holds for all sufficiently large by Assumption B Similarly, for all sufficiently large n we have Ā < if < 0. other words, for all sufficiently large n, we have
sgn
sgn (X*)
on event & Hence, Step iin Algorithm guarantees that we work with the original Y when X > O. or with Y when X In either case, the algorithm proceeds with a signal matrix that has positive leading eigenvalue on Ej. Without loss of generality, we assume that A > 0.
On event E,, have
X
C2 C2y/ww (logn) Cv/w (log n) 5/2 A
(58)
where the second inequality holds for all sufficiently large by Assumption 3 Similarly, for sufficienlly large, following Equation (58), event E also implies
1/2 < A 2.
(59)
Recalling the set Ao from Equation (53 and Ja from Equation 52 above, for each a E Ag, define the events Eg,o. and & according to
Eg {i la),
(60)
22

---

where ī is as constructed in Step 2 of Algorithm and
83, == {Q sgn (ug) for all E La and Q& = 1 for all & E faj.
(61)
Define s E {=1}" according to
sgn (uf)
if e La otherwise,
8k
(62)
and for each a E Ag. define the event a as
Es.a
Σ
8y8kW
S CC
VW log n
(63)
For S given in Step 4 of Algorithm ! event ε E3
plugging in = QYQQQ Q and expanding, it follows that on the
82 = Σ Qu =
Σ
+
Σ
Sjsk
(64)
jikE
KET.
J.kETa
On the event ε2 O E3,a O E4,ar we can lower-bound this right-hand side, obtaining
Σ lulll kEe.
-CIall log 2 X'IT./a²2 ClTaly uw logn,
(65)
where the first inequality follows from the fact that event LLa holds and the second inequality follows from the definition of la in Equation 52). Using Equation (53) and the fact that Ag. we may further bound this by
Ta (X- - CVv (x--CvVw
S²Z
1/2 5/2 n) > 0,
log²
where the second inequality holds under Assumption 3 when is sufficiently large. Thus, on the event ε n E3 E we have Ej Yj8, 0 and thus $ is well-defined (i.e., it is the square root of positive number).
We now show that is close to its population target. Rearranging the terms in Equation 64) we have that on the event ε2, E3,a n E4,a,
52 x+
S Cl Vew Vw log n.
(66)
kEda
Dividing both sides by S Vx* EkEI, 14Tl. when the event ε2 E3,a N E holds, we have
ClaaVVww logn
Caall/ww logn
Cvew logn
V\
w
< (S+ (S+V>- Exel, (u]])
(67)
VX Σter, lug)
Vxaa
KET.
where 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 V Eker, |ug on both sides (note that this quantity positive by definition of T., and the fact that Ao). it follows that the event & NE N
S
1
CVVW log Xt >' jug]
CV/Ww logn
Cv/ww (log 5/2
(68)
V ΣtEL. u
>a
X
where the second inequality follows from the definition of T, in Equation follows from Equation (53).
52 and the last inequality
23

---

We move on to Step 4 of Algorithm I from which we recall, for ease of reference, that
Exe Yjx
for j [n].
(69)
VXS
Note that by Equation (57. the square root of À well-defined on & Rearranging the definition of by in Equation 669, plugging in Y = QY Q and expanding, we have for j E [n].
o,S
Imau + EkeiRs Qxr
V
VxA-
RET
Rearranging terms and adding ūj Eket Qua to both sides, we have for any j [n]
S
Pzsut) Σ
QkuuE = 83
Σ Equut
VX+
ke
kel
(VV
A- x
EQueue + EKEl Qi)
+
-1
Uiyus kei
VxA-
Dividing by EKEl Uuaut on both sides, again noting that this quantity is positive on the event & n E8
0 -y =0; 1 Vx EKei Uukut ) + A
S
-V=-)eenut
+ EKEl Qjs (70)
VXX Evel QuauE
Taking absolute values in Equation
(70) and applying the triangle inequality.
S
ENei QiiQui Qui W
0 Qirug S 10y1 1 Vx Exel Qux
+
1 15suug +
VAA Σtei QKA
Trivially, 12 I 1. Further, on the event E n E3,a. we have i= Ta and Qis = sgn (uz) = 83 for all j la. Thus, may write
S
+ Ener. SySkW jK
/x-
B3
Uz
p0 1
+
x- E lut] V x
(71)
V ΣvEr_
jugl
On the event E,, applying Equations (58) and
59 yields that
Cvew 1/ n
V
x
d=
(72)
Applying this bound in Equation
71
on the event &g n Ez n EE we have
S
Cvew 3/2 +
Exer, Wi A
|0, - 2n5u5 s |0,1
n +
Eket, |ugl
A+
ExEt 1
x
We remind the reader that in the proof, constant O may change its precise value from line to line. Another application of Equation (72) and using Assumption 3 yields
S
C CV log
EtEL, Sy.8
i Uurußl S |7,1
VX EKEL. lugl
\ EKEe, [1
On the event E, n E2, n Es n Es.0. Equation 68 holds and we have
CVt 1/2 n +
C Cv 5/2
Exer, 315k W 5kb
j0, - -, $ |00
+
(73)
x²
x
X ΣkEt_ |uj]
24

---

Define the event
E,
max jelml
Σ
8j
S CCVIaa log
(74)
keTa
Under the event & 7 82, n E3 n Es n Es,a. we can further bound Equation 73 by
C Cvv 8/2 n
CVew 8/2 n
CV Ta lw log
R - Qu5 - [89]
d
Xt|aaa
Applying the definition of Ao in Equation 53). on the event & n E2 E3,a N& O E it holds for all j E [n)] that
Cvew log
Cowwlog"
T
Uirug (0g
(75)
x
X²
Applying the triangle inequality and using the fact that [Qbزÿğ1 S by definition,
110)++1) Dvew log
log
5/2
C CVw log
5/2
Cvew log
10g Qjruzl
(10z,ü]+1)
X*
C Cvw
log
5/2
C Vuw log
10 23suy
X
Applying this bound to Equation
75
C Cv (log (log()ogn) 55/2 5/2 Cv (log (logn) n)5/2
j0g - Qpr 0, Uzrug1
x
x
Rearranging the terms, under Assumption 3 for sufficiently large and when the event & n &2,a E3,a n E1 n Es holds, we have for all [n].
Qiruğl C CVgw(log
(76)
Recall from Sf Algorithm that we set ūj = Qiyū, for all j E [r]] such that |uyl > (a X) log For any such j. the event & & E3, E4,0 n E Equation (76) holds, and have
i - = Qg - U3 = 1051110, - فHsuح] C Cww 5/2 n
(77)
x
Consider the event
3-11000 [1Q00- -1Q0--u'llo 10 5
Cvvw 1/2
X
Recalling the events ε E2,a, Es,a; Es and Es,a defined in Equations respectively, we have
56
(60
61
63
and 74).
((E) EEEn
Usa n Essa n Es,a n ES,a
AaEAo
(78)
=F U & E Es.a n Es n Es,a aa
where the last equality holds because for any a E Ao, the event is implied by the event E₁ & n Ea n Es n Es which is fact established in the proof of Equations 76) and (77).
Since by the definition in Equation (60). LaE are disjoint, it follows from Equation 78 that
(( >
Σ P & n Es,o n E4,a E
aEAAp
(79)
Σ
n (
PE n & n (Es,a n Es,a {s
aeA.
25

---

By the union bound and basic set inclusions,
PP (&1 n E2,a O (E3,a N a O Es ) = P n (Eg,a U& U ((3,))
< ( N [2
+ (E1 n (
+ +P + E2 n (.,))
$ P (82,a nEg,m) + (fi + (E%
Applying this bound in Equation 779
((E) 2
Σ
[P (2,a)) - (P(E2, n (33,)) + P(E),)) - P(C),a))
(80)
aEAo
The terms P(E and P(Eg,)) are bounded in Lemma 9 as
P(E (P(E5,)) I O(n 0(n-8).
(81)
For the term Plε2, n a we have
2(E n 3,aa)
= P
U
Qhk + sgn (ut), Laju U
{QaR $1,1 [
kEL.
kels
By Step in Algorithm I we must have
U kETS
Qkk 1, 1,1= 1o)=
U
+1, =
kEʃ
It follows that
P(E2, n (8 =
U
sgn (ux) # sgn (uk) 1 = laj
kEla
(82)
S
P
U kee
{sgn (ux)
sgm (ut)}
For any & Icc. by the construction of A in Equation
110
must have |ug] 2 a 2 1/V2n. Thus,
by Lemma 8 we can further bound Equation
(2) as
IP
&g,a) On ))
(83)
Applying Equations
81 and (83
to Equation 80). we have
P(E) 2 Σ
P &
- -(1AAol 8)
acAA
p
& U
n Eg
-)-olddom
O(1Abin
\aEAoo
- O(1Aoon25)
n (i
2 1 - P(E -P
AaEAu
Under Assumption have P(Ef) < O(n -8 #logg), and it follows that
P(E)) 2 1 - 0n logn) n) P (n { {i+ ( LaE.D
0(1Agln~9)
Applying Lemma 7 to the right hand side yields that
IP(8)= Onn log n) - On -t) O(1Ao/n -8) 2) Onn~~10g n):
where the last inequality follows from the fact that |Aol S |A] and |A| O n)) by Equation 10
26

---

At this stage, we have shown that with probability at least 1 - O(n logn),
Cv log
3/2
Qu u² u'llco I
(84)
A
Part II. Estimation error related to u.
Note that Step | in Algorithm I further refines T to adjust the estimates of small entries u". In the remainder of the proof, show that this refinement does not affect our bound in Equation (84). By Lemma 5 it holds with probability at least O(n =) that for all j E [n]]
Ju -=] ك 80 log n + 120 1200pr /ewn kg
X 800/w logn X
120 /20
(luy) + -
where the second line follows from the triangle inequality. Rearranging terms and noting that X > 240//wn log n under Assumption 3
we have that with probability at least On =8) ,
holds for all j E [n] that
1
180/u log
120 /20/unn
Jug uzl 120 /200//T/
160 vw log
x
vlogn
That is, defining the event
{ j=1
160w2w log
|u,1
E6 = n
[1, uzl
+
(85)
X
vlog
we have
P(E $)
(86)
Note that by Equation (58) and Assumption 3 when & holds, we have /^^ /^-/X| S for sufficiently
large n. It follows that when & holds, for all j [n] such that |25l S (vew A) log n, we have
Juyl /Pw log n X 2 2/WW log
(87)
where the inequality follows from Equation 58) We have
Define the set J = {j |uy1 S (Vuw / log
162 /ww log
IP
U jEJ
|ug - -z/l >
X
<
U
My -Ggl= >
162 uw log n
n
+ P(ET)
A
VeJ
160 vw log n
|ugl
U JEJ
E
+ +0(n 8),,
Mog
where the second inequality follows from Equation (87 and Assumption Recalling the definition of Es in Equation (85) and using the fact that J S [n]. we have that the in the last inequality of the above display is subset of Eg. Following the above bound and basic set inclusions, we have
162 /Ww logn n }
IP
U jeJ
uz
P(E O(n *) s O(n -)).
Combining this with Equation probability least 1 O(n
84 and recalling the definition of à in Step 5 we have that with
d (1, u²) < Cvow 3/2
x
set out to show.
27

---

E A new estimator for X*
Consider Y and S as constructed in Steps and respectively, of Algorithm |
We can estimate X
by
ExEl 1²x) !/|n02
(88)
$2
Proposition | controls the estimation error of À given in Equation 88
Proposition 1. Under the model in Equation 1. suppose that Assumptions 7 22 and 3 hold and consider the eigenvalue estimate X as defined in Equation (88). For n sufficiently large, we have
- X² S vew /ow 10
with probability at least 1 O(n llogn).
E.1 Technical lemmas for Proposition 1
Our proof of Proposition which appears in Section E.2 below, makes use of two technical lemmas, which we establish first.
Lemma 10. Let W E Ruxa be a random matrix satisfying Assumption 7 For a fixed 8 E {+1}", for any Ao. with probability least O(n (n)-
8h W
< <Cowl Ia VVlVoogn
(89)
Proof. Since E {=1)" is fixed and the entries of W are symmetric about zero, without loss of generality, we assume that is vector of I's. Reindexing if necessary, we assume without of
generality that la = [K]. where K [Ta 0. We have K > 0 since É Ao and by the definition
of Ao in Equation 53 |al 2 (a log
0. It follows that
K
Wik
nII 0²
Σ
W jk
=nKo
nKoo +2
W imliskiK
Σ
(90)
j= k=1
71 + 13,
where
Σ
2
W +2
Σ
W -KKo
71
kk
K++kk=l
k=1
1SicKeK
1/2
Σ
W and
#-K+1iskete
73 Σ Σ
W
J=1 ISKKIKKK
will bound these three quantities separately.
We begin by bounding in Equation (90). For ease of notation, define N = K(n K/2 + 1/2).
Ya a sum of N independent sub-exponential random variables. By Equation (2.18) [56), for any t e 20,
ml N
2 vwt)
$ 2c NN2/333
Taking N- logn yields that for all suitably large n, with probability at least O(n O(n-5), -8)
Inl < 16uw / logn 162w v Kn lo
(91)
28

---

where the second inequality follows from the trivial bound N < Kn. Turning 72 in Equation (90), define
A 1xlk Ix BR
where 1x E IR is vector of all I's and Ix is the K x K identity matrix. It follows that
"1
"
22 = Σ E
W je Σ
Σ
A
J=KIISSHASK
j=K+11skesK
By the Hanson-Wrighe inequality (see Theorem 6.2.1 in (54)) for 2 0, we have
Σ
Σ
WFRAKeW je
21
j=K+11sk ISK.SK
1
vn Kuw || )
S 2 exp
-emin
(n n (1-K)j K) A
where 0 is universal constant. We note that ||A|| I K2 by construction. Taking t (8uw/c)K vn- K log n, with probability at least 1 O(n -) we have
Suw Kvn K log n.
h21
Σ
Σ
S
(92)
Finally, to bound 73 in Equation 90). define
E K(K+1)/2
w =
where vech(-) 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 of
JK = ((1,, 12) S S S
that is, pairs (f1, i2) satisfying 1 1 S 12 < K. We note that 7a sum products of the form W(a (2) (i. such that (i1, (2,, E JK and one element of (i1, i2) agrees with one element of (2), while the others disagree. For (11, E JK with i < i2, there are 2(K 1) other pairs (11.22) JK satisfying this requirement, while for (11,22) E JK with ip ig. there are (K (K-1) 1) other elements of JK satisfying the requirement. In total, there are K2(K 1) such pairs, which agrees with the number of terms in 7s. We define matrix B E ())+) ((K+))/) by identifying its rows and columns with elements of JK and setting
((i)) max (drg (1 (1i2))81.22( dizhn ), Sish (1 St.52), 8 o1152)} for (1,, 12), (2) E JK, where
{ 0
if if otherwise.
6,
There are K2(K 1) entries in B that are equal to 1, while all others are equal to zero. Thus, we have |B K / - < K3/2, By construction, one can verify that
w Bw
Σ
Σ
Σ
Σ
WG je 73-
(6132)) Unitaee
ISRAEKK
Again, by the Hanson- Hanson-Wright inequality, for every 2 O, we have
12
P P(w"" Bu 2 1) < 2 exx c emin
2
B
VW
29

---

where 0 is universal constant. Taking t (8tw /c) B|l log yields that with probability at least 1 (n =)),
Suw
S/w K3/2 log nt,
hal
Bw
F log n
(93)
where the second inequality follows from our bound on |
Finally, plugging the bounds in Equations 9 and (93) into Equation (90). we have that with probability least 1 On ²), Equation
89 holds, as we set out show.
Lemma 11. Under Assumption 1 for any fixed {+1}" and any fixed u² ES" any A.
holds with probability at least
-O(n ") that
Σ Σ NET.
W
S 44 2ol log
Proof. Since s E {=1}" is fixed and the entries of W are symmetric about zero, without loss of generality, we assume that s is vector of all I's. Reindexing if necessary, we again assume that la = [K] without loss of generality, where K |/a] Rearranging sums, we have
K
K
uy
W
W
k=
K
K
K + Σ W 5
K
Σ
Σ
(uf+
Σ
W
j=1 kmj+1
j=1
1m
j
K+1
By standard subgaussian concentration inequalities
[54] [66] using the fact that ut is unit-norm,
Σ
2 4v nw AVwww2 2K logn
S 00
completing the proof.
E.2
Proof of Proposition
Proof. Similar to the proof of Theorem assume that A 0 without loss of generality. Recalling the quantity S as defined in Step of Algorithm and the fact that $ >> O from Equation (65) define
vx (EREF Quauk)
R
(94)
S
where we recall that i is the set given in Step 2 of Algorithm and Q E ggxx is diagonal matrix given in Step 3 of Algorithm [
Plugging in Y QYQ Q and expanding the right hand side of Equation 88
we have
nli
Σ
XQjuū
Quiut kei
S2
S2
kei
(1 u2}²
Σ QuAuE
+
Σ
Qua
22 1=1
kei
1=1
Kke
21*
n//102
+
u Σ
Ug Exee
22
S2
5=1
kel
eel
30

---

Applying the definition of R2 in Equation 94 and rearranging terms,
x = Ry + R2 Ej=1 (Ekes Qkx , n/i00
Ekei Quk Evel Qun
+2R "j
(95)
[xx=Ene QRAU?))
j=1
To control the term R in Equation defined as
95 we proceed bound related term Ra for all Ao.
V (EKEL, lutt)
R
S
We recall the events E2,0. and E..a for all a E Ao as defined in Equations 60
61 and (63)
in the proof of Theorem | For any E Ao. to control the term Ra, we divide S on both sides of Equation 67 stated the proof of Theorem ! follows from Equation (67 that
VX- Eket. lug| -1|=
CVvw log
R - 1|
S
avrS
holds the event E2,0 NE3ma n NE Following the previous bound, on the event E2 n 1Egn n 8,.00 we have that
RRa - 1/5 CV logn
CVew logn
aViS ax (EKEI_ (uāl) av X S VX
ExEr luj
CV/ww logn
C CV/W log 5/2 n
S A- CV- log 5/2
Lalaa CVuw logn
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 event & O 83,a E4.a that
RR. 1 Cv/W 1og
(96)
X
By Equation (96 and Assumption 3 for sufficiently large, we have
1/2 S R. 2
(97)
on the event &2, n E E4,0.
Recall E [+ defined in Equation 62 On the event & n E3,a O E4,,, we find that, using
Equation 95 to substitute for À and applying the triangle inequality,
Σラ=1 (ERES. s wk),))² - -n
K- x
x* Ra
1| RR²
(VX' Exer, |uk]
EkEL, 8k W
+ 2n
Σ u Exer [ug]
where we substitute R2 by Ra using the fact that on E2,ar we have i i= La. Ia. Continuing from the previous bound, it follows from Equation (96) that
ύ- x² xx CvvW 5/2 +
EE=1 (EEEL. st 9x)) n nl/al02
|R
1|
R2
x
(VA+ EKEt, lu
Ekel, SkWs
+ 2R
u
Σ [16]]
31

---

according to Applying Equation 977 to Ra in the above display, we have
C Ei= (EHEI. 8 wx)) m nl
h P- x² < Cvw log 8/2 +
(Vi=EKEL EKEl. lugl)
(98)
EKET, 2j W
+ C
EnElo u4l
For all Ao. define the events
2
91.a
Σ AkE
3k Wisk
- -n/Lalo?
S SCu Hal logo and
1=1
(99)
G2.
Σ
8k W jk
S 2// Tal log
kELa j=1
On the event εn n. NEgaa n n 191, n 92... we can further bound Equation 98
SuwlkalvToog logn + CV La log
π x x CVw 8/2
EkEt, [u]]
Vx (1
following the definition of I1.a and G2 in Equation (99 By the definition of la in Equation (52) follows that
π -- S SCVW log 3/2 n n Cuw La Vologn CVew La log
X+
X+ F
Lala
holds on the event ε2,a E3,a n Es n 91,a G2 Applying Equation (53) lower bound [al we have
yー S CVW 1/ n Cuw Sowvnlog log + CV S CV/ww 1/ n, A+ holds on the event a N 09,,a000,0000 092,. where the last inequality holds under Assumption when n is sufficiently large. Consider the event
(100)
g= -- x+ CV log 5/2 n By the proof leading to Equation (1O0). we have for all a E An E2 &E NE n n n G2,a C..
follows that
P(g) 2 P U E2 n E3,a n & n G1 O G2,a
LaEAD
Σ PP (E2.a Es n Es n n1,a n G2.a),
aEAr
where the first inequality follows from set inclusion and the last equality follows from the fact that TaEA, are disjoint events according to Equation (60). By basic set inclusions, it follows that
(())
Σ
P((2a)) - PPE2, n ( P(Ei,a)
Σ PP(G)))) j=1
AE
Applying Lemma 9 Equations
83
Lemma 10 and Lemmal
11 to the above display yields that
P(g) P(E2,a) - O(1Ao =
n {
- 0(1Aglm->)
aεA.
aE
Applying Lemma and using the fact that |Aol < LA| and Equation (T0). have
|A| = Oloogn) by its definition in
P(()) 2 1 - O(n O(1Ag - $) 2 Om (n- log
completing the proof.
32

---

Proofs for lower bounds of metric entropy under d2,c0
To prove Lemma 4 we first state a few technical lemmas.
E.1 Technical Lemmas
For a semi-metric p defined over a set K, we let [V,,, p) denote the d-covering number K under (see Chapter 15 in [56]). The collection of all linear subspaces of fixed dimension of the Euclidean space R" forms the Grassmann manifold Gn.y. also termed the Grassmannian. For points on the Grassmannian, with the (unique) orthogonal projector P E R onto U, which in turn is uniquely represented by P-UU where E R whose columns form an orthonormal basis of U. For any matrix A m=xx with singular values denoted by o, (A) for 1 S i < min(m, n). the Schatten-q norm || l,s, is defined for any S S xc
adopt the projector perspective [3] subspace U Gn.r is identified
1/9
min m.))) min,mmn)
|| |Als, =
Σ
(A(
For pair of subspaces U1,24 E Gn.r identified with projectors P1 U,U P2 , Raxn, respectively, we consider the distance ds, (+, induced by the Schatten-q norm
U.U
ds, (4,(41,12) |P P2l1s, | U2U,2 lss
(101)
Lemma 12 controls the covering number of Gn,r under ds..
Lemma 12 [46] Proposition 8). For any integer S n such that 2r any such that
1 4 & do and any 8 > O, we have
((--)) (-) )7)
Co
r(n-r)
S N ds,, 0r
where Co: C. > 0 are universal constants, ds, is the distance defined Equation the Schatten-q norm.
TOT
induced by
Let Vn, == {U E RaxT : UUU=I) be the n x Stiefel manifold [6 The distance ds, (1:)) can also be viewed as distance defined on V Nn,r- For pair of orthogonal matrices U, U2 E n.ro we let
ds, (U,, U2) == U U2U, lls.-
When q 2, the Schatten-q coincides with the Frobenius norm, and have
dsp (U1, |UU U2U
Define distance dp Vn,
dF (U U2) = min | - 1| rec,
(102)
Lemma 13 controls the covering number of Vn,r under de, which follows immediately from Lemma
12
Lemma 13. For any integer S S n/2 and for every > O, we have
xn-r)
Cov2r 2r r(n-r)
co
S SN(V dr, 8) s
8
where co, Co > 0 are universal constants and de is the
Proof of Lemma 13 We identify each element U of Vn,r with the element UUT in Gn and apply
Lemma to V. under dp. By the fact that (see Lemma 2.6 in (27)
U - U.U. (d, < U.U U.U -
33

---

we have
d ds2: v2
(V.. 8) & (V dr. SN Wn
and it follows from Lemma 12 that
covr r(n-r)
Co Cov2r r(n-r)
S SV
8
completing the proof.
For any 2 r, Lemma 14 relates the packing number of any subset IK C Var to its Haar measure and the covering number Va,,. Recall that the Haar measure on Var is the invariant measure under both left- and right-orthogonal transformation [29]. In other words, for any subset K C V., s.r and orthogonal matrices 11 E O, and T2 E Oy, we have
E11 (Ti K) = Eer (KK) and En (IK I2) Exs (K))
where
T ( EK] and := EK).
For any norm ||II|| defined over set K, we also use the notation M III-II, and VI., |l 1-.1.8) to denote the 6-packing number and ô-covering number of IK under the distance induced by III-II. respectively. With the above setup, we state Lemma [4 below.
Lemma 14. For S r < let En denote the Haur measure Var. For 1 < S and any K C s.r such that (n((K) 2 7 > O, for any unitarily invariant norm III on Rexr, we have
K, I1-111 -
M
2 N NNWW &Var (1)
(103)
and
8 2.2 S N V.r III-II 2 K. I1l-Il
(104)
Proof of Lemmal 14 The bound in Equation (I04 follows from the fact that IK C V s.ns and (see
Exercise 4.2.10 in 54
S N K, IIl-Il 4 s N (Vam II- 6)
M K, -1l
To establish the bound in Equation under ||- then
103
suppose that Var has 8-packing P (U(1)) liml
M U i=l
8 2 I1--Il
B
U
c Ver
where
IB
(
II--II
6 :
-=U
- $8/2].
Since 8- d-packing set, the sets B
(v(())
(0111,111111..00 5/2) for 1,2,..., .M are disjoint and we have
M Σ
EH
(+)
IIIIII- 2 EH
U
M
U II--II 2)
(Var) =1
(105)
1=1
For any U, Ü Vars there exists I E O2 such that TU = U. Since |||I|| is invariant under C., we have
TU. III-II 2 Ü. |II 2
P.B U. I1--I11
Since En is invariant under left left-orthogonal transformation. it follows that
U. |ll )
U, I1--111 2 = EH
8 )) U. |ll
EH
EH r- B
LB
34

---

Therefore, all IIl-ll-balls with the same radius have the same Haar measure, which does not depend on the particular choice of U due the invariance properties of II|III and Enr. We denote the Haar measure of a ||| ||-balls with radius 5/2 as
6 ) U, 11-11111
11)
((6/2) = EH1
BB
then follows from Equation (105) that
Σ En (
M
( I1-I1. 2) s 1,
Mx/8/2)
from which we conclude that M S 1/v(6/2). Taking the maximal such ö-packing set yields that
1
M (V.r. II-III, 6) S
(6/2)
Recall that K. is subset of V srr and En (K) set of KK under II-IIl. then
y. Suppose that 8x (V fi=1 is 8 c/verrng
N
11l111-11. 2
k U
(()
and by the subadditivity of measures,
V II--I: 2)) 2 EH UB B V .1l-11ll1 :))
Σ Exs
2 (n(() 2 v.
Thus, it follows that
(6) 21 = N 2 7M (V 11)
Taking the maximal 8/2-covering set yields that
K, III I1l 2
N
7M (.. (1)
Finally, by Lemma 4.2.8 in [54] we have
M K. IIl // 2 N K. II-IIl, 2
and
M (V s.r: II-III 2 M (V IIl
Combining the three displays above yields Equation (103), completing the proof.
Lemma 15 controls the Haar measure of (K(s,, r, v ur ur/n). We remind the reader that IK(s, r, v //rr/// is defined in Equation (20).
Lemma 15. For n/n 2 max(4, r and s 2 (12n/H4 u)) log (12n/u) we have
En (K(s,,,, (urr Vur/n)) 1 5.
Proof of Lemma
15 Define the set
8, r. ((8,71
L
UEVAr 101 V
where ||U denotes the entrywise too norm (i.e., |1 == max,, (U D) In what follows, we omit the parameters and abbreviate L(s,r, ///n) to L. Noting that for any U LS, have m0 S vp/n, which implies that |U1|,,00 S /ur/n. Therefore, L C K(s, r, /ur/n) and
SH (K(s, (K(s,,,Vur/nn) wwr/n)) 2 1 - E (I).
(106)
35

---

Since
L UfUeVar: |U 2 2/ 12
1=1
it follows that
εH (L) S SH (fUEVar: :
1
Since U is distributed according to the Haar measure on Va,,, the column U., 1 E R is uniformly distribution on Sam!. As result, we have
εH ((UEVar 1
# )}) -
p
n
11l12
where g ~ N(0, I,) (see Lemma 10.1 in [44). Combining the above two displays.
g oc
P
EH (L) S r
(107)
g
We introduce two events
E,,
|1
3n
log
and
E,2 = {1g1100 S 33log
By Lemma 10.2 in 44 we have for all 1
P (19112 2 S 2vsst) I exp(-t).
Taking t = 2 log yields that
IP (1991 < 2 2s log
1
g2
When 2 4p and (12n/p) ()) log (12n/ μi), one verify that
3n
2 log 2 2/2 log s.
Thus, it follows that
1
P( < IP |1 < 2 2s log
<
(108)
By standard Gaussian concentration inequalities and the union bound, we have IP (E (I1lll> 2 33 log 8
< 2s exp (-3 8) = "
(109)
On the event E Eg.2. one has
logs
1
V n
|gg||
33 logs/n
Combining Equations 108] and Equations
(109). it follows that
3 "²
PP
S P ( U (
|
Applying this bound to Equation (077) we obtain
gg x0
3r
E (L) S rP
(110)
lg 12
g2
n
By the assumption that n/p max (4, r). for any
we have
s 2 (12n/H) (4) log (12/p) ()) > 12r > V6r.
Combining the above bound with Equation (110 we have
(L) 2
Finally, applying this upper bound to Equation (106), we have
1 Err (K(s,, r, Vur/n)) (L) 5'
as desired.
36

---

F.2 Proof of Lemma
Proof. Set cgr 0
Under our upper bound assumption on 8 in Equation and
n/p 2 max r), have
a
96e
log(L2n/p) (12n/ log (12m/p) 12r,
(111)
Sca
cyur
so that we always have
12n
12n
Gr
max
log
(112)
/
1
Note that owing to our assumptions that 2 12 (122g and 8² 2 c/r/8e"n, we have S Consider the subset
K3 (n, V prr/)= = (U T U,, 0, for S sissn) n):
which is subset related (but different) to K(s,r, v /r//n) previously considered in Lemma 15 Our lower bound relies on the key observation that
pr/n). MIKr,, .2. 5) 2 (n, v /rr//,, 0o 26) 2 MM(K(n, vur/n) de. 2/s6). (113) where the first inequality follows from Exercise 4.2.10 in (54), and the second inequality follows from the fact that for any U1, U2 E (n, r, pr/ we have
d2 (U1,U)) 2 dr (U,,))
Starting from Equation (133), we proceed to obtain /sō-packing for (n, r, v pr/n)) under de. Since any U E (n, r, v pr /r) can be uniquely identified with an element in ((,,,, v pr///) by restricting it to its first rows. By the assumption that / max(4, r) and the lower bound in Equation [I1I. we verify that the conditions of Lemma 13 all satisfied. Thus, following directly
in Lemma 15 and Lemma 14 from the lower bound of Err (KK(s, /ur/n))
we have
M (K. V ur)nn) de, 2/58)
2 2 (Verr, dr, 4V56).
Applying the lower bound in Lemma 13 to the right hand side of the above bound, we have
cov' r(s-r)
M (n, V/r/n), de, 2/86)
2
(114)
2 (4/56)
Under our upper bound assumption on 8 in Equation 21 and n/p 2 max (4,
ci
96c Ioe@nlog(120))
n log 12n/ 2
28
384
dur
4μ
from our choice of it follows that
crr
+1
20
86282
384
7e282
which implies V50 S -ov Thus, it follows from Equation 114
that
r(s-r)
Vie
VTe
M (K, Vur dr, 2V88) 2 where the last inequality follows from Equation
2
Noting that VTe/4 2 Ve, we have
M (R, V /r/n),, dp. 28
>
1
exp
1s
2
4
Applying Equation [13) followed by Equation 112 we obtain
M (TK d2 02,
8) M [K, v /ur/n dr, 2
1
3nr 12n P
2
1
(115)
2
exp
max
log
p
32e282
82
exp
32e282
Taking the logarithm both sides of the above display yields Equation 22
37

---

G Upper bounds of metric entropy under d2,00
To provide complete picture, Lemma 16 establishes an upper bound on the packing d-entropy of Kr,, under d2,00 that matches the lower bound in Lemma 4 up to log-factors when å satisfies Equation (2
Lemma 16. Assume that 2 pr for r [n] and μ >> 0. For all sufficiently large and any v4/(n 1) < /ur/n, we have
x²
log M g 02 6) S
log n.
(116)
6²
Proof of Lemma I6 We obtain an upper bound of (K,, un 02 6) by finding an upper bound of N (Kr, 02,00, 6). Since for any U1 and U2 E R
d2,00 (U1,U2) U01 U2112,00
we have
N (Kr, 02 8) S N (Kr,yu || 112,0::0) 8). Thus, it suffices to obtain upper bound for N (Kr 12,,00 5) instead. Let
(117)
T {u 2 0: VrS--1 //ee $1}
(118)
For any U E Kr noting that v /ur/ /ur/n - 1, we define a mapping Ty, - T given by h(U) = (1 11 ll. 12, -., . .1 1I2))..11)
Indeed, h(U) E T since by definition, we have h(U) 2 0. |I((U))22 = /r and |A(U)) 1.
We pause to give a roadmap of our proof. Recall that for a set K, its exterior d-covering is a 6-covering, except that the exterior d-covering allows elements not in in (54)). To obtain ' (Kr,u, || 2,.0 5), we will explicitly construct an exterior 8-covering of IKr, under || 112..0. To do so, we proceed in three steps. In the first step. we construct an exterior 5-covering '6 of T under || ll In the second step, we divide the set Kr,,, into separate subsets (W.)eeT via the mapping h Kr,,. + T. In this way, each element in T associated with subset Up C K, For every E '6' (the exterior (6/2)-co set of T), we construct an exterior (8/2)-covering Eo of U. under || 112.00- In the last step, we take the union of C, over e E 6 to form set 6x, and show this set is an exterior d-covering set for Kr,p, under || |12,.0. Finally, we control the cardinality of Eg to obtain an upper bound of N (Kr,,s || 112,00, 5), which in turn will yield our desired upper bound on M(Kr.,, 6).
form the covering (see Exercise 4.2.9
Step Construct an exterior (0/2)-covering set of T under ||
Il
Recall that is given in Equation (18). Let s = [4/82.. Under the assumption that >
/4/(n - 1), we have & S n. We consider the nonnegative integer solutions to the indetermi- nate equation
21 + 22 + rs, ||0|000 S ss+1
(119)
and let
8 = (VEi. VEn) is a solution of Equation
119
(120)
By Lemma 17 have 6 forms exterior 8/2- 8/2-covering set of T under || Il Since without the constraint
| oo < 1, Equation (199) has (ntrs-1) solutions, have
T[1/82]
18
n + r8 1 <
')
e(n + 18)
( r T44/22
e((n (r(n+r[p [4/822)
(121)
r8
T8
Step 2. Construct an exterior (6/2)-covering set of U. under
||
112,00
For given e E E, consider the subset
U UU Krn h(U)- v.
(122)
38

---

our next step is to construct an exterior ccovering set under || I12. for Wp. For every i E [n]. consider a (6/2)) set C,, of u,8"-1 under the l norm. By Corollary 4.2.13 in [54).
60g
1,, -
for all E [n]]
(123)
Consider the
66 = ( E R Raxr O = (01. 081,0y ....... 0,)
T,)T,O. 0, E Ce, for E [n]]
(124)
We claim that E, is an exterior (6/2)-covering set for Up under || 1|2,00 To see this, note that for any E U, and any E [n]] since U., E u,S"=1 and C, is coveriig of v, under the le norm, there exists E C2 such that
0. S.-U,
S 2
for all E [n].
Let θ O,.,0.....,
0n) E En. It follows that
8
O 2
max =E(n]
S 0:
U.
S 2
Since 6, from Equation 119 have
|ollo S rs
(125)
any solution to Equation 19 has at most nonzero entries. By Equations 119 and 1200)
we also have
|101100 S
2
(126)
V8
By Equations
123 and
124).
16,|
S
6
r
II
69
12
Sr
where the last inequality follows from Equations have
125 and (16))
By the choice of s = [4/827, we
+2 [4/8²]
[6,l -
(127)
Step Construct an exterior d-covering set for K under ||
112,00
Consider the set
6x U bo.
(128)
"EW
we claim that this forms an exterior d-covering for Kr,,, under || 12,,0-
For any U E Ky since 6 is an exterior (6/2)-covering of T under || Il.o. we can find v E such that [|/(U)) 011o0 6/2. Consider matrix Ú E _g with rows given by
(U.UU. (U) 10
if hU) 0, (U) = 0,
Ú..
for i [n], where is an arbitrary element of Ce.- Recall the definition of U. from Equation 122 By construction, Ü Un. which implies that there exists E C, C 6x such that
8
θ
2'
where we use the fact that Eg defined in Equation (124) is an exterior (6/2)-covering of U,, For i E [ra] such that (U) > 0, we have
Ü,,- - U.. -..-UU..l =
2/
10, = 1 hu,)(( < 8
1
l;(U)
39

---

and for i [n]] such that (U) = 0, we have
8
Ü - U - h.(U)) S
Combining the above two displays. follows that
8
Ü U
max KE[N]
U
U2. -
2,00
Thus, we have found E '6 such that
1 U 12,,0
Ú 12,00 + 11 U
12,00 Sd.
and it follows that 6k is an exterior 5-covering set for K under
1|2,00
Step An upper bound on MM || 112,00: 6).
Recalling the definition of 6K from Equation (128) Equations 121 and 127
imply that
[6x <
Σ 3EE
13,l
(n + [4/00])
r r/4/67
12
, 4//8
14/021
Using this bound and the fact that '6 is an exterior 5-covering set for Kr,,a under || 112,00 Exercise 4.2.9 in [54] implies that
rf1/827
e (n +
1/881)
12
N(Kryurll |I. 1|2,00 25) 1 16
r 14/821
end²
+r
12
+y.
+
4r
Combining this with with Equation
117
and Lemma 4.2.8 in [54], we conclude that
60r
end?
48
M (KGryp d2 8) S N (K 02 8/2)
(129)
64r
Taking the logarithm both sides of Equation
129
have
64 +
8²
end²
64 +
82
48
log M (Kr 02, 8)
r
log
+
+
n²
log
82
64r
82
5
65r <
Ef
6
48
log
+
log
82
64
82
where the last inequality follows from 8 < Vur/nn < 1. Under the assumption that > /4/n and ur S the right hand side of the above display be further written as
log M (Kr,u d2 8)
65r
log
en
+
65r
log (24/n),
82
64
82
yields Equation 116 for all sufficiently large, completing the proof.
Recall the definition of T in Equation (18 and & defined in Equation (10), we have Lemma
Lemma 17. Let the set C - be as defined in Equation [1I8 and let h be an arbitrary element in T. Then there exists v e & such that
8 2.
|k 2/1
(130)
V8
where 8 is given in Lemma 16 [4/82.
40

---

Proof. The inequality 1/v5 & 6/2 in Equation (130) follows directly from [4/82]. To construct a 6 satisfying Equation (T30), we first construct a R" and then make slight modification to Ç to obtain u.
To construct ç, we set Lt be either [AAs] /s [M]s] /s, and follow the recursive procedure obtain an entrywise positive Ç 2 0:
h2 /s h23
if E
0,
2
(131)
if Сー -ー 20
for 2 Sii n. The construction given in Equation 131 guarantees that
h 2
max =E|n h4 v [170) /s, v [120]] h4
1
(132)
V8"
where the last inequality follows from the fact that va vb s Va a for any 2 b > 0. Now we show that following the procedure in Equation (I3I), have
(133)
for all & E [n]. We prove the above bound by induction on k E [n]. When k = 1, we trivially have
K
h
For the inductive step, suppose that for k > have
k 1
By definition in Equation 131.
k-1
0
<
Σ
h4
Σ
(134)
then
Thus, < [[[s]]
/s satisfies
k
h2
2
x
1=1
1=1
If, contrary to Equation
we have
<0
3
then
1
Σ
11
8
and thus C [ /s again satisfies
k
Σ
1=1
Therefore, Equation 133 holds for all l E [n]. Taking = n in Equation 133 and by the fact that |al/ obtain that
s||c| sr < 1.
(135)
41

---

Following Equation (311) we also have that sc; is an integer for every i E [n]. Combined with Equation (35). we have stronger statement that
(s1|<112 sr) E (-1,0,1).
If (s||si1 - sr) = 0, setting v Ç already guarantees that | and || - -2llo S 1/ Vs.
Otherwise, (+||c1 xr) = - 1, then by Equation (131), there must be io [xx] such that
8 0 = L s1
h
[k2 $1
Lh s] +
Setting
/ s/s, if 02 v Gh 1/8
Siz
otherwise
guarantees that ||01| = r and
1 - h /2 max max 1Si h4b / /// Nio
1
S
V8²
where the last inequality follows from Equation 132). Similarly, if (s|1(11 3 - 8T) 1, then we can
alter one element of Ç to obtain v, such that || 2 and ||0: |---l hll 1/v5.
Since so,² are integers for all i E [n]. s||u|ß = sT, and the fact that
s| I max h s+
kr(n)
where the last inequality follows from / I 1 for all h E T, we see that E 86
H Proof of Theorem 2
In this section, we use the Yang-Bare 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[] We follow the notation used [56]. Given a class distributions P. we let 0 denote functional the space P, that is, mapping from distribution P to parameter ((TP) taking values in some space Q. We let Ω x Ω >> [0, oo) be a semi-metric. Proposition 2 states the Fano lower bound (Proposition 15.12 in (56)).
Proposition 2 (Fano lower bound). Let {01, 02..0.. OM1} S Ω be 28-separated set under the p semi- metric, and suppose that is uniformly distributed over the index set [M], and (Z == j) Fg,, Then for any increasing function [0, 00) + [0, 20), the minimax risk is lower bounded as
inf sup Ee + (0((0TT))) Z 4(5) PEP
I(Z:J) 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-Ban Barron method gives an upper bound for the mutual information I(Z;
Lemma 18 Yang-Barron method (59). Let NKL(E;; P) denote the s-covering number of in the square-root KL-divergence. Then the mutual information is upper bounded as
J) & inf Nog + +
e>0
Proof of Theorem 2 To each (A* (*) SXx,, associate probability distribution A u on Raxx with density given by
( UW-
JN (W) = II
1515JER
where g(-) denotes the density of standard normal. We define the class of distributions
p= PP (A',U*) 9(x p,,)).
42

---

For Mr, M2, E R" and a pair of normal distributions N(H, I²) and (H2, I their KL- divergence is given by (see Example 15.13
[56]]
KL (L, I
N(2 I
U2 - 12l12
20
follows that for any PA Pu EP,
X²2
KL (PA.U; PA-Us) 1 20²
and thus, taking square roots,
V2X* KL(Px PA..;;) S DUU - -U;
dp (U U2),
(136)
2x
where the second inequality holds from Lemma 2.6 in [2
To apply the Yang-Barron method, we follow a two-step procedure (see Chapter 15 of [56]):
1. Pick the smallest such that s² 2 log NKL (P,s).
2. Choose the largest ò that we can find a 8-packing that satisfies the lower bound
log M[ d2 8) 2 4s + log 2.
Then it follows from Lemma 18 and Proposition 2 that the minimax risk is lower bounded by 8/2. For the first step, noting that by Equation 1 e-covering set for the vKL- divergence, we have
set for V nnr under de yields an
r(n-r)
(P, S dp, CoA /2r
where the last inequality follows from Lemma suffices to have
13
Thus, in order to have e² 2 log (P,,e) it
CoA*
e² 2 r(n - r) log
σE
which holds if we set E CoX* 22/o With this choice s, then follow the second step of the Yang-Barrow method and pick d to satisfy
SCor
log M (Kprr, 02, 8)
2 log 2.
(137)
o²
By Equation (15) the proof Lemma
we have
222
log M (Kr 02, 8) 2
log 2
(138)
32e2
for 8 satisfying Eqaution 21 that
Combining Equations
137 and 138 our goal to find 6, such
c2.2
8Cor
+3log2 o²
(139)
32c282
We pick to be
Coo fr
8
(140)
12eA /20
4e
6n 6nlog(12n/H))
One can verify that 5 satisfies Equation (21) under the assumption X & (6 To see that the 5 given by Equation (10)) satisfies Equation [139. we separate discussion into cases, one for large X*, and the other for small X². When
n log( 12n/u)
X 2
(141)
3Col4
43

---

by Equation 140 we have
COO Vr
8
(142)
12ed V2Co
and therefore, Equation 139
follows from
cjr²
9CorA*2
8Cor
log2
32e262
0²
x²
where the first equality holds from Equation 142 for all nt sufficiently large.
and the last inequality follows from Equation (44
On the other hand, when
n nlog( 10gg11m/p)
X < <
(143)
3C0u
by Equation (10)) we have
co
Hr
(144)
4e
V
6n (0g(12n///
and therefore, Equation 139
follows from
3rn log((1n//M)
8rn log(12n/p) + blggog
8Cor + log
32c252
σ²
where the first equality follows from Equation (44). the next inequality holds for all n sufficiently large, and the last inequality holds from Equation (143). Thus, conclude that the choice of å given
in Equation (140) satisfics Equation (I39). completing the second step of the Yang-Barros Barron method.
Finally, combining Proposition 2 and Lemma
18 we conclude that for universal constant 0,
EA. u 02 (0,U*)
8
( [ovT X
pe (log(n/u))
inf sup T (A-,U))E0(X w.r)
2
c
V
completing the proof.
I Additional experiments
Here collect additional experiments complement our simulations in Section 5
1.1 Additional numerical results on rank-one eigenvector estimation
We provide additional details for the experiments previously discussed in Section Recall that observe
M W A + W.
and wish to recover u* E $n-1, We refer the reader to Section 5.1 for the details of how X u² and W are generated and how we run Algorithm
In Section 5.1 we mentioned that under Laplacian noise, as shown in the third column of Figure [ the estimator given by Algorithm [ seems have slight dependence the coherence parameter u.. We give close examination of the estimation error of the largest entry of u² in Figure 3 with shaded bands indicating 95% bootstrap confidence intervals. Figure shows that the estimation error of the largest entry of u² for ū is seen to be much smaller than 10 while in the third column of Figures| [] the estimation eггoг d (ū, u²) )) is well above 10 This indicates that the dependence [ on observed in the right-hand subplot of Figure [ comes not from estimating the largest entry of u" but rather from estimating the other entries. our experiment, the other entries all nearly incoherent (that is, they have magnitude at most ((ylog n//n), whence their estimation errors are expected to have no dependence on μ asymptotically. Thus, the slight dependence on exhibited Figure iss most likely to be small order dependence compared to the error rate stated in Theorem and should not affect the asymptotic eπror rate.
44

---

10-1
Error (Log Scale)
10
10-3
2500
5000
(500)
10000
12500)
15000
2300
5000
750k)
10000
12500
15000
n
Figure 3: Numerical enror in recovering the largest entry of ut" as a function of matrix dimension by the leading eigenvector (blue line) or the estimator given Algorithm (orange line) for three different choices of ||"=" co 0.8 (dotted lines), 0.55 (dashed lines) and 0.3 (solid lines). The plot on the left corresponds to u** generated via the Bernoulli scheme, while the plot on the right corresponds to the Haar scheme.
1.2 Additional numerical results on rank-r eigenvector estimation
We provide additional details for the experiments previously discussed in Section 5.2 Recall that observe
== W U'A'' +W
and wish recover U* _R In addition the rank-2 setting discussed in Section 5.2 include experimental results for the case when M has rank 3. We also provide estimation error under d2 for our estimate Ò in Algarithm 2 and the spectral estimate U, to complement our results under dx reported Section 5.2] The experiments follow the same setup outlined Section 5.2 and
we refer the readers there for details regarding rumning Algorithm 2 the generation of A U and W.
We first provide more details as to how we obtain the estimation error under d2, Normally, since
d2 U*) min
üT ŪT-U"* U 2,00
reo,
obtaining the d2.00 estimation error requires finding an orthogonal matrix that minimizes a nonsmooth function, which hard to achieve. In 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 Ü, rather than searching over all r E O,. By assigning each column of Ù the sign of the corresponding column in U* resolve this ambiguity and can obtain the d2 estimation error.
Figure compares the empirical accuracy, measured by d2,20, of estimating U* via the r leading eigenvectors U of Y (blue lines) and via Ü produced by Algorithm 2 (orange lines). Shaded bands are generated from point-wise 95% confidence intervals using bootstrap approximation. Similar to the rank-one setting, Algorithm 2 recovers U* with much smaller estimation error under da compared to the naive spectral estimate, especially when the coherence μ is large. The figure also shows that Algorithm 2 performs well under different noise distributions.
M" having rank-3. compares the empirical accuracy. measured under doc. of estimating each ui for & = 1, 3 via the leading eigenvectors of Y (blue/purple lines) and via úū given by Algorithm 2 (orangerred lines). Shaded bands are generated from wise 95% confidence intervals using bootstrap approximation. As in the first plot of Figure 2 under Gaussian noise, the estimation error of ū4 shows little to no visible dependence on μ, and is much smaller compared the leading cigenvectors of Y. Under Rademacher noise, in the second plot
Figure corresponds
45

---

Method
10-1
Spectral
Our Method
12,00 Error (Log Scale)
1
0.55
10-1
0.3
0.8
10-2
2030)
Hisi
(805)
1000
12000
14030
2830
6980)
st30
10000
12raj
1900
2850
dieg
soea
mnte
1300
1400
Figure 4: Error as measured in d2,c0 as a function of matrix dimension ni by spectral estimate (blue) and the estimator in Algorithm 2 (orange) for three different choices of || 0.8 (dotted lines), 0.55 (dashed lines) and 0.3 (solid lines). Columns correspond to W being Gaussian (left), Rademacher (center) and Laplacian (right). The rows correspond to the signal matrix having rank-2 (top) and rank-3 (bottom).
Spectral, A
Our Method,
10-1
Spectral, R Spectral, N
0.3
0.8
Our Method,
foo Error (Log Scale)
Our Method, k=3
10-2
1008))
15030
3000
15660
3000
10000
Figure 5: Error measured in dos as a function of matrix dimension n, for the three leading signal cigenvectors u., k = 2, 3 (line width) by the spectral estimate (blue/purple) or the estimator given in Algorithm
2 (orange/red) for three different choices of ||u*| oo: 0.8 (dotted lines), 0.55 (dashed lines) and 0.3 (solid lines). The plots correspond to W being Gaussian (left), Rademacher (center) and Laplacian (right).
of Figure 2] the dependence on again appears slightly reversed from that of the spectral estimator. For Laplacian noise, as the third plot of Figure 2 there again seems to be 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 in Theorem and should not affect the asymptotic error rate,
I.3 Comparison with AMP-based eigenvector estimation
As mentioned in the main text, to the best of our knowledge, we the first paper consider the problem of non-spectral entrywise eigenvector estimation. The nearest obvious method to serve as comparison point, we were insist upon one, would likely be one based on approximate message passing (AMP; see [o4] an overview). AMP methods make explicit coherence assumptions, the underlying mechanism essentially requires incoherence: inherent 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 mean field assumption whereby the empirical distribution of the entries of u' converges &g some distribution Since
46

---

Method
Spectral
Our Method
AMP
30 Error (Log Scale)
Villur
3/
3n
10-1
3n
10
3 10
x 10a
6 10
10
2 10*
(Log Scale)
Figure 6: Estimation emror under d as a function of size n, by approximate message passing (AMP; green), the leading eigenvector (blue) and Algorithm 1 (orange) for /n|l mu||uullo equal to 3/3 (solid lines), 3/1/4 (dashed lines) or 3/5 (dotted lines) under Gaussian noise. Each data point is the mean of 30 independent trials.
AMP-based methods are tailored to fz-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 comparison against Algorithm|] for the sake of completeness. The experimental setup mirrors that of Figure [I but now includes estimation error for an AMP-based method, as well. We generate u" according to the following procedure: set random entry of u* to be a E (3m1/3 3m/44/ /n, 3n /vn), then generate the remaining entries by drawing uniformly from [+1]"11 and normalizing these to have l norm v1 - a², This way, |u=||a and the coherence is a²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).
M* + W, we estimate using the spectral estimate u, the AMP method and our method as described in Section and measure the estimation error under doc We report the mean 30 independent trials for each combination of conditions (i.e., each combination of problem size n and magnitude a). We vary the matrix size from 3000 to 22000 in increments of 1000.
Having generated
Figure clompares the entrywise estimation error of the AMP method (green), the leading eigenvector of Y (blue) and our Algorithm (orange). Across settings, Algorithm| recovers u" with much smaller errоr under doe compared 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 mean field approximation method and not well-suited for our setting. Adapting AMP- methods to target entrywise recovery rather than & recovery, hopes of rectifying the poor performance exhibited in Figure is promising direction for future work.
47

---

NeurIPS Paper Checklist
1. Claims
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) new method for estimating the eigenvectors in signal-plus-noise matrix models and 2) new lower bound for eigenvector estimation in the small-eigenvalue regime. These results are expanded upon (including thorough discussion of assumptions and limitations) in Sections 2 3 and 6 Our experiments in Section 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 the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
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 through 4 In particular, see Remarks D and Our experiments in
Section explore which of our assumptions might be relaxed or removed. A broad, albeit short, overview of limitations and areas for future work also given in Section 6 titled "Discussion, limitations and conclusion". Computational costs and efficiency are addressed just before Algorithm
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 any strong assumptions and how robust the results 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 few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or 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 seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess..
48

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
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 I and are prominently laid out and explained in Sections] [ and 2 The necessity of these assumptions and the potential to relax remove them discussed in those sections, well in Section All theorems and lemmas are stated with their necessary additional assumptions (c.g., growth rates and relations between parameters), and all are numbered, cross-referenced and have working hyperlinks. Full proof' 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 cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide 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 supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Algorithms are described in the text, including details regarding how hyper- parameters were selected and minor changes made to Algorithms and "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 provided or not.
If the contribution is 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 specific model and empirical evaluation, it may be necessary to either make 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 large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
49

---

While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification; in addition the algorithmic descriptions in Sections 2 and and the details in Section 5] we have included code for running all reported experiments in our supplemental materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
ccips.cc/public/gute http://ddissseeeeee http://p......iieeeee////eeaaaaa Sttp://ooooeeSSseeiiiiiiieeea
osoooiiccc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: the main such concern in this paper surrounds the selection the parameters onn and 3 in Algorithm T Selection of these parameters is discussed length in Remark 2 and in our description of the experiments in Section 5 We have also provided code that reflects the discussion in the paper.
Guidelines:
50

---

The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: all experiment plots include error bars denoting 95% bootstrap confidence intervals. This is discussed in Section 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 include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: This is addressed the beginning of Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics Bttnghhhrpps//pprrrrr...o//////p
Answer: [Yes]
51

---

Justification: This paper concerns theoretical question surrounding minimax estimation rates. It involves neither human subjects nor sensitive data. Societal impacts, either positive or negative, are of course possible (e.g., statistical methods and models are frequently abused or used toward malicious ends), but our work creates no risks that warrant mitigation, the best of our knowledge. All experimental code uses only open source software tools.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
This paper concerns theoretica//methoollgiiaa 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 cigenvector estimation methods (c.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 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
Justification:
Guidelines:
The answer NA means that there 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 unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeett 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 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. 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 theoretical question surrounding minimax estimation rates and includes models data with risk of misuse, to the best of our knowledge.
52

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: the experimental code, included in the supplementary materials, uses only open source software tools.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pacerswithcode thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the experimental code, included in the supplementary materials, uses only open source software tools.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
53

---

Answer:
[NA]
Justification:
This paper involves neither crowdsourcing nor human subject research.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper involves neither crowdsourcing nor human subject research.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
54


Reviews:
[{"review_id": "anFbFW0nLm", "reviewer": "Reviewer_dN7g", "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.", "questions": "1. The description of Algorithm 1 is too brief. Could you provide a more in-depth discussion?\n2. 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": "See points 1 and 4 in the weaknesses part above.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The classical spectral estimator has an intrinsic dependence on the coherence $\\mu$. That is, when $\\mu$ is large, the low-rank signal exhibits additional structures (e.g., sparsity) beyond low-rankness, and the spectral estimator performs particularly poorly due to its failure to fully utilize these additional structures. This paper proposes a new estimator designed to eliminate this dependence on $\\mu$.\n2. This paper carefully designs a series of simulations to further validate its theoretical findings (as shown in Figure 1), demonstrating that the proposed estimation procedure has little dependence on the coherence $\\mu$.", "weaknesses": "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. \n2. Assumption 2 seems to be confusing, according to the following comments. \n\na)  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). \n\nb) 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.\n\n3. 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.\n\n4. The work lacks experimental validation on real-world datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1) The theoretical results [...] only fit for the scenarios where the low-rank signal matrix is symmetric, thereby limiting its practical use.\n\nWe note that there are many applications (see, e.g., network analysis, neuroimaging, covariance estimation) where the target low-rank matrix to be estimated is symmetric.\nWe believe the result can be extended to the asymmetric case (i.e., the signal matrix is now $\\lambda^* u^* v^{* T}$) via standard matrix dilation arguments.\nWe will add a brief discussion of this point to the paper.\n\n2) a) [...] in the first example given by the authors, $c_1$ and $c_1$ that satisfy condition $\\|u^*\\|_2=1$ are related to  $n$, while the authors state that they are constants (line 125).\n\nWe apologize for the miscommunication.\nIn this example, in which $c_1$ and $c_2$ are chosen to ensure that $u^*$ has norm $1$, both are asymptotically constant with respect to $n$.\nThat is, they are both $\\Theta( 1 )$.\nWe will clarify the example in the manuscript to avoid this misunderstanding.\n\n2) b) [...] $\\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? [...] 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.\n\n$u^*$ is related to $n$, but not necessarily via $\\alpha_0$.\nInherently, $u^*$ is of dimension $n$, so given a fixed coherence, $n$ partially informs the behavior of $u^*$.\nFor a particular choice of coherence, certain values of $\\alpha_0$ are compatible with this coherence and others are not.\nFor example, if $\\alpha_0$ is large, $u^*$ must be coherent.\n\nThe coupling of coherence and Assumption 2 is perhaps a red herring: the important aspect of our result is that spectral methods will depend inherently on the coherence whether Assumption 2 holds or not.\nOur method does not depend on the coherence, provided that Assumption 2 holds.\n\nAs discussed in the paper, it seems likely that Assumption 2 can be removed, suggesting that the answer to the referee's question \"whether the disappearance of coherence in the proposed method is due to the careful design of the algorithm or the existence of Assumption 2.\" is that the algorithm is the reason for the disappearance of the coherence.\n\nPlease see the global rebuttal for further discussion of Assumption 2.\n\n3) 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.\n\nTo clarify, the upper bound in Theorem 1 is under Assumptions 1 through 4 and should be compared to the lower bound in Equation (9).\nThe lower-bound in Section 4 concerns a different regime, and establishes an impossibility result.\nIn the beginning of Section 4, we explain that the lower bound in Equation (9) may be suboptimal in certain regimes (i.e., when $\\lambda^*$ is small).\nTheorem 2 in Section 4 improves the lower bound in Equation (9) in this small-$\\lambda^*$ regime.\n\nWe will edit the introduction and Section 4 to clarify this point.\n\n4) The work lacks experimental validation on real-world datasets.\n\nWe agree that validation on real world data sets is always nice to have.\nThis is a theoretical paper, concerned with understanding the fundamental limits of estimation in a particular problem.\nWe would suggest that experiments on real data are best left for follow-up work dedicated to the engineering problems subsequent to this theoretical work.\n\nQuestions:\n\nQ1) [...] Could you provide a more in-depth discussion [of Alg. 1]?\n\nConsider an entry of $Y$ given by\n$ \\lambda^* u_i^* u_j^* + W_{ij} $.\nIf $i,j \\in [n]$ correspond to large entries of $u^*$, then $u_i^* u_j^*$ is large, and $Y_{ij}$ has a large SNR.\nIf we knew the locations of these large entries, we could obtain a more accurate estimate of $u^*$ by concentrating on these locations.\nEssentially, Alg. 1 and Alg. 2 have two steps: finding large locations, then using them to improve the spectral estimate of $u^*$.\nWe will expand the discussion of Alg. 1 accordingly.\n\nQ2) 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?\n\nThe 3425 number is the total computation time expended on all experiments reported in the paper.\nThat is, this is the total number of compute hours  to produce the experimental results (both spectral and our method).\nThis was included in accordance with the NeurIPS \"Experiments Compute Resources\" checklist requirement, which reads \"For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?\"\nNote that this figure comprised some 6000 or so experimental runs (i.e., individual problem instances) in total, including a few very large-scale problem instances, which account for the vast majority of the total compute time.\n\nThe runtimes of our method and spectral methods are quite close, as discussed at the bottom of page 4: our method is a refinement of the spectral estimate, and this refinement can be done quickly.\nWe will add more detailed discussion of this point and an explicit timing comparison.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tcMMGq0DqT", "reviewer": "Reviewer_qfDx", "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.", "questions": "I have no particular questions that may change my evaluation.", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The result is a welcomed addition to the literature of low-rank estimation. Coherence-free estimation is an important step to get closer to minimax optimal estimation. Due to time constraints, I cannot check all the details of the proof, but the overall approach appears reasonable.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their kind words.\nA brief response to their concerns is below.\n\n1) The main weakness is Assumption 2 and Assumption 3, which are a bit weird and could significantly worsen the bound in some cases. \n\nWe agree that Assumption 2 is ungainly. Please see our discussion of this point in the global rebuttal.\n\nAs for Assumption 3, we assume that the reviewer is referencing the $\\epsilon_0$-dependence.\nAs mentioned above, our experiments in Section 5 strongly suggest that this technical condition is not necessary for our results to hold.\nAs discussed in Remarks 1 and 2 and sporadically throughout Sections 2 and 6, we believe this should be removable, but a formal proof is difficult and is a current focus of our ongoing research.\nShould a breakthrough be achieved before relevant deadlines, we will update the paper accordingly.\n\nIn the event that the referee's concern is with the growth assumption in Assumption 3, we note that this assumption is related to our discussion elsewhere in the paper about the two different growth regimes.\nIn short, Sections 2 and 3 concern the setting where $|\\lambda^*| = \\Omega( \\sqrt{n} )$, up to logarithmic factors, hence the growth rate in Assumption 3.\nSection 4 concerns the ``small signal'' setting, where $|\\lambda^*| = O( \\sqrt{n} )$.\nThere, our Theorem 2 provides a lower bound on the estimation rate, which improves previous known lower bounds.\nWe perhaps did not adequately highlight the fact that the two main theorems of the paper concern different growth regimes for $|\\lambda^*|$.\nWe will update the manuscript to make this distinction more clear.\n\n2) Also, the upper bound is only proved for rank-one matrices.\n\nPlease see our discussion of this point in the global rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rUxYs8uuWc", "reviewer": "Reviewer_85jE", "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.", "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?  \n2) 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?\n3) Is it possible to extend Theorem 2 to general $\\Lambda$ which are not necessarily constant multiples of the identity? \n4) 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.\n\nTypos:\n1) Line 449: A $\\sum_{i}$ is missing \n2) Line 673: It should be $\\mathcal{E}_{5,\\alpha}^c$ and the complement outside of the bracket should not be there.\n3) Line 954: an extra $\\leq$ appears\n4) Line: 1046: it should be $\\mathbb{K}_{r,\\mu}$", "limitations": "The limitations of the assumptions are clearly stated in remarks.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1) The authors introduce an efficient spectral algorithm to compute an estimator that out performs the spectral estimator (in terms of the $\\ell_{2,\\infty}$ distance) and tackles the case when the incoherence parameter $\\mu$ is large with respect to $n$. The rates of convergence of the estimator do not depend on $\\mu$. The algorithm is new and it appears to be a strict improvement over the naive estimator. \n2) The main theorems in the paper are supported by detailed proofs of all results. The proofs are nicely written and the presentation of the results are clear and easy to follow. Furthermore, numerical experiments further support the claims and possible generalizations and weakening of the assumptions of the main results.\n3) Although the Gaussian noise is required in Assumption 1, it appears that it can be removed quite easily. For instance, it appears that Lemma 1 does not use the Gaussian nature of $W$ at all.", "weaknesses": "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.\n2) An algorithm for finite rank spikes are proposed, but the generalization of Theorem 1 to the finite rank case has not been proven. \n3) Theorem 2 is stated when $\\lambda$ is a constant multiple of the identity, so it is slightly more restrictive than in equation 9.\n4) Assumption 2 seems slightly limiting. It appears like a difficult condition to verify in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive assessment and thoughtful suggestions. We address their concerns and questions below.\n\n1) [The authors] prove a nice rate of convergence for [Alg. 1]. Unfortunately, the proof relies on some technical assumptions to simplify the proof. [remainder elided for space]\n\nPlease see our discussion of Assumption 2 in the global rebuttal.\n\n2) [...] the generalization of Theorem 1 to [$r > 1$] has not been proven.\n\nWe agree that a proof for general $r \\ge 1$ would be ideal. Please see our discussion of this in the global rebuttal.\n\n3) Theorem 2 is stated when $\\Lambda$ is a constant multiple of the identity, so it is slightly more restrictive than in equation 9.\n\nThe referee is correct that Theorem 2 takes $\\Lambda^*=\\lambda^* I$, which is more restrictive than Eq. (9).\nTo clarify, $\\Lambda^*$ is a scalar multiple of $I$, but that scalar need not be constant: we require only $ 0<\\lambda^*\\le C\\sigma\\sqrt{n}.$\nIf $\\lambda^*$ grows faster than this, we are in the regime from Section 2.\n\nMore importantly, Theorem 2 establishes a limit to estimation.\nThe result implies eigenvector recovery is hard when $\\Lambda^*$ is a scalar multiple of the identity, so the problem is no easier for a larger class of matrices.\n\nWe believe Theorem 2 can be adapted to allow structure in $\\Lambda^*$.\nIn particular, we believe that the problem is hardest when the smallest eigengap in $\\Lambda^*$ is small.\nThis would suggest that $\\Lambda^* = \\lambda^* I$ is the hardest setting.\nWe will add a brief discussion of this after Theorem 2, leaving a precise treatment to future work.\n\n4) Assumption 2 [appears difficult to check in practice].\n\nPlease see our discussion of Assumption 2 in the global rebuttal.\n\nAs for verifying Assumption 2 in practice, this is perhaps a case where assumptions are part and parcel of the method (e.g., $t$-tests require independence which is usually hard or impossible to verify).\nThat said, as mentioned around line 253, a fundamental step in our implementation of Alg. 1 (and in our stated Alg. 2) is to conjugate $Y$ by a Haar-distributed orthogonal matrix.\nThis essentially obliterates any structure in $u^*$: $H u^*$ is Haar-distributed.\nThe success of Alg. 1 despite this suggests practitioners should not be too concerned about Assumption 2 when applying this method.\n\nQuestions\n\nQ1) [it seems easy to violate Assumption 2.] Is it true that if $u^*$ was generated by normalizing a vector with i.i.d entries that assumption 2 will be violated?\n\nWhether or not $u^*$ obeys Assumption 2 is somewhat technical.\nIf $u^*$ is generated by renormalizing iid Gaussians, then Assumption 2 fails: the resulting vector is Haar-distributed.\nThis is the focus of Fig. 1, where we explore two settings that violate Assumption 2: $u^*$ (before normalization) has iid Gaussian (top row) and iid Bernoulli (bottom row) entries.\nPer Fig. 1, our method outperforms \"pure\" spectral methods even in this \"bad\" setting.\n\nThe referee is incorrect that renormalizing a vector of iid entries must violate Assumption 2.\nIf the distribution has suitable structure, $u^*$ may still obey Assumption 2.\nSuppose $u^*$ is obtained by renormalizing a vector $g=(g_1,g_2,\\dots,g_n)$ with iid entries from a distribution with variance $1$, so $u^*\\approx g/\\sqrt{n}$.\nIf 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 $\\approx ap/\\sqrt{n}$ or $\\approx b(1-p)/\\sqrt{n}$.\nThe result is a $O(n^{-1/2})$ gap between the entries of $u^*$, and we can take $\\alpha_0=(\\log n)^{-L}\\approx n^{-1/2}$.\nThis is a \"random\" analogue of our example after Assumption 2, where we take $u^*=1_n/\\sqrt{n}$.\n\nA complete account of which distributions do and do not violate Assumption 2 is interesting, but perhaps beside the point, since Assumption 2 seems removable.\nWe will add examples after Assumption 2 to further elucidate this point.\n\nQ2) [... it appears that] $\\Lambda^*$ and $U^*$ are non random, and the only randomness is in $W$. [...]\n\nAs mentioned above, Theorem 2 establishes a fundamental limit to how well we can estimate $U^*$.\nThe standard tool for these bounds, which we use here, requires finding a collection of parameters (in our case, choices of $U^*$ and $\\Lambda^*$) that are hard to distinguish based on observed data (i.e., $Y$).\nThis should clarify why $U^*$ and $\\Lambda^*$ are not random: they are model parameters, not random variables.\n\nPerhaps the referee has in mind a Bayesian paradigm, where $U^*$ and $\\Lambda^*$ have priors.\nThis can be done, but the lower bound in Theorem 2 holds as a statement about estimation in general.\n\nQ3) Is it possible to extend Theorem 2 to general $\\Lambda^*$ [that are not constant multiples of the identity]?\n\nSee our response to Concern 3 above.\n\nQ4) [perhaps Assumption 2 can be removed via a union bound]\n\nWe considered this when working on our proofs.\nIndeed, we apply Lemma 9 in a union bound over $\\mathcal{A}$.\nUnfortunately, the \"bigger\" union bound the referee seems to be suggesting (i.e., over all $n$-dimensional binary vectors) incurs a factor of $2^n$ in the probability bound, which incurs an extra $\\sqrt{n}$ in the error bound, which is too loose for our purposes.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LNDvkCUFB3", "reviewer": "Reviewer_nQFd", "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.", "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.\n- In line 44, the results in [6] assume that all entries of the spike $u^*$ are $O(1/\\sqrt{N})$.\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.)\n- 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^*)$.\n- 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.)\n- 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": "The work does not seem to have potential negative societal impact.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The proposed algorithm is new, and the error bound indeed does not depend on the incoherence parameter.\n- The error bound of the algorithm is mathematically analyzed and also tested by numerical experiments.", "weaknesses": "- 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.\n- 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}$.\n- 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.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the referee for their careful reading.\nWe must politely disagree with their correctness concerns, which mostly relate to citations in the literature review.\nThese provide context and background to our paper and are unrelated to our proofs.\nWe have clarified these points below and will edit the manuscript accordingly.\nWe trust this will assuage the referee's concerns.\n\n1) [...] performance should be compared with other non-spectral methods [...].\n\nThe most obvious competing method is approximate message passing (AMP; see the global rebuttal).\nAMP methods typically require a limiting prior distribution $\\pi$ for the entries of $\\sqrt{n} u^*$, which limits performance when $u^*$ is coherent.\nTo see this, let $\\nu_n$ be the empirical distribution of the entries of $\\sqrt{n} u^*$.\n$\\pi$ must be the limit of $\\nu_n$ and obey the conditions of Prop. 3.4 in Feng, et al (see also \"Information-theoretically optimal sparse PCA\" by Deshpande and Montanari, Section 2.1).\nIf one \"hides\" a few moderate entries in $u^*$, increasing coherence without changing the limiting distribution, entrywise estimation fails.\nOn the other hand, one can show that a highly coherent $u^*$ violates the conditions needed by AMP.\n\nSetting this aside, the global rebuttal PDF shows an experiment comparing AMP against our Alg. 1, where our method consistently outperforms AMP.\nWe will add a detailed description of this experiment and why $\\ell_2$ methods are unsuitable for entrywise estimation.\n\n2) Assumption 2 is strange and cannot hold in many important cases. [...] if [$u^*$] contains many entries of the size $n^{-\\alpha}$, then Assumption 2 may not hold [...].\n\nWe agree Assumption 2 is strange. See our discussion in the global rebuttal.\n\nThe referee is incorrect in their counter-example.\nIf their $\\alpha$ is not $1/2$, then absent a very careful choice of spacing, there will be a gap between the larger and smaller entries of $u^*$ and Assumption 2 will hold.\nThe important condition is the existence of *some* $\\alpha \\in \\mathcal{A}$.\nChoosing one \"bad\" $\\alpha$ as the referee seems to suggest need not violate Assumption 2.\n\n3) [...] [6] assumes all entries of the spike are $O(1/\\sqrt{n})$.\n\nWe cite [6] illustrate a widespread belief that when $\\lambda^*$ is too small, estimation is difficult or impossible (see, e.g., the discussion after Lemma 1 in [6]).\nThe citation is not toward a proof.\n\n4) [...] the original BBP transition in [8] is not [in this paper's setting]\n\nYes, [8] is for Gaussian covariance.\nSimilar results for many other models are well known to researchers in this community.\nFor the model in our paper, see \"The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices\" by Benaych-Georges and Nadakuditi, or Section 3 of the AMP survey above.\nWe will add these to the manuscript.\n\n5) [...] the case $\\lambda^* \\gg\\sqrt{n}$ is not considered in [8] and thus it is unclear whether [...] Lemma 1 [applies]. When $|\\lambda^*| = \\Theta( \\sqrt{n \\log n} )$, Lemma 1 only says that $\\lim\\inf_n d_\\infty(u,u^* )\\ge 0$, not about the asymptotic bound for $d_\\infty(u,u^* )$.\n\nThe setting $\\lambda^* \\gg \\sqrt{n}$ is indeed not in [8], but our aim is not to apply [8] in relation to Lemma 1 (or vice versa).\nLemma 1 suggests that the upper bound in Eq. (4) is not generally improvable, so the error in the leading sample eigenvector must depend on coherence.\nOur paper removes this dependence by considering methods that are not based on the leading eigenstructure alone.\nIn other words, Lemma 1 supports the idea that to remove dependence on coherence, we need a method that is not purely spectral.\nLemma 1 indeed does not directly apply to $|\\lambda^*| = \\Theta( \\sqrt{n \\log n} )$, but it suggests a similar lower bound on the entrywise error of the spectral estimator, since there is no phase transition in this regime.\nA finite-sample version of Lemma 1 in this regime is also possible.\n\n6) [...] [22] is under the assumption that $|\\lambda^*| = \\Theta( \\sqrt{n} )$ and [...] [45] is under the assumption that [$W$] is GOE. [$W$ is not GOE due to the diagonal.]\n\nAs stated at the bottom of page 4, Alg. 1 yields a new estimator for $\\lambda^*$, investigated in Appendix E.\nThe Equation (14) estimator is a known quantity to most researchers in this subfield.\nWe use it in our experiments instead of our new estimator so we can investigate Alg. 1 and 2 without accounting for using a new eigenvalue estimator at the same time.\nWe omit lengthy discussion of the estimator in Equation (14), as these details have been established elsewhere.\n\nThe citations disputed by the referee point out other works that have studied this estimator, providing context to our use of it.\nCitations [22,25,49,16] all show versions of the decomposition $\\lambda=\\lambda^* +n\\sigma^2 /\\lambda^* +O(\\sigma\\sqrt{\\log n})$.\nThese are to highlight papers where similar ideas have been used, not because they all hold in our setting.\nThe necessary proof ideas for our paper are found in [25].\nWe will edit the text to make this more clear.\n\nThe referee is correct that $W$ is not precisely GOE.\nThe diagonal entries influence important quantities in random matrix theory (e.g., the leading eigenvalue).\nIn our problem, though the $n$ on-diagonal entries are swamped by the $O(n^2)$ off-diagonal entries.\nOur proofs account for this.\nOne could also use Weyl's inequality after uniformly bounding the diagonal entries as $O(\\sqrt{\\log n})$.\nThis factor is swamped by the $\\sqrt{n}$ factors elsewhere in the relevant bounds.\nSee also Theorem 1.3 in \"The largest eigenvalue of rank one deformation of large Wigner matrices\" by Feral and Peche.\nWe cite [45] to show where this estimator has been studied before, not necessarily under the exact same setting as us.\nWe will clarify this in the text.\n\n7) [The probability $n^{-7}$ bound below line 491 has the wrong exponent] \n\nWe have increased the constant on the union bound and corrected Lemma 3 accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FyO0uJ6CLm", "reviewer": "Reviewer_pryd", "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}$.", "questions": "1) You consider only symmetric matrices in the paper. Are all results easily transferable to asymmetric case (for example, by symmetrization trick)?\n\n2) 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?\n\n3) Could you please give some more precise hints why is rank-$r$ case more difficult than rank-$1$ case?\n\n4) Are there any other entrywise lower bounds in the literature that are not simple corollaries of Frobenius lower bounds? \n\n5) 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": "The authors have addressed limitations adequately.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1) Theorem 1 showing coherence free entrywise estimation of eigenvectors is very interesting. It is a very practical result that can improve any experiments requiring good entrywise estimates. Also, the algorithm itself and its guarantee are interesting for their own sake.\n\n2) Even though authors do not prove guarantee in general rank-$r$ setting, it is praiseworthy that they propose and empirically evaluate a generalization of rank-$1$ algorithm. \n\n3) As authors nicely describe in Section 1.2, lower bounds for matrix (or eigenvector) estimation in $\\\\Vert \\cdot \\\\Vert_{2\\to\\\\infty}$ are usually derived based on lower bounds for Frobenius norm estimation, and are generally not tight. I am not aware of any previous results that are as tight as the one claimed in Theorem 2.\n\n4) Lastly, experimental results complement really well theoretical results, and show that proposed algorithms look very promising even in practice.", "weaknesses": "1) The main theorem is proven only in rank-$1$ setting, and rank-$r$ setting is only empirically tested.\n\n2) 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. \n\n3) Bounds might be improvable in log terms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their praise and for their thoughtful suggestions.\nSpecific responses to their concerns and questions are given below.\n\n1) The main theorem is proven only in rank-$1$ setting, and rank-$r$ setting is only empirically tested.\n\nPlease see our discussion in the global rebuttal.\n\n2) 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.\n\nWe note that in all cases where we invoke Gaussianity, we do so only to ensure an appropriate tail bound (i.e., concentration inequality).\nAs such, our Gaussian assumption can be relaxed to a Gaussian tail decay.\nWe will update the theorem statements and proofs accordingly to encompass this more general case.\n\n3) Bounds might be improvable in log terms.\n\nWe agree with this conjecture.\nAs with many results in the low-rank estimation literature, the logarithmic terms in our bounds are incurred typically due to union bounds and/or the extra factors needed to ensure that bounds hold with probability polynomially small in $n$.\nAs the referee is surely aware, removing these terms typically requires a great deal of highly technical work for a gain that is interesting primarily as a technical challenge.\nAs such, we would suggest leaving this further analysis for future work in a probability or mathematics journal.\n\n===Questions===\n\nQ1) You consider only symmetric matrices in the paper. Are all results easily transferable to asymmetric case (for example, by symmetrization trick)?\n\nIn short, the answer is yes, using standard matrix dilation arguments (i.e., symmetrization).\nWe will add a sketch of this argument to the text.\n\nQ2) In rank-$r$ case when you split matrix $Y$ into $\\lambda^*_k u_k^* u_k^{* T}$ and [noise terms], how would you mitigate the fact that this new noise [...] is dependent on signal i.e. on $k$-th eigenvector? Is this an issue at all?\n\nRecall that we conjugate $Y$ by a Haar matrix $H$.\nLet $v$ be the leading eigenvector of $H Y H^T$ and let $Q$ be diagonal with entries given by the signs of the entries of $v$.\nLet $\\xi$ be the indicator of whether or not the norm of $v$ is at least $|v_{(\\lfloor n/2 \\rfloor)}|$.\nConsider the case where $r = 2$.\nOur estimate is of $u^*_1$ is given by\n\n$\\hat{u}_i = \\frac{\\lambda_1^* u_1^{* \\top} H Q \\xi}{\\hat{S} \\sqrt{\\hat{\\lambda}_1}} u_1^* + \\frac{\\lambda_2^* u_2^{* T} H Q \\xi}{\\hat{S} \\sqrt{\\hat{\\lambda}_1}} u_2^* +\\frac{W H Q \\xi}{\\hat{S} \\sqrt{\\hat{\\lambda}_1}}.$\n\nCompared to the $r=1$ case, the middle term is new.\nLet us sketch why this term does not much matter.\nWith high probability, the diagonal of $Q$ is the sign of some entries of $u_1^{* T} H$, which is almost independent of $u_2^{* T} H$ by properties of random vectors uniformly distributed on $\\mathbb{S}^{n-1}$.\nThus, one expects that $u_2^{* T} H Q \\xi = O(\\sqrt{\\log n})$ with high probability, and the error introduced by $u_2^{* T}$ is at most $O(\\sqrt{n^{-1} \\log n})$ when $|\\lambda_2^*| = \\Theta(\\lambda_1^*)$.\nThis implies that when $|\\lambda_1^*| = \\tilde{\\Theta}(\\sigma \\sqrt{n})$, we would expect an almost coherence free rate.\nWhether we can extend the proof to $|\\lambda_1^*| \\gg \\sigma \\sqrt{n})$ remains uncertain, but at least we would expect our method to work in the most interesting regime $|\\lambda_1^*| = \\tilde{\\Theta}(\\sigma \\sqrt{n})$.\nAlternatively, we can possibly be more careful in selecting $\\xi$, so that $u_1^{* T} H Q \\xi = \\Theta(n)$ while $u_2^{* T} H Q \\xi \\ll O(\\sqrt{\\log n})$ and the coherence-free rate holds in a wider range of $\\lambda_1^*$.\n\nQ3) Could you please give some more precise hints why is rank-$r$ case more difficult than rank-$1$ case?\n\nIn the rank-$r$ case, when we sum over the large entries of one spike, we need to also consider whether the other spikes affects the estimation.\nWe choose to use a random orthogonal transformation to get the spikes into general positions, so that when summing over the large entries of one spike, the effect of other spikes is ignorable.\nAs mentioned in the intuition of Alg. 1, our method basically has two steps: selecting a suitable subset, and fitting on this subset.\nIn the rank-one case, we make Assumption 2 so that we can perform selection and fitting on the same data.\nThe random orthogonal transformation we use for the rank-$r$ case breaks Assumption 2 and introduces some complicated dependence, which we do not yet know how to resolve technically.\n\nQ4) Are there any other entrywise lower bounds in the literature that are not simple corollaries of Frobenius lower bounds?\n\nTo the best of our knowledge, this is the first such entrywise result that does not simply fall back on Frobenius lower bounds.\n\nQ5) 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.\n\nWe are not aware of any other coherence-free methods against which to compare.\nThe referee's suggestion to use leverage scores to identify high-coherence entries is a good one, except that this is not easily done without already having a good estimate of the coherence.\nIndeed, at a high level, the intuition behind our Algorithm 1 is precisely that of the referee: we want to focus our efforts on the high-coherence entries, but we must identify them first.\nWe will update the manuscript to discuss this point in more detail.\n\nIf one must find a method to compare against aside from the ``purely spectral'' method in our experiments, the best we are aware of would be an approximate message passing (AMP) method for eigenvector recovery.\nSee our discussion in the global rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the referees and area chairs for their time, efforts and for their helpful comments, which have greatly improved the paper.

Two common themes among the reviewers' reports were Assumption 2 and the extension of Theorem 1 to the general $r \ge 1$ case.
In addition to these two points, two reviewers asked questions about other non-spectral methods.
We address these three themes below.

**Concerning Assumption 2**

We agree with the opinion expressed by several reviewers that Assumption 2 is not especiall natural.
Per Remarks 1 and 2 in the paper, we believe that Assumption 2 is entirely technical, and can likely be removed.
Our Section 5 experiments support this belief: our methods succeed even when Assumption 2 fails (e.g., Fig. 1).
For example, Alg. 1 outperforms "pure" spectral methods when $u^*$ is Haar-distributed, though this violates Assumption 2.

We note that to the best of our knowledge, this is the first paper to remove dependence on coherence, so there are not yet many tools for this setting.
The main difficulty arises from the fact that without Assumption 2, the selected entries $\hat{I}$ depend on $W$ in a complicated way.
We will add a more detailed discussion of these technical difficulties to the manuscript.
We aim to develop the tools for analyzing this challenging setting, but removing Assumption 2 is fundamentally hard.
Nonetheless, this is the focus of ongoing work, and we will update the manuscript accordingly should a breakthrough be achieved before the deadline.

**Extension of Theorem 1 to $r > 1$**

We agree with the sentiment, expressed by several reviewers, that a proof for the general case of $r \ge 1$ would be ideal.
As discussed in the text, our experiments in Section 5 support our claim that Algorithm 2 succeeds in the general rank-$r$ case, though of course this does not constitute a proof.
A sketch of why the rank-$r$ case should follow similarly to our rank-$1$ case is provided just before Algorithm 2.
We have given a more detailed sketch in our response to reviewer "pryd", and we will incorporate this sketch into the manuscript to provide additional intuition to future readers.
Conditional on acceptance and if time permits, we will add detailed proofs for this general case to the appendix.

**Comparison with other non-spectral methods**

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 for comparison is one based on approximate message passing (AMP; see "A Unifying Tutorial on Approximate Message Passing" by Feng, Venkataramanan, Rush, and Samworth for an overview).
We include in our attached PDF a figure summarizing additional experiments comparing our method to another non-spectral method: one based on approximate message passing (AMP).
These are analogous to our experiments in Figure 1 of the manuscript, now includ
ing an additional method.
These experiments demonstrate that our method in Algorithm 1 outperforms the only other non-spectral eigenvector recovery method of which we are aware, namely one based on AMP.

AMP methods make no explicit coherence assumptions, but the underlying mechanism essentially requires incoherence: inherent to AMP methods for eigenvector recovery is that the eigenvector is modeled as having all its entries drawn i.i.d.~according to a common distribution.
Specifically, AMP methods make a mean field assumption whereby the empirical distribution of $\{ u^*_i : i \in [n] \}$ converges in $\ell_2$ to a distribution $\pi$.
AMP-based methods fail in entrywise recovery problems because they are tailored to $\ell_2$-recovery: small $\ell_2$ error does not necessary imly small entrywise recovery.
Adapting AMP-based methods to target entrywise recovery is an interesting direction for future work, but well beyond the scope of this paper.

Meta-review: 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.
Decision: Accept (poster)