Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
复制标题
尖峰随机矩阵和同步的 PCA 最优性和次优性
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ankur Moitra
中科院分区：
文献类型：
--
作者：
Amelia Perry;Alexander S. Wein;A. Bandeira;Ankur Moitra
随机矩阵理论的一个中心问题是理解尖峰随机矩阵模型的特征值，其中一个显着的特征向量被植入到随机矩阵中。这些分布形成了自然的统计模型，用于整个科学领域的主成分分析（PCA）问题。Baik，Ben Arous和Peche表明，尖峰Wishart系综渐近地表现出尖锐的相变：当信号强度高于临界阈值时，可以根据顶部特征值检测到尖峰的存在，并且低于阈值，顶部特征值不提供任何信息。这样的结果形成了我们的理解的基础上，当PCA可以检测到一个低秩信号中存在的噪声。
然而，并非所有关于尖峰的信息都必须包含在频谱中。我们研究的统计方法，包括非光谱的基本限制。我们的成果包括：
I）对于高斯维格纳系综，我们表明PCA实现了各种良性先验的尖峰的最佳检测阈值。我们扩展了以前的工作，球对称和i.i.d. Rademacher先验通过一个基本的，统一的分析。
II）对于任何非高斯Wigner系综，我们证明了PCA总是次优检测。然而，PCA的一个变体通过根据精心设计的函数对矩阵项进行预变换来实现最佳阈值（对于良性先验）。这种方法之前已经陈述过，我们给出了严格和一般的分析。
III）对于高斯Wishart系综和各种组上的同步问题，我们表明，效率低下的程序可以在PCA成功的阈值以下工作，而没有已知的有效算法实现这一点。在统计上可能做到的和可以有效做到的之间的这种技术差距仍然存在。
A central problem of random matrix theory is to understand the eigenvalues of spiked random matrix models, in which a prominent eigenvector 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 Peche showed that the spiked Wishart ensemble exhibits a sharp phase transition asymptotically: when the signal strength is above a critical threshold, it is possible to detect the presence of a spike based on the top eigenvalue, and below the threshold the top eigenvalue provides no information. Such results form the basis of our understanding of when PCA can detect a low-rank signal in the presence of noise.
However, not all the information about the spike is necessarily contained in the spectrum. We study the fundamental limitations of statistical methods, including non-spectral ones. Our results include:
I) For the Gaussian Wigner ensemble, we show that PCA achieves the optimal detection threshold for a variety of benign priors for the spike. We extend previous work on the spherically symmetric and i.i.d. Rademacher priors through an elementary, unified analysis.
II) For any non-Gaussian Wigner ensemble, we show that PCA is always suboptimal for detection. However, a variant of PCA achieves the optimal threshold (for benign priors) by pre-transforming the matrix entries according to a carefully designed function. This approach has been stated before, and we give a rigorous and general analysis.
III) For both the Gaussian Wishart ensemble and various synchronization problems over groups, we show that inefficient procedures can work below the threshold where PCA succeeds, whereas no known efficient algorithm achieves this. This conjectural gap between what is statistically possible and what can be done efficiently remains open.
影响因子：
2.5
作者：
Singer, A.
通讯作者：
Singer, A.
关于高斯随机矩阵中大平均和方差分析拟合子矩阵的最大尺寸。
DOI：
10.3150/11-bej394
发表时间：
2013
期刊：
Bernoulli : official journal of the Bernoulli Society for Mathematical Statistics and Probability
影响因子：
--
作者：
Sun,Xing;Nobel,AndrewB
通讯作者：
Nobel,AndrewB