What makes sublinear algorithms so fast? Lecture I

Anna Gilbert
University of Michigan

This is a mini-course on sublinear algorithms in sparse signal recovery. It will give an overview of randomized approximation algorithms. It will also include two main topics from which we draw techniques: combinatorial group testing and coding theory.

Lecture 1: Introduction to randomized, approximation algorithms
a. Definitions
b. Goals
c. Examples

Back to Short Course: Sparse Representations and High Dimensional Geometry : In conjunction with the AMS 2007 Von Neumann Symposium