Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank

1 Introduction

• Vanilla spectral recovery in the stochastic block model reaches the information-theoretic limit and coincides with MLE exact recovery whenever MLE succeeds, settling a conjecture in Abbe et al. (2014b, 2016).The paper concludes that MLE and SDP have no exact-recovery advantage over the spectral method when the model is correct, although SDP may offer robustness and certificates.Source: §1 · pp. 2–3

1.1 A sample problem

• In the SBM sample problem, the expectation has rank 2, while simulations show that the second eigenvector’s coordinates form separated communities and its first-order approximation is much more accurate entrywise.Figure 1 uses n = 5000, a = 4.5, and b = 0.25; the approximation error is smaller than the direct eigenvector-to-population error in infinity norm.Source: §1.1 · pp. 3–5, Figure 1 · p. 4

1.2 First-order approximation of eigenvectors

• Under low-rank expectations, spectral-norm and row-wise concentration with suitable eigenvalue gaps yield a sign-adjusted, entrywise approximation of u_k by A u_k^*, enabling linearized eigenvector analysis.The approximation error is small order-wise, and the conditions apply to SBM throughout the log n regime regardless of the relative sizes of a and b.Source: §1.2 · pp. 6–7

1.3 MLE, spectral algorithm, and strong consistency

• The analysis controls the linearized error rather than direct eigenvector distance, because asymmetric coordinate errors can leave signs correct even when infinity-norm distance is large.Consequently, when MLE succeeds away from the phase-transition boundary, the eigenvector estimator sgn(u2) also recovers the true communities with probability 1 −o(1).Source: §1.3 · p. 7

1.4 An iterative perspective: power iterations

• The paper also introduces an iterative perspective centered on the top eigenvector of the centered adjacency matrix as an algorithmic intuition for the perturbation analysis.The supplied introduction begins this perspective but does not provide its subsequent derivation or conclusions.Source: §1.4 · p. 8
• A single power iteration from the population eigenvector yields the first-order approximation, while leave-one-out and Davis–Kahan analysis provide the paper’s proof strategy.The iterative view explains why one carefully designed iterate can achieve the desired precision, although the paper does not prove results through iteration or induction.Source: §1.4 · p. 8

1.5 Related works

• Prior work established perturbation bounds but largely missed basis-dependent ℓ∞ behavior or was suboptimal in difficult stochastic regimes, motivating this paper’s entrywise analysis across synchronization, SBM, and matrix completion.The related literature includes deterministic ℓ∞ and 2 →∞ bounds, randomized singular-vector analyses, and entrywise studies of synchronization and ranking.Source: §1.5 · pp. 9–10

1.6 Notations

• The notation section defines vector ℓ2 and ℓ∞ norms, matrix spectral, max, and 2 →∞ norms, row and column notation, asymptotic comparison symbols, and orthonormal-column matrices.These conventions support the paper’s eigenvector and eigenspace perturbation statements.Source: §1.6 · p. 10

2.1 Random matrix ensembles

• The framework assumes a separating eigen-gap that also accounts for distances to zero, together with row-wise independence, spectral-norm concentration, and row concentration tailored to the matrix distribution.The row-concentration function ϕ yields tighter bounds when entries of W are uneven, a feature identified as crucial for sparse binary stochastic block models.Source: §2.1 · pp. 10–12

2.2 Entrywise perturbation of general eigenspaces

• The eigenspace result handles repeated eigenvalues by comparing U with U* after an explicit orthogonal matrix rotation, rather than assuming uniquely defined eigenvectors.The rotation is constructed from the singular value decomposition of H = U^T U* through the matrix sign function.Source: §2.2 · p. 12
• Under Assumptions A1–A4, Theorem 2.1 states that, with probability at least 1 − δ0 − 2δ1, eigenspace and rotated-error magnitudes satisfy the displayed bounds.Specifically, the bounds control ∥U∥2→∞, ∥U sgn(H) − A U*(Λ*)−1∥2→∞, and ∥U sgn(H) − U*∥2→∞, with dependencies on κ, ϕ(1), γ, ϕ(γ), ∥U*∥2→∞, and γ∥A*∥2→∞/Δ*.Source: §2.2 · pp. 12–13
• The results apply to non-leading eigenvectors and need not assume low-rank A*, while in the rank-one case they recover the linearization Au*/λ* with error smaller than ||u*||∞ when ϕ(1) ≲ 1 and γ = o(1).This makes entrywise analysis of u tractable through its linear approximation Au*/λ*.Source: §2.2 · p. 13
• For low-rank A* = U*Λ*(U*)^T, Corollary 2.1 removes the ||A*||2→∞/Δ* term and controls empirical eigenspaces, their linearization error, and their distance from U*.The same probability guarantee, 1 − δ0 − 2δ1, applies, with bounds proportional to ||U*||2→∞ and the concentration parameters.Source: §2.2 · p. 13

