Finding Planted Subgraphs using the Schur-Horn Relaxation

Thursday, January 28, 2016 - 2:00pm - 2:50pm
Keller 3-180
Venkat Chandrasekaran (California Institute of Technology)
Extracting structured planted subgraphs from large graphs is a fundamental question that arises in a range of application domains. We describe a computationally tractable approach based on convex optimization to recover certain families of structured graphs that are embedded in larger graphs containing spurious edges. Our method relies on tractable semidefinite descriptions of majorization inequalities on the spectrum of a matrix, and we give conditions on the eigenstructure of a planted graph in relation to the noise level under which our algorithm succeeds. (Joint work with Utkan Candogan.)