Research Group | Seminar | WSU Colloquium | Department Home

Washington State University
Combinatorics, Linear Algebra and Number Theory Seminar

Department of Mathematics and Statistics
  December 7, Monday, 4:10 - 5:00 PM


David Wu


Title: Maximum Likelihood Inference of Random Dot Product Graphs through Conic Programming

We present a convex cone program that attempts to infer the latent vectors of a random dot product graph (RDPG). The optimization problem can be naturally interpreted as an MAP problem with a low rank prior, and has connections to the well-known semidefinite program relaxation of the MaxCut problem. Using the primal-dual optimality conditions, we show asymptotic consistency of the latent vector estimates under mild technical assumptions. Our experiments on synthetic RDPGs not only recover natural clusters, but also reveal the underlying low-dimensional geometry of the original data.