Sharp conditions for exact recovery of general planted subgraphs in ER graphs are given by the minimal maximum subgraph density, with matching bounds, a spectral algorithm, and computational hardness results via low-degree polynomials.
Testing in high-dimensional spiked models
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
We consider the five classes of multivariate statistical problems identified by James (1964), which together cover much of classical multivariate analysis, plus a simpler limiting case, symmetric matrix denoising. Each of James' problems involves the eigenvalues of $E^{-1}H$ where $H$ and $E$ are proportional to high dimensional Wishart matrices. Under the null hypothesis, both Wisharts are central with identity covariance. Under the alternative, the non-centrality or the covariance parameter of $H$ has a single eigenvalue, a spike, that stands alone. When the spike is smaller than a case-specific phase transition threshold, none of the sample eigenvalues separate from the bulk, making the testing problem challenging. Using a unified strategy for the six cases, we show that the log likelihood ratio processes parameterized by the value of the sub-critical spike converge to Gaussian processes with logarithmic correlation. We then derive asymptotic power envelopes for tests for the presence of a spike.
fields
cs.IT 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Recovery of Planted Subgraphs
Sharp conditions for exact recovery of general planted subgraphs in ER graphs are given by the minimal maximum subgraph density, with matching bounds, a spectral algorithm, and computational hardness results via low-degree polynomials.