图 书 馆
稀疏主成分检测的复杂性理论下界Complexity Theoretic Lower Bounds for Sparse Principal Component Detection |
|
| 课程网址: | http://videolectures.net/colt2013_berthet_sparse/ |
| 主讲教师: | Quentin Berthet |
| 开课单位: | 普林斯顿大学 |
| 开课时间: | 2013-08-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | In the context of sparse principal component detection, we bring evidence towards the existence of a statistical price to pay for computational efficiency. We measure the performance of a test by the smallest signal strength that it can detect and we propose a computationally efficient method based on semidefinite programming. We also prove that the statistical performance of this test cannot be strictly improved by any computationally efficient method. Our results can be viewed as complexity theoretic lower bounds conditionally on the assumptions that some instances of the planted clique problem cannot be solved in randomized polynomial time. |
| 关 键 词: | 稀疏主成分; 统计代价; 计算效率; 检验; 统计性能 |
| 课程来源: | 视频讲座网公开课 |
| 最后编审: | 2019-05-26：cwx |
| 阅读次数: | 42 |