Research map / Learning theory and algorithms / Matrix and tensor methods
Nonlinear Laplacians: Tunable principal component analysis under directional prior information
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 nonlinear Laplacian spectral algorithms that add a diagonal term sigma(Y1) to a normalized observation, and characterizes the signal strength needed for outlier eigenvalues in sparse biased PCA and the Gaussian planted submatrix model.
Problem
Detecting and recovering a rank-one signal in noisy symmetric matrices when prior information says the signal is biased toward the all-ones direction (e.g., planted dense subgraphs), where direct PCA is suboptimal.
Approach
Deform the observed matrix by adding a diagonal matrix of a bounded nonlinear function of the row sums (degree profile), forming a nonlinear Laplacian whose top eigenpair is analyzed via free probability and subordination; a suitably chosen sigma lowers the critical signal strength below the direct spectral threshold of 1.
Key results
- For the Gaussian planted submatrix model, a numerically optimized sigma gives beta_* about 0.755-0.765, versus 1 for the direct spectral algorithm (sigma=0).
- Theory shows the degree vector Y1 alone cannot achieve strong detection for any constant beta, yet combined with the spectrum it lowers the detection threshold.
- On C. elegans, for a 15-vertex dense subgraph, a nonlinear Laplacian finds one with 73% of possible edges versus 65% for the naive spectral algorithm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add a suitably tuned nonlinear diagonal term based on the degree vector | Direct spectral algorithm on Gaussian Planted Submatrix · Gaussian Planted Submatrix | critical signal strength β*: 1 -> < 0.76 | Helped |
| Replace the direct spectral algorithm with a nonlinear Laplacian using a Z-shaped nonlinearity (ablation) | Direct spectral algorithm · Gaussian Planted Submatrix | critical signal strength β*: 1 -> \num{0.765} | Helped |
| Replace the direct spectral algorithm with a nonlinear Laplacian using an S-shaped sigmoid (ablation) | Direct spectral algorithm · Gaussian Planted Submatrix | critical signal strength β*: 1 -> \num{0.755} | Helped |
| Learn the nonlinear diagonal function with an MLP (ablation) | Nonlinear Laplacian · Gaussian Planted Submatrix | critical signal strength β*: 1 -> \num{0.759} | Helped |
| Optimize a step-function diagonal nonlinearity (ablation) | Nonlinear Laplacian · Gaussian Planted Submatrix | critical signal strength β*: 1 -> \num{0.755} | Helped |
| Use only the eigenvalues of the observed matrix, without the degree-vector diagonal term (ablation) | Gaussian Planted Submatrix detection · Gaussian Planted Submatrix | strong detection below β = 1 | Hurt |
| Use only the degree vector, without spectral information (ablation) | Gaussian Planted Submatrix detection · Gaussian Planted Submatrix | strong detection | Hurt |
| Use a nonlinear Laplacian instead of the naive spectral algorithm | C. Elegans network dense-subgraph search · C. Elegans network, 15-vertex dense subgraph | fraction of possible edges present: 65% -> 73% | Helped |
Surprising findings
- The degree vector Y1 alone is useless for strong detection at any constant signal strength, yet adding it as a diagonal deformation substantially improves the spectral threshold.
Limitations
- Theoretical results are proven for compressed nonlinear Laplacians and GOE noise; extension to other noise models (e.g., planted clique) is only conjectured.
- Critical threshold beta_*(sigma) is computed numerically from integral equations, not in closed form.
- Analysis assumes sparse or biased signals with specific distributional assumptions; general behavior on dense signals is not proven.
Experimental setup
Datasets: synthetic Gaussian planted submatrix instances C. elegans neural network
Benchmarks: Gaussian planted submatrix (synthetic) C. elegans neural network dense subgraph search
Metrics: outlier eigenvalue threshold beta_* squared correlation of top eigenvector with signal edge density of found subgraph
Baselines: direct spectral algorithm (sigma=0) belief propagation approximate message passing
Builds on: BBP phase transition Non-Negative PCA free probability additive convolution
Closest papers by meaning
- Generalized Laplacian in Spectral Seriation on Manifold Data (NeurIPS 2026 · similarity 0.88)
- Sparse Quantized Spectral Clustering (ICLR 2021 · similarity 0.88)
- Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods (NeurIPS 2024 · similarity 0.86)
- The Noisy Laplacian: a Threshold Phenomenon for Non-Linear Dimension Reduction (ICML 2025 · similarity 0.86)
- Coherence-free Entrywise Estimation of Eigenvectors in Low-rank Signal-plus-noise Matrix Models (NeurIPS 2024 · similarity 0.86)
- Spectral Estimation with Free Decompression (NeurIPS 2025 · similarity 0.86)
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.