An ALPS view of Compressive Sensing
V. Cevher, EPFL, Laboratoire de systèmes d'information et d'inférence

Seminar • 13 August 2010

More Info ...Abstract
Compressive sensing (CS) is an alternative to Shannon/Nyquist sampling for acquisition of sparse or compressible signals that can be well approximated by just K<< N elements from an N-dimensional basis. Instead of taking periodic samples, we measure inner products with M≤N random vectors and then recover the signal via a sparsity-seeking optimization or greedy algorithm. The standard CS theory dictates that robust signal recovery is possible from M=O(K log(N/K)) measurements. The implications are promising for many applications and enable the design of new kinds of analog-to-digital converters, cameras and imaging systems, and sensor networks. In this talk, we introduce three first-order, iterative CS recovery algorithms, collectively dubbed algebraic pursuits (ALPS), and derive their theoretical convergence and estimation guarantees. We empirically demonstrate that ALPS outperforms the Donoho-Tanner phase transition bounds for sparse recovery using Gaussian, Fourier, and sparse measurement matrices. We then describe how to use ALPS for CS recovery in redundant dictionaries. Finally, we discuss how ALPS can also incorporate union-of-subspaces-based sparsity models in recovery with provable guarantees to make CS better, stronger, and faster.