0.25
0.5
0.75
1.25
1.5
1.75
2
Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
Published on Aug 20, 20151645 Views
Given a large data matrix $A\in\reals^{n\times n}$, we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution $A_{ij}\sim P_0$, or instead $A$ contain
Related categories
Chapter list
Sum-of-squares Lower Bounds for Hidden Clique00:00
The Setup00:00
Not ordered ...00:32
Not colored ...00:39
The Setup - 200:43
Outline 01:04
Motivation01:23
Statistically ...01:49
Spectral methods: the state of the art02:20
Sparse PCA - 103:20
Sparse PCA - 203:35
Sparse PCA - 303:38
Summarizing ...03:43
Prior computational lower bounds04:03
Question04:42
Sum of squares04:58
Sum of squares for (Hidden) Clique06:02
SOS relaxation06:53
SOS(d) for (Hidden) Clique 07:32
A Sum of Square test08:27
Untitled08:55
Main Result: hardness for SOS (4)09:23
Comments10:23
Proof strategy10:57
The witness for d=4 - 111:55
The witness for d=4 - 212:45
The witness for d=4 - 312:57
Comparing - 113:10
Comparing - 213:29
A toy example14:06
The Moment Method14:40
Conlusions15:44