Aug, 2014
稀疏主成分估计中的统计和计算折衷
Statistical and computational trade-offs in estimation of sparse principal components
Tengyao Wang, Quentin Berthet, Richard J. Samworth
TL;DR通过研究计算复杂性理论,发现在满足一定限制的协方差集中条件下存在有效的样本大小范围,在此范围内无法有随机多项式时间算法达到最佳极小风险率;对著名的半定松弛估计方法的理论性能进行研究,揭示了统计效率和计算效率之间微妙的相互作用,此方法为多维数据稀疏主成分分析提供了一种解决方案。