EE Systems Seminar
Convex Geometry for Structured Signal Recovery: Super-Resolution and Total Variation Minimization
Abstract: In this talk we will explore the performance limits of recovering structured signals from low-dimensional linear projections, using tools from high dimensional convex geometry. In particular, we focus on two signal reconstruction applications: low-rank Hankel matrix completion for super-resolution of spectrally sparse signals, and total variation minimization for recovering gradient-sparse signals. Using the tool of Gaussian width, we obtain counter-intuitive performance bounds on the sample complexity for these two applications.
In recovering spectrally sparse signals, we show that low-rank Hankel matrix completion can achieve super-resolution of spectrally sparse signals, surprisingly eliminating the usual separation condition on neighboring frequencies required by atomic norm minimization.
We further extend our results to non-uniform sampling of spectrally sparse signals. I will also present a new inequality of nuclear norm, as a byproduct of this research.
In investigating the sample complexity of total variation minimization, we show that the required sample complexity grows in the square root of the ambient dimension, rather than the commonly seen logarithm of the ambient dimension. We further obtain precise phase transition for total variation minimization, the characterization of which was open.
Bio: Weiyu Xu received his B.E. in Information Engineering from Beijing University of Posts and Telecommunications in 2002, and a M.S. degree in Electronic Engineering from Tsinghua University in 2005. He received a M.S. and a Ph.D. degree in Electrical Engineering in 2006 and 2009 from California Institute of Technology (Caltech), with a minor in Applied and Computational Mathematics. He is currently an assistant professor in the Department of Electrical and Computer Engineering at the University of Iowa. Since 2015, he has also been on the faculty of Applied and Computational Mathematical Sciences (ACMS) of the University of Iowa. His research interests are large-scale optimization for big data, statistical signal processing, compressed sensing and low rank matrix recovery, and communication. Dr. Xu is a recipient of the Information Science and Technology Fellowship at Caltech, the Charles Wilts best doctoral thesis research award in 2010, and the Iowa Energy Center Impact Award in 2016.
Host: Babak Hassibi
Contact: Katie Pichotta firstname.lastname@example.org