Washington State
University
Combinatorics, Linear Algebra and Number Theory Seminar
Department of Mathematics and Statistics
Zoom
December 7, Monday, 4:10 - 5:00 PM
David Wu
MIT
Combinatorics, Linear Algebra and Number Theory Seminar
Department of Mathematics and Statistics
Zoom
December 7, Monday, 4:10 - 5:00 PM
David Wu
MIT
Title: Maximum
Likelihood Inference of Random Dot Product Graphs
through Conic Programming
Abstract: 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.
Abstract: 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.