Fundamental Limits for Broken Sample Problems
Time: 2024-05-27
Published By: Ruixin Li
Speaker(s): Jiaming Xu(Duke University)
Time: 16:00-17:00 May 28, 2024
Venue: Room 77201, Jingchunyuan 78, BICMR
Abstract: In this talk, I will explore a classic statistical challenge: the broken sample problem. Imagine a random sample of vectors is drawn from a joint distribution. Before observing them, each vector in the sample is broken into two subvectors and the original pairing information is lost. The central question we address is whether it is possible to recover this lost pairing information just by observing these two sets of subvectors. The broken sample problem has a rich history in statistics, dating back to the 1960s, with initial applications in matching records for surveys and censuses. Recently, this problem has gained renewed interest due to its relevance in fields such as data de-anonymization, robotics, multi-target tracking, signal processing, and data integration. It encapsulates a range of related problems found in the literature, including record linkage, database alignment, geometric matching, and shuffled regression. Despite extensive research over the past decade, determining the precise statistical thresholds for detection and estimation has remained a challenge. In this presentation, I will discuss our latest progress in determining these thresholds and important open problems on this topic. Part of the talk is based on joint work with Leon Lufkin and Yihong Wu from Yale University. The preprint is available at https://arxiv.org/abs/2402.09693
Bio-Sketch: Jiaming Xu is an associate professor at the Fuqua School of Business at Duke University. He received a Ph.D. degree from UIUC in 2014, an M.S. degree from UT-Austin in 2011, and a B.E. degree from Tsinghua University in 2009, all in Electrical and Computer Engineering. His research interests include high-dimensional statistics, networks, information theory, convex and non-convex optimization, and queueing theory. He received a Simons-Berkeley Fellowship in 2016 and an NSF Career Award in 2022.
Bio-Sketch: Jiaming Xu is an associate professor at the Fuqua School of Business at Duke University. He received a Ph.D. degree from UIUC in 2014, an M.S. degree from UT-Austin in 2011, and a B.E. degree from Tsinghua University in 2009, all in Electrical and Computer Engineering. His research interests include high-dimensional statistics, networks, information theory, convex and non-convex optimization, and queueing theory. He received a Simons-Berkeley Fellowship in 2016 and an NSF Career Award in 2022.