PaperlayerView exact revision on arXiv

Source-linked AI summary

Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials

Yihan Zhang

arXiv:2609.28781v3math.PRcs.DScs.NAmath.NAmath.STstat.TH

TL;DR

The paper asks how well the top eigenvalue and eigenvector of a random matrix can be approximated by applying a low-degree polynomial to the matrix and a random Gaussian vector. It analyzes this approach with Chebyshev polynomials and identifies degree thresholds and a critical-regime accuracy limit for spiked GOE and GOE.

  • Problem

    The paper studies how well the top eigenvalue and eigenvector of a random symmetric matrix can be approximated using q(A)b, with q a degree-d polynomial and b an independent standard Gaussian vector.

    Source: §1 · p. 2

  • Method

    The proofs use Chebyshev polynomials, which act component-wise on the eigenvalue spectrum while retaining eigenvectors and are orthonormal with respect to the semicircle law.

    Source: §3.1 · p. 9

  • Results

    For GOE, constant degree suffices for top-eigenvalue approximation, degree n^1/3+o(1) is necessary and sufficient for top-eigenvector approximation, and critical-regime accuracy has an Airy-point-process scaling limit.

    Source: §1 · pp. 2, 4

  • Takeaways & Limitations

    The paper determines fundamental limits for low-degree polynomial approximation in spiked GOE and GOE and develops quantitative linear-spectral-statistic estimates that may be independently useful.

    Source: §5 · p. 19

    The theoretical results mainly concern expected squared overlap or Rayleigh quotient in the large-n, large-d limit; understanding their finite-dimensional variance remains open.

    Source: §5 · p. 21

Abstract

from arXiv · show

We initiate the study of approximating the top eigenvalue and eigenvector of a random symmetric matrix $ A \in \mathbb{R}^{n\times n} $ using $ q(A)b $ where $q$ is a degree-$d$ polynomial and $b$ is a standard Gaussian vector independent of $A$. For spiked GOE $ Y = \lambda vv^\top + X $, we identify $ d_\star = \frac{\log(n)}{2\log(\lambda)} $ to be the critical degree threshold above which accurate approximation of the top eigenvalue and eigenvector is possible. This sharpens the common belief that spectral methods can be implemented by $ O(\log(n)) $-step power iterations and offers a precise connection between spectral methods and low-degree polynomial algorithms, a popular proxy for all polynomial-time algorithms. For GOE $X$, we identify $ d_\star = n^{1/3+o(1)} $ to be the critical degree threshold for top eigenvector approximation, whereas constant degree suffices for top eigenvalue approximation. Moreover, in the limit where $ d/n^{1/3} $ converges to a positive finite constant, we compute the exact asymptotic eigenvector approximation accuracy in terms of the expected squared overlap. These results significantly improve upon predictions made in randomized numerical linear algebra for deterministic data matrices that the iteration count of power methods with random initialization is governed by the inverse spectral gap. Technically, our analyses leverage extremal properties of Chebyshev polynomials and draw upon the rich literature of random matrix theory.

1 Introduction

The paper studies polynomial approximations to the top eigenvalue and eigenvector of random matrices, identifying critical degree thresholds for spiked GOE and GOE. It also develops growing-degree estimates for GOE linear spectral statistics that support these results.

Context

  • The q(A)b framework captures many randomly initialized iterative algorithms and is a special case of low-degree polynomial estimators.For spiked matrix models, existing work cited here leaves open the algorithmic issue of approximating the top eigenvector; this paper studies polynomial approximations directly.Source: §1 · p. 2

