Jiaming Xu (Duke)

May 7, 2021

Title and Abstract

The planted matching problem: Sharp threshold and infinite-order phase transition

Abstract: Motivated by applications such as particle tracking, we study the planted matching problem, where the goal is to reconstruct a perfect matching planted in a randomly weighted bipartite graph, whose planted and unplanted edge weights are independently drawn from two different distributions. We determine the sharp threshold at which the optimal reconstruction error (fraction of misclassified edges) exhibits a phase transition from non-zero to zero. Furthermore, in the special case of exponential weight distributions, this phase transition is shown to be of infinite-order and we further determine the reconstruction error of the maximum likelihood estimation in terms of a system of differential equations that result from a message-passing algorithm.

The talk is based on joint work with Jian Ding (Penn), Yihong Wu (Yale), Dana Yang (Duke), Mehrdad Moharrami (UIUC), and Cristopher Moore (SFI). Preprints available at https:arxiv.orgabs2103.09383 and https:arxiv.orgabs1912.08880.

Bio

Jiaming Xu is an assistant professor in the Fuqua School of Business at Duke University. He received the Ph.D. degree from UIUC in 2014 under the supervision of Prof. Bruce Hajek, the M.S. degree from UT-Austin in 2011, and the B.E. degree from Tsinghua University in 2009, all in Electrical and Computer Engineering. He received a Simons-Berkeley Fellowship in 2016. His research interests include high-dimensional statistics, information theory, convex and non-convex optimization, and queueing theory