Convex Geometry for Structured Signal Recovery: New Results in Super-Resolution and Total Variation Minimization

Thursday, January 28, 2016 - 3:15pm - 4:05pm
Keller 3-180
Weiyu Xu (The University of Iowa)
In this talk, we 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: a total variation minimization for recovering gradient-sparse signals and a low-rank Hankel matrix completion for super-resolution of spectrally sparse signals. Using the tool of Gaussian width, we obtain counter-intuitive performance bounds on the sample complexity for these two applications. For 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.

For 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.
MSC Code: