Spectral transition conjecture for censored additive spiked matrices
Spectral transition conjecture for censored additive spiked matrices
Let be random as in the paper's spiked-prior assumption, let be a density defining an additive noise channel , and let denote its Fisher information. Fix and define the local Fisher score , applied entrywise to matrices. Let
where are i.i.d. with density and , and form by independently replacing each upper-triangular entry of by zero with probability , making the same replacement symmetrically below the diagonal. Censored spectral transition conjecture. There exists depending only on and such that: (i) if , then in probability; (ii) if , then for some , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.