题目：From Shuffled Linear Regression to Homomorphic Sensing
报告人：Dr. Manolis Tsakiris, 上海科技大学
地点：教三 308 主持人：李春光
A recent line of research termed Shuffled Linear Regression has been exploring under great generality the recovery of signals from permuted measurements; a challenging problem in diverse fields of data science and machine learning. In its simplest form it consists of solving a linear system of equations for which the right-hand-side vector has been permuted. In the first part of this talk I will present a provably correct method based on algebraic geometry together with its associated algorithm, the latter being a first working solution to this open problem, able to handle thousands of noisy fully permuted measurements in milliseconds. In the second part of the talk I will discuss the issue of uniqueness of the solution, in a general context which I have termed Homomorphic Sensing*. Given a linear subspace and a finite set of linear transformations I will present dimension conditions of algebraic-geometric nature guaranteeing that points in the subspace are uniquely determined from their homomorphic image under some transformation in the set. As a special case, this theory explains the operational regime of Unlabeled Sensing, in which the goal is unique recovery of signals from both permuted and subsampled measurements.
*Has been accepted by ICML2019. Preprint: https://arxiv.org/abs/1901.07852
Manolis Tsakiris is an electrical engineering and computer science graduate of the National Technical University of Athens, Greece. He holds an M.S. degree in signal processing from Imperial College London, UK, and a Ph.D. degree from Johns Hopkins University, USA, in theoretical machine learning, under the supervision of Prof. Rene Vidal. Since August 2017 he is an assistant professor at the School of Information Science and Technology (SIST) at ShanghaiTech University. His main research interests are subspace learning methods and related problems in algebraic geometry. For more information, please visit his homepage.