Abstract: The nascent field of compressed sensing is founded on the fact that high-dimensional signals with simple structures can be recovered accurately from just a small number of randomized samples. Several specific kinds of structures have been explored in the literature, from sparsity and group sparsity to low-rankness. However, two fundamental questions have been left unanswered, namely: What are the general abstract meanings of “structure” and“simplicity”? And do there exist universal algorithms for recovering such structured objects from fewer samples than their ambient dimension? In this talk, I address these two questions. Using algorithmic information theory tools such as the Kolmogorov complexity, we provide a unified definition of structure and simplicity. Leveraging this new definition, we develop and analyze an abstract algorithm, minimum complexity pursuit (MCP), for signal recovery motivated by Occam's Razor. MCP requires just $O(\kappa \log n)$ randomized samples to recover a signal of complexity $\kappa$ and ambient dimension n.
Furthermore, our results establish a new connection between data compression and compressed sensing. In particular, I will show that if the rate-distortion function of a compression algorithm for a class of signals satisfies certain properties, then it can be employed to recover signals of that class from their undersampled set of linear measurements. Since compression algorithms usually use far more complicated signal structures than sparsity, this result may potentially benefit many applications.
This talk is based on joint work with Arian Maleki and Richard Baraniuk.
Bio: Shirin Jalali received her Ph.D. in Electrical Engineering and M.Sc. in Statistics from Stanford University in 2009. Since then, she has been a postdoctoral fellow at the Center for Mathematics of Information at California Institute of Technology. She has received her B.Sc. in Electrical Engineering from Sharif University of Technology in 2002 and her M.Sc. in Electrical Engineering from the same institution in 2004. Her main research interests are in information theory and statistical signal processing.