Research Group
| Seminar | WSU Colloquium
| Department Home

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.