论文检索

计算高效检验的精确错误率AI 解读

We revisit the fundamental question of simple-versus-simple hypothesis testing with an eye toward computational complexity, as the statistically optimal likelihood ratio test is often computationally intractable in high-dimensional settings. In the classical spiked Wigner model with a general i.i.d. spike prior, we show (conditional on a conjecture) that an existing test based on linear spectral statistics achieves the best possible trade-off curve between type-I and type-II…

低次多项式估计的计算障碍AI 解读

One fundamental goal of high-dimensional statistics is to detect or recover planted structure (such as a low-rank matrix) hidden in noisy data. A growing body of work studies low-degree polynomials as a restricted model of computation for such problems: it has been demonstrated in various settings that low-degree polynomials of the data can match the statistical performance of the best known polynomial-time algorithms. Prior work has studied the power of low-degree…

PCA 的最优性与次优性之一：尖峰随机矩阵模型AI 解读

A central problem of random matrix theory is to understand the eigenvalues of spiked random matrix models, introduced by Johnstone, in which a prominent eigenvector (or “spike”) is planted into a random matrix. These distributions form natural statistical models for principal component analysis (PCA) problems throughout the sciences. Baik, Ben Arous and Péché showed that the spiked Wishart ensemble exhibits a sharp phase transition asymptotically: when the spike strength is…