Algorithms and Complexity Seminar
Compressible priors and structured sparsity models
Volkan Cevher (Rice University)
Compressive sensing 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 compressive sensing 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, will describe a set of probability distributions, dubbed compressible priors, whose independent and identically distributed (iid) realizations result in p-compressible signals. A signal is called p-compressible if its sorted coefficients exhibit a power-law decay, where the decay rate is equal to 1/p. I will illustrate that wavelet coefficients of natural images can be well approximated by the compressible priors with a dimension independent p-parameter. I will then show how this observation predicts a disappointing compressive sensing recovery for natural images from compressive measurements that grow only logarithmically with the image dimension.
For compressive sensing to truly live up to its name, it is therefore necessary to leverage concepts from state-of-the-art signal compression and processing algorithms. In many such algorithms, the key ingredient is a more realistic signal model that goes beyond simple sparsity by codifying the inter-dependency structure among the signal coefficients. I will present a new model-based compressive sensing theory that parallels the conventional theory and provides concrete guidelines on how to create model-based recovery algorithms with provable performance guarantees. To demonstrate the new theory, I will focus on how to integrate a relevant signal model -clustered sparsity on wavelet trees - into a state-of-the-art compressive sensing recovery algorithm and prove that the new algorithm offers robust recovery from just M=O(K) measurements.