Sparse representations and approximation theory

This paper is an attempt to both expound and expand upon, from an approximation theorist’s point of view, some of the theoretical results that have been obtained in the sparse representation (compressed sensing) literature. In particular, we consider in detail ℓ1m-approximation, which is fundamental in the theory of sparse representations, and the connection between the theory of sparse representations and certain nn-width concepts. We try to illustrate how the theory of sparse representation leads to new and interesting problems in approximation theory, while the results and techniques of approximation theory can further add to the theory of sparse representations.