SDP Gaps from Pairwise Independence.
Siavosh BenabbasKonstantinos GeorgiouAvner MagenMadhur TulsianiPublished in: Theory Comput. (2012)
Keyphrases
- pairwise
- semi definite programming
- pairwise constraints
- metric learning
- semidefinite programming
- multi class
- higher order
- markov random field
- semi supervised
- high order
- similarity function
- pairwise interactions
- semidefinite
- spectral clustering
- graph matching
- dependence structure
- semidefinite program
- loss function
- conditional independence
- independence assumption
- belief propagation
- convex programming
- linear programming
- similarity measure
- dissimilarity matrix
- data sets