Ludwig Schmidt: Approximation-Tolerant Model-Based Compressive Sensing

Speaker: Ludwig Schmidt , MIT

Date: Wednesday, November 13, 2013

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Ilya Razenshteyn

Contact: Joanne Talbot Hanley, 617-253-6054,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,,

Reminder Subject: TALK: Algorithms and Complexity Seminar: 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 signi?cantly less than O(klog(n/k)) measurements.

Joint work with Chinmay Hegde and Piotr Indyk.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Joanne Talbot Hanley Email at Wednesday, October 30, 2013 at 10:34 AM.