Ludwig Schmidt: Approximation-Tolerant Model-Based Compressive Sensing

The goal of sparse recovery is to recover a k-sparse signal x from (possibly noisy) linear measurements of the form y=Ax, where A describes the measurement process. Standard results in compressive sensing show that it is possible to recover the signal x from m=O(klog(n/k)) measurements, and that this bound is tight. The framework of model-based compressive sensing (introduced by Baraniuk et al.) overcomes the lower bound and reduces the number of measurements further to O(k) by limiting the supports of x to a subset M of all possible supports. This has led to many measurement-efficient algorithms for a wide variety of signal models, including block-sparsity and tree-sparsity.

However, extending the framework to more general models has been stymied by a key obstacle: for the framework to apply, one needs an algorithm that given a signal x finds the best approximation to x that has support in M (this procedure is often called the “model projection procedure”). An approximation algorithm for this optimization task is not sufficient. Since many problems of this form are not known to have exact polynomial-time algorithms, this requirement poses a fundamental obstacle for extending the framework to a richer class of models. Generalizing the model-based framework to approximate model projections has been a subject of a large body of research in the recent years.

In this talk, we show how to remove this obstacle and extend the model-based compressive sensing framework so that it requires only approximate solutions to the aforementioned optimization problems. Interestingly, our extension requires the existence of two approximation algorithms, one for the maximization and one for the minimization variants of the optimization problem. We then apply our framework to the Constrained Earth Mover’s Distance (CEMD) model, obtaining a sparse recovery scheme that uses significantly less than O(klog(n/k)) measurements.

Joint work with Chinmay Hegde and Piotr Indyk.