Algorithmic Theory of Sparse Approximation Problems

We are given a dictionary D of N dimensional vectors.
Later, we are given a signal A that is also an N dimensional vector.
Our problem is to find the best B term representation---
linear combination of B vectors from D---for the given signal A.
This is the general sparse approximation problem
and it has applications in many areas---signal
processing, harmonic analysis, communication theory, compression
---depending on the nature of D and  the notion of
error in the representation.

In this talk, I will present an overview of classical as well as modern
algorithmic results on this problem, with special
focus on "Compressed Sensing", a new direction formulated recently.