Main results

  • For spiked GOE, the critical degree is log(n)/(2 log(λ), and a Chebyshev-polynomial combination approximates the top eigenvalue and eigenvector above this threshold.The threshold is optimal for estimating the spike even among general polynomials in matrix elements.Source: §1 · pp. 2–3
  • For GOE, constant degree suffices to approximate the top eigenvalue, whereas degree n^1/3+o(1) is necessary and sufficient to well approximate the top eigenvector.The contrast distinguishes eigenvalue from eigenvector approximation in the pure-noise model.Source: §1 · p. 2
  • In the GOE critical regime d ≍ n^1/3, eigenvector approximation accuracy has an exact scaling limit expressed using the Airy point process.The limit applies when d/n^1/3 converges to a positive finite constant.Source: §1 · pp. 2, 4

Context

  • The guarantees are asymptotically exact on average for spiked GOE, while the paper says existing RNLA bounds specialized to these ensembles can lose constants or even an order.The paper does not expect the optimal Chebyshev polynomial or these guarantees to be universal across all matrices.Source: §1 · p. 3

Technical contribution

  • For GOE, the paper estimates linear spectral statistics for polynomials of growing degree, extending classical results that require a fixed test function.A near-order-optimal estimate for Chebyshev polynomials of logarithmic degree is instrumental to the spiked-GOE proofs.Source: §1 · p. 4

2 Setup and preliminaries

The section defines the polynomial approximation setting and the random-matrix ensembles under study. It also introduces second-kind Chebyshev polynomials and their properties used in the analysis.

2 Setup and preliminaries

  • Approximation is measured by the expected squared overlap with the top eigenvector and by the value achieved as an approximation to the top eigenvalue.The matrix A is either GOE or spiked GOE, and the polynomial acts on A applied to an independent Gaussian vector.Source: §2 · p. 5

2.1 GOE and spiked GOE

  • GOE is defined through independent upper-triangular entries, and its spiked counterpart uses a deterministic unit vector and GOE noise.The section also recalls the semicircle law and classical locations of GOE eigenvalues.Source: §2.1 · pp. 5–6

2.2 Chebyshev polynomials

  • Second-kind Chebyshev polynomials are used as an analysis basis, with semicircle orthogonality, a three-term recurrence, and a product-to-sum formula.The section also introduces the associated Christoffel–Darboux kernel.Source: §2.2 · pp. 6–7

3 Main results

This section presents results on spectral approximation in spiked and pure GOE, Bayes-AMP dynamics for a Gaussian prior, and Chebyshev-based polynomials that attain optimal approximation results. It also derives the GOE limiting overlap at degree scale d/n^(1/3) by analyzing Chebyshev coefficient profiles and optimizing over their weak limits.

3.1 Results for spiked GOE

  • Degrees d ≫ δc log(n) permit vanishing-error top eigenvalue and eigenvector approximation in spiked GOE, whereas d ≪ δc log(n) permits neither with nontrivial accuracy.The phase transitions of OPTn,d and VALn,d are governed by the scaling limit of Kd(λ⋆, λ⋆)/n.Source: §3.1 · p. 7
  • In spiked GOE, qopt and qval are Chebyshev-polynomial combinations that maximize the eigenvector and Rayleigh-quotient objectives, respectively.The proof uses Chebyshev polynomials, which are orthonormal with respect to the limiting semicircle law.Source: §3.1 · pp. 9–10

3.2 Results for spiked GOE with a prior

  • For the Gaussian prior, Bayes-AMP is a one-step-memory power iteration, and state evolution establishes top-eigenvector alignment under a stationary initialization independent of X.Theorem 3 also gives an asymptotically exact characterization of its dynamics from random initialization when t/log(n) → δ.Source: §3.2 · pp. 10–12

3.3 Results for GOE

  • For every fixed GOE degree d, Theorem 5 gives the exact limiting optimal eigenvalue approximation; degree O(1/√ε) suffices for asymptotic value 2(1 − ε), achieved by qval.This improves the O(1/ε) degree dependence in Theorem 4.Source: §3.3 · pp. 12–13
  • For GOE, top eigenvector approximation requires and is achievable at degree n^1/3+o(1); at the critical scale, the paper gives an exact limit for approximation accuracy.The critical-window limit is expressed in terms of OPTn,d.Source: §3.3 · pp. 13–14
  • Multiplying q(x) by x + 2 suppresses contributions near the left spectral edge −2, at the cost of one degree, which is inconsequential in the limit.The sum is otherwise dominated by eigenvalues near the right spectral edge.Source: §3.3 · p. 15
  • The overlap limit follows by combining truncated spectral-edge sums with the top eigenvalues, using independence of the Gaussian weights and Airy point process.The argument takes n → ∞ and then M → ∞, subject to justifying joint convergence and handling modes of convergence.Source: §3.3 · pp. 15–16
  • For d/n^(1/3) → δ, the limiting overlap argument identifies the rescaled polynomial profile with Γδ,u(s), uniformly on compact intervals of s ≤ 0.The s ≥ 0 case follows similarly, and s = 0 follows by continuity.Source: §3.3 · pp. 15–16
  • Although the displayed convergence formally requires strong profile convergence, weak convergence suffices after optimization because the additional limit terms vanish.The discussion does not address the technical details.Source: §3.3 · p. 15
  • Optimizing over weak limits of rescaled Chebyshev coefficient profiles yields the stated asymptotic overlap limit for sequences of nonzero polynomials.The result applies when the profiles converge weakly to a nonzero u in L2([0, 1]).Source: §3.3 · p. 16

4 Numerical experiments

Numerical experiments corroborate the theoretical predictions and investigate cases not covered by the theory. They show degree-dependent transitions, finite-size fluctuations, and similar results when the noise entries are changed to Rademacher variables.

Spiked GOE

  • The squared overlap of qopt(Y)b transitions around δc as degree increases, while finite n leaves a less sharp transition and nontrivial trial-to-trial fluctuations even at n = 16000.The plotted overlap averages 100 trials for each n, with individual trials also shown at n = 16000.Source: §4 · p. 16, Figure 1 · p. 17
  • Near δc, the spiked-GOE Rayleigh quotients follow the predicted 2-to-λ⋆ transition away from the threshold, but qval and qopt differ near it because of finite-n effects.The comparison uses qval below δc and qopt above it; Figure 2 also directly compares their Rayleigh quotients.Source: §4 · p. 16, Figure 2 · p. 17
  • The iteration (38) yields squared-overlap and Rayleigh-quotient transitions of 0-to-1 and 0-to-λ⋆, respectively, around δc.Figure 3 plots overlap in the first row and Rayleigh quotient in the second.Source: §4 · p. 16, Figure 3 · p. 18

GOE

  • For GOE, bvd respects the 1/3 overlap threshold but oscillates above it and does not always attain the maximal value 1.The experiments examine bvd, designed for eigenvalue approximation, where the theory does not provide polynomials optimal across the full range of δ.Source: §4 · p. 16, Figure 4 · p. 18

Universality

  • With Rademacher noise entries replacing GOE entries, the numerical results are visually almost indistinguishable from their GOE counterparts.The experiments repeat those in Figures 1 and 2 with the changed entry distribution.Source: §4 · p. 19, Figure 5 · p. 19, Figure 6 · p. 19

5 Discussion and future directions

The discussion identifies open questions about finite-size fluctuations and extensions beyond GOE. It also highlights the challenge of approximating informative eigenvectors when a spiked invariant ensemble has multiple outlying eigenvalues.

Discussion

  • The paper studies fundamental limits for approximating top eigenvalues and eigenvectors in spiked GOE and GOE, using random matrix theory and developing quantitative estimates of linear spectral statistics.The estimates may also be of independent interest.Source: §5 · p. 19

Universality

  • Figures 7 and 8 repeat the experiments in Figures 3 and 4, respectively, changing X from GOE to Rademacher.The paper describes the Rademacher entries as rescaled to match GOE entry-wise variance.Source: Figure 7 · p. 20, Figure 8 · p. 20

Fluctuation

  • The theory primarily studies expected squared overlap and Rayleigh quotient in large-n,d limits, while finite-size experiments suggest nontrivial fluctuations whose variance remains open.The authors leave the dimension-dependent variance of these quantities for future work.Source: §5 · p. 21

Universality and non-universality

  • The authors expect several GOE results to extend to Wigner matrices under bounded-moment assumptions, but provide no formal justification and do not expect all results to hold for heavy-tailed matrices.They specifically cite GOE eigenvalue rigidity as a proof ingredient and identify conditions for extensions as future work.Source: §5 · p. 21

Invariant ensemble

  • Multiple outliers in spiked invariant ensembles can make the rightmost eigenvector suboptimal, posing a challenge for approximating informative eigenvectors in the middle of the spectrum.The paper notes that achieving the optimal weak recovery threshold may require carefully combining all outlying eigenvectors.Source: §5 · p. 21

6 Proofs for spiked GOE

The proofs establish Theorem 1’s claims for spiked GOE using Chebyshev-polynomial and spectral-measure estimates, kernel asymptotics, matching bounds, and criticality conditions. They also show that the relevant conditions switch at the critical scaling parameter δc and, for logarithmic degree, that H is close to the identity with high probability.

Lemma 9

  • Lemma 9 identifies a unique degree-d maximizer up to sign and gives a maximizing polynomial in terms of rd.Its proofs use Chebyshev-polynomial expansions and orthonormality; the supplied passages do not show the polynomial’s formula.Source: §6 · pp. 21–22

Lemma 10

  • Lemma 10 establishes a spectral-trace comparison for matrices X and Y using a function f of bounded variation.The proof expresses the comparison through the difference of their empirical spectral distribution functions and the total variation of f.Source: §6 · p. 25

Lemma 11

  • For fixed τ∈(0, 2/3) and d=O(log(n)), Lemma 11 gives a high-probability estimate uniformly over 0≤m≤2d+2.The displayed estimate itself is not included in the supplied passage.Source: §6 · p. 25

Lemma 12

  • With probability 1−o(1), ∥H−I_{d+2}∥₂ ≤ Cτ n^(−1+τ)(3d)^5 for d=O(log(n)).Here τ is any fixed constant in (0, 2/3), and Cτ depends only on τ.Source: §6 · p. 28

Lemma 15

  • When d|t − λ⋆| → 0, Lemma 15 gives K_d(λ⋆, t) = (1 + o(1))K_d(λ⋆, λ⋆) and K_d(t, t) = (1 + o(1))K_d(λ⋆, λ⋆).Source: §6 · pp. 31–32

Proof of Item 1

  • For OPT_n,d, the proof establishes Item 1 by matching an upper bound with a lower bound attained asymptotically by q_opt.Source: §6 · pp. 33–34

Proof of Item 2

  • Under assumption (25), matching upper and lower bounds establish VAL_n,d = r_d + o(1).The upper bound holds uniformly over degree-d polynomials, and the lower bound uses q_val.Source: §6 · pp. 34–35

Proof of Item 3

  • Under assumption (27), the proof establishes VAL_n,d → λ⋆ by matching a lower bound with the upper bound E[λ1(Y)] = λ⋆ + o(1).The lower bound uses q_opt and shows its value converges to λ⋆.Source: §6 · p. 36

Proof of Item 4

  • For δ > δc, condition (27) holds; for δ < δc, condition (25) holds, yielding the stated threshold result under scaling assumption (28).The proof uses the asymptotic expansion of the kernel and verifies the limiting behavior of Φ and r_d.Source: §6 · p. 36

7 Proofs for spiked GOE with a prior

The proofs connect Bayes-AMP iterates to polynomial transforms of the spiked matrix and use state evolution to analyze their asymptotic behavior. They establish the claimed threshold behavior by relating polynomial overlap and Rayleigh-quotient quantities to the relevant limits.

Proof of Proposition 2

  • For the prior-based Bayes-AMP recursion, α_t reaches the nontrivial fixed point α = λ^2 − 1, yielding the stated Wasserstein-2 convergence result.The proof uses this fixed point to show the update function is Lipschitz, as required for the cited convergence theorem.Source: §7 · pp. 36–37
  • The state-evolution argument gives x_t converging to the unique fixed point 1 as t tends to infinity, which is used to obtain the second result in (39).The process (X_1, …, X_t) is described as centered Gaussian with recursively specified covariance.Source: §7 · p. 37
  • The proof establishes asymptotic alignment between the iterates and the top eigenvector by shifting Y to a positive-definite matrix and controlling the error in successive limits.The error term vanishes as n, then t, then s tend to infinity.Source: §7 · pp. 37–38

Lemma 16

  • Bayes-AMP iterates can be expressed as scaled polynomial transforms of Y applied to the initialization, by induction using the three-term recurrence for p_t.The displayed relation gives v_{t+1} as a scaled p_{t+1}(Y)v_0.Source: §7 · pp. 38–39

Proof of Theorem 3

  • The proof of Theorem 3 derives the claimed result from a quantity that tends to zero for δ < δc and infinity for δ > δc.The proof combines this threshold behavior with preceding overlap and Rayleigh-quotient limits.Source: §7 · pp. 39–40

8 Proofs for GOE

The proofs for GOE characterize the fixed-degree eigenvalue optimizer and show that eigenvector approximation vanishes below the critical degree and tends to one above it. In the critical case, they establish compact-interval convergence, control the residue term, derive truncated edge-statistic limits using Airy-point-process limits, and use matching bounds to prove convergence of eigenvalue-weight limits and squared-overlap accuracy.

8.1 Eigenvalue approximation

  • The fixed-degree eigenvalue optimization has optimum r_d, attained by q_val.The proof reduces the Rayleigh-quotient optimization to the stated problem and identifies its optimizer.Source: §8.1 · p. 41

8.2 Subcritical case

  • OPT_n,d(GOE(n)) = o(1) under the subcritical degree assumption (44).The proof uses high-probability spectral bounds and a lower bound on eigenvalue counts in intervals of length d^-2.Source: §8.2 · pp. 41, 44

8.3 Supercritical case

  • OPT_n,d(GOE(n)) → 1 under the supercritical scaling (45).The proof uses q(x) = T_d(f_n(x)), bounded in modulus on [−3, u_n] and positive and increasing above u_n.Source: §8.3 · pp. 45–46

8.4 Critical case

  • Under assumption (49), a subsequence of the critical-case tuples converges with edge locations from the Airy point process and a nonnegative limiting scalar.The stated subsequential limits include −Λ_0 ≥ −Λ_1 ≥ ··· from the Airy point process, with Σ ≥ 0 almost surely.Source: §8.4 · pp. 47–48
  • The proof establishes convergence in (171) uniformly on every compact interval of s.For s ≤ 0, it shows the third factor converges uniformly to δ^-3/2Γδ,u(s); the positive-s case follows by analogous estimates.Source: §8.4 · pp. 49–50
  • GOE eigenvalue counting statistics have a uniform variance bound on E ∈ [−2, 2], obtained by transferring a GUE bound through the Forrester–Rains relation [33].The proof also uses tightness of the largest and smallest GOE eigenvalues at the spectral edges.Source: §8.4 · pp. 51–52
  • The residue term in (191) converges to zero in probability, using edge bounds and control of the mean and fluctuations of the rescaled counting statistic.The proof combines the estimates in (202), (208), and (209) to conclude (191).Source: §8.4 · pp. 54, 56
  • For fixed m, the rescaled GOE edge eigenvalues converge jointly to Airy points, yielding convergence of truncated Yℓ statistics and then Yℓ by removing the truncations.The argument passes from finite collections of edge eigenvalues to the truncated limits, then takes N and ℓ′ to infinity.Source: §8.4 · p. 57
  • The limiting critical-case vector is nonnegative almost surely, obtained by taking the degree-truncation limit after convergence for fixed truncation.Source: §8.4 · pp. 59–60
  • For fixed m, the joint limit of S and the first m rescaled polynomial eigenvalue weights is (Σ, Γδ,u(−Λ0)², …, Γδ,u(−Λm−1)²).Source: §8.4 · p. 60
  • The squared-overlap limit has nonnegative excess mass, and the overlap converges in expectation via distributional convergence and boundedness.The excess is σ − ∥u∥²_L2([0,1]); the proof uses the continuous mapping and dominated convergence theorems.Source: §8.4 · p. 64
  • Every unit-norm u in L2([0,1]) admits a sequence of degree-d polynomials whose associated step functions converge strongly to u and whose σn tends to 1.This construction supplies the lower-bound approximants used in the theorem proof.Source: §8.4 · pp. 65–66
  • Matching upper and lower bounds establish the critical-case formula (50) for the limiting optimal GOE approximation accuracy.The upper bound controls subsequential limits; the lower bound uses the polynomial sequence constructed for arbitrary unit-norm u.Source: §8.4 · p. 66

A Auxiliary results

The appendix collects auxiliary results for GOE eigenvalues, outlying-eigenvalue fluctuations, and weak convergence tested over compact sets. It also verifies that GOE meets the assumptions needed to transfer a rigidity result.

A Auxiliary results

  • For n ≥ 3, GOE(n) satisfies the cited rigidity theorem’s spectral assumption, and Gaussian tail bounds verify its fourth assumption.The proof gives C0 = 2 and permits δ−, δ+ to be any positive constants less than 3/4.Source: A Auxiliary results · p. 72
  • The rigidity result for a general matrix H also holds for sufficiently large n with X distributed as GOE(n), after adjusting constants to absorb nuisance factors.The proof invokes [28, Theorem 2.2] and uses the triangle inequality for the transfer.Source: A Auxiliary results · p. 72
  • A proposition addresses Gaussian fluctuations of an outlying eigenvalue for the spiked model Y when λ > 1 is fixed.It refers to λ⋆ as defined in (12).Source: A Auxiliary results · p. 73
  • The compact-set convergence proof combines boundedness of a weakly convergent sequence with finite ε-nets to control inner products uniformly over the compact set.It takes the supremum over the compact set, passes to the limit using weak convergence on the finite net, then sends ε to zero.Source: A Auxiliary results · p. 73

Related papers

Loading 2609.28781v3…