Spectral transition conjecture for censored additive spiked matrices

About 2 years old · traced to

Let x\bm{x} be random as in the paper's spiked-prior assumption, let p(y)p(y) be a density defining an additive noise channel P\mathcal{P}, and let FPF_{\mathcal{P}} denote its Fisher information. Fix η∈(0,1)\eta\in(0,1) and define the local Fisher score f(y)=−p′(y)/p(y)f(y)=-p'(y)/p(y), applied entrywise to matrices. Let

Y(0)=λnxx⊤+W,\bm{Y}^{(0)}=\frac{\lambda}{\sqrt n}\bm{x}\bm{x}^{\top}+\bm{W},

where Wij=Wji∼P0W_{ij}=W_{ji}\sim\mathcal{P}_0 are i.i.d. with density pp and Wii=0W_{ii}=0, and form Y\bm{Y} by independently replacing each upper-triangular entry of Y(0)\bm{Y}^{(0)} by zero with probability η\eta, making the same replacement symmetrically below the diagonal. Censored spectral transition conjecture. There exists γ∈R\gamma\in\mathbb{R} depending only on pp and η\eta such that: (i) if λ<1/(1−η)FP\lambda<1/\sqrt{(1-\eta)F_{\mathcal{P}}}, then n−1/2λmax⁡(f(Y))→γn^{-1/2}\lambda_{\max}(f(\bm{Y}))\to\gamma in probability; (ii) if λ>1/(1−η)FP\lambda>1/\sqrt{(1-\eta)F_{\mathcal{P}}}, then for some ε=ε(λ)>0\varepsilon=\varepsilon(\lambda)>0, n−1/2λmax⁡(f(Y))→γ+εn^{-1/2}\lambda_{\max}(f(\bm{Y}))\to\gamma+\varepsilon in probability. This predicts that entrywise Fisher-score preprocessing yields a spectral algorithm whose transition matches the computational threshold suggested by the censored channel's Fisher information. The source says the conjecture is numerically verifiable but non-trivial to prove using standard random-matrix techniques because censoring corrupts the additive structure.

References

Primary source

Dmitriy Kunisky, “Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing”, arXiv:2403.07862 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.