6.801/6.866  Machine Vision

Seminar announcement

Hi class, there's a talk happening today some of you might be interested in attending.

Ludwig Schmidt: Approximation-Tolerant Model-Based Compressive Sensing
Speaker: Ludwig Schmidt
Speaker Affiliation: MIT
Host: Ilya Razenshteyn

Date: Wednesday, November 13, 2013
Time: 4:00 PM to 5:00 PM

Location: 32-G575

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.

Relevant URL:
For more information please contact: Joanne Talbot Hanley, 617-253-6054, mailto:joanne@csail.mit.edu ">joanne@csail.mit.edu

Announced on 06 November 2013  2:23  p.m. by Heejung Kim

Welcom & Piazza page

Welcome to 6.801/6.866!
We will be using a Piazza page, where you can ask and answer questions about the course.
Professor Horn and I will also be monitoring the Piazza asks, but we can't guarantee that we will be answering the questions frequently.
If you had questions specifically for Professor Horn or myself, feel free to email us.

Announced on 05 September 2013  2:46  p.m. by Heejung Kim