Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
Amelia Perry111The first two authors contributed equally. Email: This work is supported in part by NSF CAREER Award CCF-1453261 and a grant from the MIT NEC Corporation. Department of Mathematics, Massachusetts Institute of Technology Alexander S. Wein Email: This research was conducted with Government support under and awarded by DoD, Air Force Office of Scientific Research, National Defense Science and Engineering Graduate (NDSEG) Fellowship, 32 CFR 168a. Department of Mathematics, Massachusetts Institute of Technology Afonso S. Bandeira Email: A.S.B. was supported by NSF Grant DMS-1317308. Part of this work was done while A.S.B. was with the Department of Mathematics at the Massachusetts Institute of Technology. Department of Mathematics, Massachusetts Institute of Technology Department of Mathematics and Center for Data Science, Courant Institute of Mathematical Sciences, New York University Ankur Moitra Email: This work is supported in part by NSF CAREER Award CCF-1453261, NSF Large CCF-1565235, a grant from the MIT NEC Corporation and a Google Faculty Research Award. Department of Mathematics, Massachusetts Institute of Technology Computer Science and Artificial Intelligence Lab, Massachusetts Institute of Technology
Abstract
A central problem of random matrix theory is to understand the eigenvalues of ‘spiked’ or ‘deformed’ random matrix models, 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é [2005] 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. Subsequently, sharp spectral phase transitions have been proven in many other random matrix models. Such results form the basis of our understanding of when PCA can detect a low-rank signal in the presence of noise, and how well it can estimate it.
中文速览
随机矩阵中的"加噪低秩信号"模型是理解主成分分析（PCA）何时有效的核心框架：当信号强度超过某个临界值时，顶部特征值会从噪声分布中跳出，PCA 因此能检测到信号；低于该阈值时，特征值完全淹没在噪声里。但特征谱并不一定携带全部信息——本文系统研究了在谱阈值之下，是否存在任何统计方法（包括非谱方法）能更早地检测或恢复信号。作者对高斯 Wigner 矩阵证明了 PCA 的谱阈值对多种先验分布确实是信息论最优的，对非高斯 Wigner 矩阵则证明 PCA 永远不是最优的，但通过对矩阵元素做精心设计的逐元变换可以严格改进检测能力；而对 Wishart 系综和群同步（synchronization）问题，他们发现存在计算上低效但统计上更强的方法，能在 PCA 失效的区域成功检测信号，揭示了统计可行性与高效算法之间可能存在本质差距。所有下界均基于 Le Cam 的邻近性（contiguity）框架，通过控制似然比的二阶矩来证明两个分布无法被可靠区分，这一方法不仅适用于渐近分析，在部分情形下还给出了有限样本的非渐近界，为理解高维统计推断的根本极限提供了统一而严格的理论基础。
原文 arXiv:1609.05573;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1609.05573v2