Video: Exact Recovery via Convex Relaxations

There is only a video for that presentation from Spectral Algorithms: From Theory to Practice organized at the Simons Institute at Berkeley.

Exact Recovery via Convex Relaxations, Moses Charikar

When do convex relaxations return integer solutions? In this talk, I will discuss several instances of discrete optimization problems where, for a suitable distribution on inputs, LP and SDP relaxations produce integer solutions with high probability. This phenomenon has been studied in the context of LP decoding, sparse recovery, stochastic block models and so on. I will also mention some recent results for clustering problems: when points are drawn from a distribution over k sufficiently separated clusters, the well known k-median relaxation and a (not so well known) SDP relaxation for k-means exactly recover the clusters.

Download Video [2.2GB .mp4]

  Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.