en-es
en
0.25
0.5
0.75
1.25
1.5
1.75
2
Complexity Theoretic Lower Bounds for Sparse Principal Component Detection
Published on Aug 09, 20136388 Views
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
Related categories
Chapter list
Complexity Theoretic Lower Bounds for Sparse Principal Component Detection00:00
Sparce principal component detection (1)00:13
Optimal testing - Gaussian01:38
Optimal testing - Robust (1)03:33
Sparce principal component detection (2)07:35
Optimal testing - Robust (2)07:52
Minimax testing07:56
Polynomial testing07:58
Detection levels08:15
Detection rates08:43
Planted clique problem09:36
Erdos-Renyi graphs (1)09:40
Erdos-Renyi graphs (2)10:15
Erdos-Renyi graphs (3)10:24
Erdos-Renyi graphs (4)11:14
Erdos-Renyi graphs (5)11:16
Planted clique problem (1)11:29
Planted clique problem (2)11:39
Planted clique problem (3)11:51
Hypothesis (1)13:44
Hypothesis (2)15:17
Reduction description16:24
Rates18:29
Untitled19:21