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 recovery can achieve super-resolution of spectrally sparse signals, surprisingly eliminating the usual separation condition on neighboring frequencies required by atomic norm minimization. 
     Very recently, we are able to show no separation requirements on adjacency frequencies are needed for super-resolution using Hankel matrix recovery,  even under non-uniform sampling of spectrally sparse signals. I will also present a newly discovered 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.