Jul, 2016
聚类、稀疏 PCA 和子矩阵定位中的信息论限制和相变
Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
Jess Banks, Cristopher Moore, Nicolas Verzelen, Roman Vershynin, Jiaming Xu
TL;DR研究了检测结构化低秩信号矩阵被加性高斯噪声污染的问题,包括在高斯混合模型中的聚类, 稀疏主成分分析和子矩阵定位。通过将第一和第二时刻方法应用于这些 “种植模型” 和零模型之间的似然比来导出阈值的上下界,我们证明了在信号矩阵过于微弱时没有任何算法可以检测其信号。