Department of Mathematics and Statistics

Department of Mathematics and Statistics
Department of Mathematics and Statistics

Department Colloquium


Alexei Novikov (Penn State)

Friday, November 15th, 2019

Time: 2:30 p.m.  Place: Jeffery Hall 234

Speaker: Alexei Novikov (Penn State)

Title: The Noise Collector for sparse recovery in high dimensions.

Abstract: The ability to detect sparse signals from noisy high-dimensional data is a top priority in modern science and engineering. A sparse solution of the linear system $Ax=b$ can be found efficiently with an $l_1$-norm minimization approach if the data is noiseless. Detection of the signal's support from data corrupted by noise is still a challenging problem, especially if the level of noise must be estimated. We propose a new efficient approach that does not require any parameter estimation. We introduce the Noise Collector (NC) matrix $C$ and solve an augmented system $Ax+Cy=b+e$, where $e$ is the noise. We show that the $l_1$-norm minimal solution of the augmented system has zero false discovery rate for any level of noise and with probability that tends to one as the dimension of $b$ increases to infinity. We also obtain exact support recovery if the noise is not too large, and develop a Fast Noise Collector Algorithm which makes the computational cost of solving the augmented system comparable to that of the original one. I'll introduce this new method and give its geometric interpretation.

Prof. Alexei Novikov obtained his Ph.D.~from Stanford in 1999 and then held postdoctoral positions at the IMA and at CalTech before joining the Pennsylvania State University where he is now a Professor in the Department of Mathematics. Prof. Novikov specializes in applied analysis and probability. His research has been supported by the NSF since 2006, as well as by the US--Israel Binational Science Foundation from 2005-2009.