Research map / Learning theory and algorithms / Matrix and tensor methods
Coherence-free Entrywise Estimation of Eigenvectors in Low-rank Signal-plus-noise Matrix Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a coherence-free entrywise eigenvector estimator for rank-one spiked models that refines the leading eigenvector using a data-driven set of large entries, achieving near-minimax l_inf error without coherence dependence, plus new metric entropy lower bounds for rank-r subspaces under l_{2,inf}.
Problem
Entrywise (l_inf / l_{2,inf}) estimation of eigenvectors of a low-rank signal matrix under noise is typically suboptimal, with error depending on the coherence of the signal eigenvectors.
Approach
Refine the leading eigenvector by summing entries of the observed matrix indexed by a estimated set of large-magnitude eigenvector entries, using the signal-dominated submatrix to build a new estimate for large entries and keeping spectral estimates for small entries; the resulting error bound has no dependence on coherence under Gaussian noise.
Key results
- Under Gaussian noise the proposed rank-one estimator shows no visible dependence on coherence mu, while the spectral estimator degrades as mu grows (simulations with n up to 15100, 20 trials).
- Theorem gives d_infty bound C sqrt(nu_W) (log n)^{5/2} / |lambda*| with probability 1-O(n^{-8} log n), matching the Gaussian-noise minimax rate up to log factors when |lambda*| = Omega(sigma sqrt(n log n)).
- New metric entropy lower bound log M(K_{r,mu}, d_{2,inf}, delta) gtrsim r^2/delta^2 yields improved minimax lower bound min{sigma sqrt(r)/lambda_r, sqrt(mu r/(n log(n/mu)))} for rank-r eigenspace estimation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace the leading-eigenvector estimate with the coherence-free estimator | Rank-one eigenvector estimation · Gaussian noise; high-coherence signals | d∞ error | Helped |
| replace the leading-eigenvector estimate with the coherence-free estimator | Rank-one eigenvector estimation · Rademacher noise; high-coherence signals | d∞ error | Helped |
| replace the leading-eigenvector estimate with the coherence-free estimator | Rank-one eigenvector estimation · Laplacian noise; high-coherence signals | d∞ error | Helped |
| use the coherence-free estimator instead of the spectral estimator | Rank-r eigenvector estimation · Gaussian noise; rank 2 | d∞ error | Helped |
| use the coherence-free estimator instead of the spectral estimator | Rank-r eigenvector estimation · Rademacher noise; rank 2 | d∞ error | Helped |
| use the coherence-free estimator instead of the spectral estimator | Rank-r eigenvector estimation · Laplacian noise; rank 2 | d∞ error | Helped |
| use the coherence-free estimator instead of the spectral estimator | Rank-r eigenvector estimation · Rank 3; appendix simulations | d₂,∞ error | Helped |
| use the proposed estimator instead of AMP | Eigenvector estimation · Appendix comparison | entrywise and ℓ₂,∞ error | Helped |
| use AMP instead of the proposed estimator | Eigenvector estimation · Appendix comparison | ℓ₂ error | Mixed |
Surprising findings
- Under Rademacher noise the coherence dependence of the proposed estimator appears reversed relative to the spectral estimator.
- The rank-one method's bounded entrywise error can be achieved even though Haar-random eigenvectors violate the technical gap assumption with high probability, which the authors argue is merely a technical requirement.
Limitations
- Assumes homoscedastic noise.
- Technical gap assumption on eigenvector entries (Assumption 2) and eps_0 dependence may be unnecessary but are required by the proof.
- Rank-r extension lacks theoretical analysis and requires eigengaps to estimate each eigenvector separately.
Experimental setup
Datasets: synthetic spiked Wigner matrices (Gaussian, Laplacian, Rademacher noise)
Benchmarks: simulated spiked Wigner models
Metrics: l_infinity error (d_infty) l_{2,infty} error bootstrap confidence intervals
Baselines: leading eigenvector (spectral method) approximate message passing (AMP)
Builds on: spectral estimation perturbation bounds (Abbe, Fan, Wang, Zhong 2020) Baik-Ben Arous-Péché phase transition Yang-Barron method
Closest papers by meaning
- Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods (NeurIPS 2024 · similarity 0.88)
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.87)
- Entrywise error bounds for low-rank approximations of kernel matrices (NeurIPS 2024 · similarity 0.86)
- Nonlinear Laplacians: Tunable principal component analysis under directional prior information (NeurIPS 2025 · similarity 0.86)
- Perturbation Bounds for Low-Rank Inverse Approximations under Noise (NeurIPS 2025 · similarity 0.85)
- Spectral Estimation with Free Decompression (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.