Spectral transition conjecture for censored additive spiked matrices

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=WjiP0W_{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 n1/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, n1/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.

Sources & referencesView supporting material

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.