Sketching semidefinite programs for faster clustering

Dustin G. Mixon, Kaiying Xie

Many clustering problems enjoy solutions by semidefinite programming. Theoretical results in this vein frequently consider data with a planted clustering and a notion of signal str…