One of the central problems of modern mathematical approximation
theory is to approximate functions, or signals, concisely, with
elements from a large candidate set called a dictionary.  Formally, we
are given an N-dimensional signal S and a dictionary D of unit vectors
that span R^N. A representation of B terms for the input signal S is a
linear combination of dictionary elements.  Typically, B is much
smaller than N, so that the representation is a concise approximation
to S.  The L^2 error of the representation indicates how well it
approximates S.  The problem is to find the best B-term
representation, {\em i.e.}, find a representation that minimizes the
L^2 error.  

<BR>
<BR>
A dictionary may be redundant in the sense that there is
more than one possible exact representation for S.  Redundant
dictionaries are used because, both theoretically and in practice, for
important classes of signals, as the size of a dictionary increases,
the error and the conciseness of the approximations improve.

<BR>
<BR>
We present the first known efficient algorithm for finding a provably
approximate representation for an input signal over redundant
dictionaries. We identify and focus on redundant dictionaries with
small coherence (ie., vectors are nearly orthogonal).  We present an
algorithm that preprocesses any such dictionary in time and space
polynomial in the size of the dictionary, and obtains a 1 + epsilon
approximate representation of the given signal in time nearly linear
in signal size N and polylogarithmic in |D|; by contrast, most
algorithms in the literature require Omega(|D|) time, and, yet,
provide no provable bounds. The technical crux of our result is our
proof that two commonly used local search techniques, when combined
appropriately, gives a provably near-optimal signal representation
over redundant dictionaries with small coherence.  Our result
immediately applies to several specific redundant dictionaries
considered by the domain experts thus far.  In addition, we present
new redundant dictionaries which have small coherence (and therefore
are amenable to our algorithms) and yet have significantly large
sizes, thereby adding to the redundant dictionary construction
literature.