The Taub Faculty of Computer Science Events and Talks

Compressive sensing (CS), also known as compressive sampling, has become widely popular in recent years. In the first part of the talk, we review the little known fact, that the invention of CS preceded the papers that popularized it by almost a decade. Spectrum-blind sampling (SBS), proposed by Bresler and Feng in the mid-90’s, and further developed into “image compression on the fly,” with Venkataramani, and Gastpar, is the first known compressed sensing technique. This work from the 1990's already included the conceptual breakthrough of sampling at the sparsity level, theoretical guarantees and computationally efficient algorithms, treatment of both finite-length vectors and analog sampling, of the single-vector case and of jointly-sparse recovery (the so-called multiple measurement vector problem), and applications to imaging. In the second part of the talk, guided by the applications that originally spurred the invention of CS in the 1990's, and which have continued to motivate much of the work on CS to date, we examine the current status of CS theory and algorithms. We find that in spite of deep and seminal contributions in this area, the available results have some limitations. The most powerful performance guarantees for polynomial-time algorithms have been obtained for unstructured random Gaussian or sub-Gaussian sensing matrices. However, in most practical applications, such sensing matrices are infeasible, owing to either the physics of the acquisition system, or computational cost. On the other hand, the performance guarantees for structured sensing matrices that arise in practice are too conservative, or inapplicable. Another weakness of current CS has been the extension to jointly-sparse recovery: algorithms that perform well in practice are computationally expensive, and those that are fast, have inferior performance. We describe new results that address both of these limitations of current theory and algorithms. Expanding on the ideas first proposed for SBS and image compression on the fly, we describe new guaranteed algorithms for jointly-sparse recovery, which provide the best of both worlds: they are fast, and perform at least as well as the best known (but expensive) algorithms. Addressing the broader problem of sensing with structured matrices, we develop new tools for performance guarantees, and new efficient algorithms to which these guarantees are applicable. The new algorithms are not only guaranteed under more lenient conditions that are satisfied in practical compressive sensing systems, but, in numerical experiments, they also perform better than existing algorithms.