3.1 Z2-synchronization and spiked Wigner model

• For Gaussian Z2-synchronization, taking the sign of the leading eigenvector achieves exact recovery in the regime where the MLE does, and therefore agrees with the MLE with high probability.The method computes the leading eigenvector of Y and returns its coordinatewise signs; the result also extends to the stochastic block model.Source: §3.1 · p. 14

3.2 Stochastic Block Model

• In the two-block stochastic block model, the vanilla second-eigenvector sign method achieves exact recovery whenever information-theoretically possible and the optimal minimax misclassification rate otherwise.This resolves the conjecture of Abbe et al. (2014b) and shows that trimming or refinement is unnecessary for these guarantees.Source: §3.2 · pp. 16–17
• The SBM analysis relies on a tight first-order ℓ∞ approximation, because direct eigenvector perturbation can exceed the signal scale even when all coordinate signs are correct.The approximation reduces the analysis to weighted Bernoulli sums and holds for any constants a and b without depending on the gap √a − √b; extensions to K > 2 blocks face orthogonal-transform ambiguity.Source: §3.2 · pp. 17–18

3.3 Matrix completion from noisy entries

• For noisy matrix completion, a spectral estimator based on the leading singular vectors receives new entrywise bounds for U, V, and UΣV^T − M*.Because the rectangular model is asymmetric, the proof adapts the eigenvector framework through symmetric dilation; the singular-vector bounds are described as the first of their type for this spectral algorithm.Source: §3.3 · pp. 19–20
• When σ ≳∥M ∗∥max, the spectral algorithm is rate-optimal, matching the lower bound established by Cand`es and Plan (2010).The result is stated under the sampling condition p > c log n for sufficiently large c.Source: §3.3 · p. 20
• Theorem 3.4 recovers the matrix-estimation benchmark up to a factor of √log n, using the general relation between Frobenius and max norms.The comparison applies under the incoherence-related setting discussed alongside the lower-bound benchmark.Source: §3.3 · p. 20
• For singular-vector estimation, the entrywise bound likewise recovers the Frobenius-based rate up to √log n and yields max-norm bounds of the correct order.The paper emphasizes that these bounds describe spectral-algorithm behavior more informatively than Frobenius-norm counterparts rather than improving Frobenius rates.Source: §3.3 · pp. 20–21

4.1 Z2-synchronization

• Below the theoretical boundary σ = n/(2 log n), the eigenvector estimator almost always perfectly recovers the Z2-synchronization signal, while above it recovery fails.Figure 5 reports success proportions over 100 independent runs, with lighter pixels indicating higher recovery proportions.Source: §4.1 · p. 21, Figure 5 · p. 21

4.2 Stochastic Block Model

• The stochastic block model’s empirical exact-recovery phase transition matches the theoretical boundary curves.The eigenvector method’s success proportions are measured over 100 independent runs across varying parameters a and b.Source: §4.2 · pp. 21–22
• As n increases, mean SBM misclassification-rate curves approach the theoretical prediction −(√a−b)^2/2 from Theorem 3.2 (ii).Experiments fix b = 2, vary a from 2 to 8, and compare n ∈ {100, 500, 5000}.Source: §4.2 · p. 22

• First-order eigenvector and eigenspace approximations achieve small ℓ∞ errors under random perturbations and yield sharp guarantees for three statistical problems.Source: §5 · p. 23
• The perturbation theorems are currently limited to symmetric matrices, motivating extensions to SVD for rectangular matrices and to graph Laplacian or non-backtracking matrices.Source: §5 · p. 23
• Relaxing row- and column-wise independence to block-wise independence could broaden applicability to cryo-EM and related problems.Source: §5 · p. 24
• In the examples, the spectral algorithm is strongly consistent if and only if the MLE is, despite the MLE being potentially NP-hard to compute.The authors propose studying how general this equivalence is to better understand statistical and computational tradeoffs.Source: §5 · p. 24

A Outline of proofs

• Key observations lead to inequalities (2.6) and (2.7) in the eigenvector case.Source: A Outline of proofs · p. 25
• The eigenvector perturbation analysis provides insights used in the general eigenspace perturbation result.Source: A Outline of proofs · p. 25
• The section then outlines the proof ideas for Theorem 2.1.Source: A Outline of proofs · p. 25

Rank-one perturbation setup

• Weyl’s inequality and spectral-norm concentration ensure the leading eigenvalue remains within γλ* of λ*, with λ at least λ*/2 when γ < 1/2.This lower bound controls the reciprocal-eigenvalue perturbation in the eigenvector analysis.Source: §A.1 · p. 25
• Row concentration bounds the entrywise fluctuation (A−A*)u* with probability 1−δ1/r, reducing the analysis to controlling A(u−u*).The remaining term is difficult because A and u−u* are dependent.Source: §A.1 · p. 25

Leave-one-out decoupling

• Leave-one-out matrices A(m) remove the mth row and column, making A−A(m) independent of A(m) and decoupling the dependence.This construction follows techniques related to Bean et al. (2013), Javanmard and Montanari (2015), and Zhong and Boumal (2018).Source: §A.1 · p. 25
• The leading eigenvectors u(m) of A(m) make the mth row independent of u(m)−u*, allowing row concentration to control the problematic leave-one-out term.The resulting bound is of order λ*(γ+ϕ(γ))(∥u∥∞+∥u*∥∞), with the ∥u∥∞ term later absorbed.Source: §A.1 · pp. 25–26

Closing the perturbation bounds

• Davis–Kahan control of ∥u−u(m)∥2, together with bounds on the sparse perturbation A−A(m), yields sharp control of both leave-one-out terms and establishes inequalities (2.6) and (2.7).After rearrangement, terms involving ∥u∥∞ are absorbed, and the remaining quantities are bounded using ∥u*∥∞ and the earlier bound on ∥Au*∥∞.Source: §A.1 · p. 26

B.1 Deterministic lemmas

• Under ∥A − A∗∥2 ≤ γ∆∗ and small γ, the auxiliary matrices U (m) and H(m) provide independence while preserving deterministic eigenspace and rowwise bounds.The construction yields ∥A(m) − A∗∥2 ≤ 5γ∆∗ and supports the simplified inequalities used in Lemma 3.Source: §A.2 · p. 27, §B.1 · pp. 30–31

A.2 Proof ideas for Theorem 2.1

• Theorem 2.1’s proof controls the aligned eigenspace norm ∥UH∥2→∞ by combining decoupling, Davis–Kahan perturbation bounds, and row concentration for non-uniform weights.The second and third error terms are shown to be vanishing proportions, while the concentration function ϕ(x) is essential for controlling the third term.Source: §A.2 · p. 27
• The resulting bound is roughly O(∥U ∗∥2→∞ + ∥A∗∥2→∞/∆∗), so aligned empirical eigenspaces inflate the population norm by at most a constant factor in many applications.This control is then used to prove the sharp approximation ∥UH − AU ∗(Λ∗)−1∥2→∞.Source: §A.2 · p. 27
• When γ = o(1), the final approximation error is an order smaller than ∥U ∗∥max + ∥A∗∥2→∞/∆∗.The third term is bounded with probability 1−δ1 by O((γ + ϕ(γ))(∥U ∗∥max + ∥A∗∥2→∞/∆∗)).Source: §A.2 · p. 28

B.1 Deterministic lemmas

• The deterministic lemmas align U with U ∗ through H = U^TU ∗ and sgn(H), showing that H is close to the orthonormal matrix sgn(H).These alignment tools are developed while temporarily assuming only A1, using techniques similar to Fan et al. (2017).Source: §B.1 · p. 28
• The proof identifies ∥sgn(H) − H∥2 with 1 − cos θ̄r and bounds it through canonical angles and spectral perturbation control.The singular values of H are cosines of the canonical angles between the column spaces of U and U ∗.Source: §B.1 · pp. 28–29
• For general rank r, noncommutativity between H and Λ creates the main technical difficulty, unlike the scalar r = 1 case where the commutator vanishes.The deterministic bounds address this difficulty through control of ΛH − HΛ and perturbation terms involving decoupled matrices.Source: §B.1 · p. 29

B.2 Proof of Theorem 2.1

• Theorem 2.1 is proved by combining Lemma 4’s bound on ∥AU*∥2→∞ with Lemma 5’s bound on max_m ∥A_m·(U^(m)H^(m) − U*)∥2.Lemma 4 uses row concentration, while Lemma 5 controls the leave-one-out perturbation term.Source: §B.2 · p. 32
• Row concentration and a union bound give ∥(A − A*)U*∥2→∞ ≤ Δ*ϕ(1)∥U*∥2→∞ with probability at least 1 − δ1.The deterministic component is controlled using A*U* = U*Λ* and bounded by ∥Λ*∥2∥U*∥2→∞.Source: §B.2 · pp. 32–33
• Lemma 5 establishes, on an event of probability at least 1 − δ1 and under ∥A − A*∥2 ≤ γΔ*, the stated uniform rowwise perturbation bound.The bound is 6γ∥A*∥2→∞ + Δ*ϕ(γ)(4κ∥UH∥2→∞ + 6∥U*∥2→∞).Source: §B.2 · p. 33
• The leave-one-out construction makes (A − A*)_m· independent of V^(m), enabling Assumption A4 and union bounds to establish the event E1.On the spectral event and E1, (B.12) further gives ∥V^(m)∥F ≤ √r∥V^(m)∥2 ≤ 6γ√r.Source: §B.2 · p. 33
• The proof constructs an event E with probability at least 1 − δ0 − 2δ1 on which Lemmas 1, 3, 4, and 5 jointly control ∥UH∥2→∞.This event also includes ∥A − A*∥2 ≤ γΔ* and the auxiliary inequalities needed for Theorem 2.1.Source: §B.2 · p. 34
• The resulting control eliminates ∥UH∥2→∞ from the right-hand side using 16κϕ(γ) ≤ 1/2 under Assumption A1.The first two theorem inequalities follow from this rearrangement, while the third follows from the second and the auxiliary bounds.Source: §B.2 · pp. 34–35

Proof setup

• The proof models Z2-synchronization with A∗ = xx∗ and A = Y, where the signal has rank one and normalized entries |u∗_i| = 1/√n.It chooses ϕ(x) = x and γ = max{3√(log n), 1/√n}, giving γ = o(1) and ||u∗||∞ ≤ γ.Source: §C.1 · p. 35

Concentration verification

• Standard Gaussian concentration verifies the required spectral-norm and row-concentration assumptions for A − A∗.The spectral bound is ||A − A∗||2 ≤ 3σ√n with probability at least 1 − O(e^-n/2), while each row projection is Gaussian with variance at most σ^2||w||2.Source: §C.1 · p. 35

Entrywise approximation

• Theorem 1.1 yields, with an optimal global sign, ||su − (u∗ + σWu∗/n)||∞ ≲ (1/√n) log n.The bound compares the empirical eigenvector to the signal eigenvector plus its linear Gaussian perturbation.Source: §C.1 · p. 35

High-probability conclusion

• A Gaussian tail bound and union bound establish the required simultaneous entrywise control with probability 1 − o(1).The proof then uses that √n u∗ = x has entries in {±1} to conclude the desired inequality.Source: §C.1 · p. 36

C.2 Proofs for Stochastic Block Model

• The stochastic block model proofs proceed from Corollary 3.1 through concentration lemmas, a linearized-eigenvector tail bound, Theorem 3.2, and Theorem 3.3.The proof sequence explicitly includes Lemma 8 for controlling linearized-eigenvector entries and additional lemmas after the main theorems.Source: §C.2 · p. 36
• For a > b > 0, nI tends to infinity, allowing Zhang and Zhou’s results to yield equation (3.4).The derivation uses K = 2 and a′ = a log n, b′ = b log n.Source: §C.2 · p. 36
• The Corollary 3.1 proof verifies the theorem assumptions for the second eigenvector using concentration inequalities with failure probabilities δ0 = c2n^-3 and δ1 = 2n^-3.Lemma 6 supplies one concentration condition, while Lemma 7 establishes the remaining condition for the stochastic block model.Source: §C.2 · p. 37
• Lemma 8 controls differences of Binomial variables by applying Markov’s inequality to moment-generating functions, extending a similar lemma in Abbe et al. (2016).The proof chooses λ = −log(a/b)/2 and derives the desired inequality from logarithmic bounds.Source: §C.2 · p. 38
• Theorem 3.2’s auxiliary argument handles dependence caused by matrix symmetry by restricting attention to a subset of independent variables and applying large-deviation bounds.The proof uses the function h(t) = t log t − t + 1 and a change-of-measure argument for Bernoulli sums.Source: §C.2 · pp. 40–42

C.3 Proofs for matrix completion from noisy entries

• The noisy matrix-completion proofs introduce SNMC(A∗, p, σ), apply Theorem 2.1 to it, and derive preliminary results before treating NMC(M∗, p, σ).The proof plan then bounds reconstruction errors in subsection C.3.3.Source: §C.3 · p. 43
• SNMC(A∗, p, σ) is a symmetric random-matrix ensemble with independently sampled observations and Gaussian noise, where observed entries are scaled by 1/p.The model has observation probability p and noise variance σ^2.Source: §C.3 · p. 43

C.3.1 Analysis of SNMC(A∗, p, σ)

• The perturbation control satisfies ϕ(γ) ≤ 4γ√log n(1 + γ√log n), linking the error term to γ and the logarithmic sampling dimension.Here γ combines sampling and noise effects through γ = c1κ̄√(np)(1 + σ∥A^*∥max).Source: §C.3.1 · p. 43
• For A ∼ SNMC(A^*, p, σ) with np ≤ 1, Lemma 12 shows that Assumptions A1–A4 hold and that a constant C > 0 exists with probability at least 1 − 14/n.The proof checks Assumptions A1, A3, and A4, then applies Theorem 2.1.Source: §C.3.1 · pp. 43–44
• When p ≥ 6log n/n, Chernoff concentration ensures no row has more than 2np sampled entries with probability at least 1 − n^-1, so trimming is unnecessary.This makes the untrimmed symmetric model compatible with the cited matrix-completion results.Source: §C.3.1 · p. 44
• Bernstein and Gaussian concentration bounds establish the rowwise controls in Lemma 15 needed for Assumption A4.The argument separately controls sampling fluctuations in (Ā − A^*)m·W and Gaussian noise over the sampled index set.Source: §C.3.1 · pp. 44–46
• With probability at least 1 − 14/n, the SNMC model satisfies the required assumptions and yields entrywise bounds for U and Usgn(H) − U^*.The bounds depend on κ, γ, ϕ(γ), and γ∥A^*∥2→∞/∆^*; under np ≲ 1 they simplify as in (C.13).Source: §C.3.1 · p. 46

C.3.2 From SNMC(A∗, p, σ) to NMC(M ∗, p, σ)

• Symmetric dilation reduces NMC(M^*, p, σ) to SNMC(A^*, p, σ), with the r largest eigenvalues of A^* equal to the r singular values of M^*.The corresponding eigenvectors and singular-vector blocks allow Lemma 12 to be rephrased for rectangular noisy matrix completion.Source: §C.3.2 · pp. 46–47

C.3.3 Reconstruction errors

• Under the stated matrix-completion conditions, Lemma 18 verifies Assumptions A1–A4 with probability at least 1 − 14/n.The condition is np(∥M*∥max + σ) ≤ 1.Source: §C.3.3 · p. 47
• The proof controls the estimated singular-vector norms and their sign-aligned entrywise deviations from the population factors through κ and η.Specifically, the singular-vector norms scale as ∥U∥2→∞ ∨ ∥V∥2→∞ ≲ κη, while the aligned deviations are bounded via the corresponding barred factors.Source: §C.3.3 · pp. 47–48
• The reconstruction analysis aligns the estimated factors with sgn(H), preserving UΣV^T while enabling Hölder-based control of ∥UΣV^T − M*∥max.It defines ˜Σ = sgn(H)^TΣsgn(H), ˜U = Usgn(H), and ˜V = Vsgn(H).Source: §C.3.3 · p. 48
• The alignment perturbation satisfies ∥sgn(H) − H∥2 ≲ γ^2, and the resulting singular-value discrepancy obeys ∥˜Σ − Σ∥2 ≲ γσ*.Assumption A1 also forces κγ ≲ 1.Source: §C.3.3 · p. 48

C.4 Further results of SBM: more than 2 blocks

• The three-block population embedding has only three distinct rows, corresponding to the true memberships, and empirical embeddings are compared up to an orthonormal transformation.The repeated non-leading eigenvalue permits any orthonormal basis of its eigenspace, motivating alignment by a 2 × 2 orthonormal matrix before clustering.Source: §C.4 · p. 49
• Lemma 19 shows that each node’s empirical embedding is closest to the center associated with its true block, with high probability.The result establishes separation among the three block-specific centers in the two-dimensional spectral embedding.Source: §C.4 · p. 50
• If three estimated centers satisfy max1≤j≤3 ||v̂_j − v_jQ||_2 < δ/√n for sufficiently small δ, assigning nodes to their nearest center exactly recovers z.Thus, sufficiently precise center estimates convert the embedding separation into exact block-membership recovery.Source: §C.4 · p. 50
• The authors do not identify a simple estimator for the centers; multi-stage k-means on a carefully selected subset is suggested, but would add complexity without improving on trimmed or cleaned spectral methods.They leave development of such an estimator as an open question, noting that existing trimmed or cleaned algorithms already attain the information threshold for exact recovery.Source: §C.4 · p. 50