Rounding Moment Based SDP Relaxations by Column Selection

Rounding Moment Based SDP Relaxations by Column Selection - Ali Kemal Sinop

Ali Kemal Sinop
Institute for Advanced Study; Member, School of Mathematics
October 8, 2013

In this lecture, I will talk about moment based SDP hierarchies (which are duals of SOS relaxations for polynomial optimization) in the context of graph partitioning. The focus will be on a certain way of rounding such hierarchies, whose quality is related to the problem of column based matrix reconstruction. Finally I will describe how to relate this to the spectral or isoperimetric profiles of the underlying constraint graph.