### DIMACS Theoretical Computer Science Seminar

Title: Nonuniform Sparse Approximation via Haar Wavelets

Speaker: **S. Muthukrishnan**, DIMACS, Rutgers University

Date: October 11, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

In 1910, Haar introduced a wavelet basis for representing functions
on N points using N projections. Parseval's theorem from circa
1799-1801 shows that picking the largest B such projections yields
the least error in representing any such function with B terms, B < N.
This is an example of a result in UNIFORM sparse approximation theory
where error is taken uniformly as the sum of squares of errors at each
point.

We initiate the study of NONUNIFROM sparse approximation theory where
each point has an IMPORTANCE and we want to minimize the weighted sum
of individual errors. In particular, we study the problem using the
Haar wavelet basis. Parseval's Theorem does not help under nonuniform
importance.

We present the first known polynomial time algorithms for this problem,
taking time O(n^2B/log B) in general; when the IMPORTANCE function is
well-behaved, the running time is near-linear. The goal is to evolve
to some theory of "information content" of the IMPORTANCE functions and
how that affects the complexity of sparse linear approximation using the
Haar basis.

SPEAKER'S NOTE: This talk will be somewhat ad-hoc. This area seems to be
near-natal and therefore has many open problems; so
"Come for the talk, Stay for the open problems".