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

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}$.

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. 2) 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. 3) 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. 4) 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. 2) Gaussianity assumption is restricting. If your results hold under less restrictive assumptions (you mention Assumption 1 in Chen et al. 2021), I would prefer having at least a statement of an analogue of Theorem 1 in the most general setting you can have. 3) Bounds might be improvable in log terms.

Questions

1) You consider only symmetric matrices in the paper. Are all results easily transferable to asymmetric case (for example, by symmetrization trick)? 2) In rank-$r$ case when you split matrix $Y$ into $\\lambda_k^{\\star} u_k^{\\star} {u_k^\\star}^\\top$ and the remaining terms that you consider as noise, how would you mitigate the fact that this new noise containing all non-$k$ eigenvectors is dependent on signal i.e. on $k$-th eigenvector? Is this an issue at all? 3) Could you please give some more precise hints why is rank-$r$ case more difficult than rank-$1$ case? 4) Are there any other entrywise lower bounds in the literature that are not simple corollaries of Frobenius lower bounds? 5) How does your method compare with other coherence free methods? For example, using leverage scores for sampling more the entries with high coherence (effectively reducing noise on those entries)? I agree that your model is not the same, but if you could comment on high level differences between the two methods.

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

The authors have addressed limitations adequately.

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.

Strengths

- The proposed algorithm is new, and the error bound indeed does not depend on the incoherence parameter. - 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. - Assumption 2 is strange and cannot hold in many important cases. For example, if the spike $u^*$ contains many entries of the size $n^{-\alpha}$, then Assumption 2 may not hold due to a similar reason as it does not hold when $u^*$ is drawn uniformly from $S^{n-1}$. - Several claims are not rigorous in the sense that they are cited from references in which assumptions are different from those in the current manuscript. (See Questions.)

Questions

Below, I collected several previous results used in the current paper that are not directly applicable since the assumptions in the original papers are different from those in the current paper. - In line 44, the results in [6] assume that all entries of the spike $u^*$ are $O(1/\sqrt{N})$. - In line 46, the original BBP transition in [8] is not for the signal-plus-noise matrix models. (It was for a Gaussian matrix where the spike is contained in the covariance matrix.) - In line 52, the case $|\lambda^*| \gg \sqrt{n}$ is not considered in [8] and thus it is unclear whether the results in Lemma 1 can be applied to this case. Moreover, strictly speaking, when $|\lambda^*| = \Theta(\sqrt{n \log n})$, Lemma 1 only says that $\liminf_{n \to \infty} d_{\infty} (u, u^*) \geq 0$, not about the asymptotic bound for $d_{\infty} (u, u^*)$. - In line 144, the result in [22] is under the assumption that $|\lambda^*| = \Theta(\sqrt{n})$ and the result in [45] is under the assumption that the noise matrix is GOE. (The noise matrix $W$ in the current paper is not a GOE matrix since the variance of the diagonal entries is the same as that of the off-diagonal entries.) - In the inequality below line 491, since the probability estimate on $\max |W_{ii}|$ is basically a union bound, with the coefficient $4$, it seems to hold only with probability $1-O(n^{-7})$.

Rating

4

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

The work does not seem to have potential negative societal impact.

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.

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. 2) 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. 3) 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. 2) An algorithm for finite rank spikes are proposed, but the generalization of Theorem 1 to the finite rank case has not been proven. 3) Theorem 2 is stated when $\lambda$ is a constant multiple of the identity, so it is slightly more restrictive than in equation 9. 4) Assumption 2 seems slightly limiting. It appears like a difficult condition to verify in practice.

Questions

1) Assumption 2 is slightly hard to parse. It seems like it is quite easy to violate Assumption 2 by introducing some randomness in the generation of $u^\star$. Is it true that if $u^\star$ was generated by normalizing a vector with i.i.d entries that assumption 2 will be violated? 2) The subscripts of the expected value in Theorem 2 is mysterious. It appears that the $\Lambda_\star$ and $U_\star$ are non random, and the only randomness is in $W$. Perhaps some notational clarification is needed here? 3) Is it possible to extend Theorem 2 to general $\Lambda$ which are not necessarily constant multiples of the identity? 4) Perhaps proving an uniform bound in Lemma 9, will allow us to do a proof without assumption 2, since we can handle cases when $\hat I$ and $W$ are dependent. However, we will likely lose the $\sqrt{\log n}$ bound if we wanted something uniform. Typos: 1) Line 449: A $\sum_{i}$ is missing 2) Line 673: It should be $\mathcal{E}_{5,\alpha}^c$ and the complement outside of the bracket should not be there. 3) Line 954: an extra $\leq$ appears 4) Line: 1046: it should be $\mathbb{K}_{r,\mu}$

Rating

7

Confidence

2

Soundness

3

Presentation

4

Contribution

3

Limitations

The limitations of the assumptions are clearly stated in remarks.

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.

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.

Questions

I have no particular questions that may change my evaluation.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

4

Limitations

n/a

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.

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$. 2. 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. 2. Assumption 2 seems to be confusing, according to the following comments. a) Firstly, in the first example given by the authors, and $c_1$ and $c_2$ that satisfy condition $\|u^*\|_2=1$ are related to $n$, while the authors state that they are constants (line 125). b) Secondly, $\alpha_0$ is related to $n$, meaning $u^*$ is related to $n$. Therefore, under Assumption 2, considering the influence of $\alpha_0$, what will happen to the coherence? For example, will it no longer be related to $n$? In other words, Assumption 2 and the coherence condition are coupled together, making it difficult to determine whether the disappearance of coherence in the proposed method is due to the careful design of the algorithm or the existence of Assumption 2. 3. The lower bound derived in this paper does not seem to align with the environmental conditions. In other words, the upper bound is given under the assumption that Assumptions 1 through 4 are satisfied. When constructing a bad instance to prove the lower bound, this bad instance should also satisfy such assumptions. Additionally, the selection of $\lambda^*$ does not conform to Assumption 3. 4. The work lacks experimental validation on real-world datasets.

Questions

1. The description of Algorithm 1 is too brief. Could you provide a more in-depth discussion? 2. The paper mentions that the computation of the simulation requires 3425 hours, which seems to be very very time-consuming. Do the classical spectral algorithms or other related algorithms also need this high kind of computational cost?

Rating

6

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

See points 1 and 4 in the weaknesses part above.