Research map / Learning theory and algorithms / Matrix and tensor methods
Spectral Phase Transition and Optimal PCA in Block-Structured Spiked 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.
Proves that PCA on a transformed block-structured spiked Wigner matrix has a BBP-type phase transition at the algorithmic threshold lambda_1(Omega_K)=1, and characterizes the outlier location and overlap with the signal.
Problem
Spectral detection and reconstruction in inhomogeneous (block-structured variance-profile) spiked Wigner models, where the BBP phase transition for outliers and overlaps was only conjectured or studied in restricted cases.
Approach
Applies PCA to a linearly transformed matrix Y-tilde (Hadamard rescaling by inverse variance profile minus a diagonal correction) and uses a quadratic vector equation for the Stieltjes transform with a Perron-Frobenius/Farkas argument to show the outlier and overlap transition occur exactly at lambda_1(Omega_K)=1, with an explicit overlap formula.
Key results
- For lambda_1(Omega_K) <= 1 there is no outlier outside the bulk and the overlap vector mu converges to zero.
- For lambda_1(Omega_K) > 1 the top eigenvalue of Y-tilde/sqrt(N) converges to 1 and separates from the bulk, with |mu| given by C^{-1/2} D_{rho^{1/2}}(1_K - g(1)).
- The transition threshold of PCA on the transformed matrix matches the optimal algorithmic recovery threshold lambda_1(Omega_K)=1, proving Conjecture 2.6 of prior work.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply PCA to the transformed matrix Ỹ instead of the original matrix Y | Spectral detection for the inhomogeneous spiked Wigner model · Inhomogeneous spiked Wigner model | detection threshold | Helped |
| Apply PCA to the transformed matrix Ỹ instead of Y ⊙ Δ^(⊙−1/2) | Spectral detection for the inhomogeneous spiked Wigner model · Inhomogeneous spiked Wigner model | detection threshold | Helped |
| Use PCA on Ỹ when λ₁(Ω_K) ≤ 1 | PCA on transformed matrix Ỹ · Inhomogeneous spiked Wigner model, λ₁(Ω_K) ≤ 1 | overlap with signal: overlap converges to 0 | No clear effect |
| Use PCA on Ỹ when λ₁(Ω_K) > 1 | PCA on transformed matrix Ỹ · Inhomogeneous spiked Wigner model, λ₁(Ω_K) > 1 | top eigenvalue: λ₁(Ỹ/√N) → 1 | Helped |
| Increase λ₁(Ω_K) across the threshold 1 | PCA on transformed matrix Ỹ · Inhomogeneous spiked Wigner model | overlap with signal: λ₁(Ω_K) = 1 | Helped |
Limitations
- Analysis restricted to rank-one signal and block-constant variance profile with fixed K.
- Assumes Gaussian noise for the proof, with universality invoked for extension.
- Limiting overlap constant C is given only implicitly via a root of a quadratic vector equation without closed form.
Experimental setup
Baselines: linearized AMP spectral method on Y spectral method on Y Hadamard Delta^{-1/2}
Builds on: BBP phase transition approximate message passing Perron-Frobenius theorem
Closest papers by meaning
- Fluctuations of the largest eigenvalues of transformed spiked Wigner matrices (ICML 2025 · similarity 0.88)
- Optimal Spectral Transitions in High-Dimensional Multi-Index Models (NeurIPS 2025 · similarity 0.88)
- Random Matrix Theory of Early-Stopped Gradient Flow: A Transient BBP Scenario (NeurIPS 2026 · similarity 0.87)
- Free Decompression with Algebraic Spectral Curves (NeurIPS 2026 · similarity 0.84)
- Coherence-free Entrywise Estimation of Eigenvectors in Low-rank Signal-plus-noise Matrix Models (NeurIPS 2024 · similarity 0.84)
- Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods (NeurIPS 2024 · similarity 0.84)
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.