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".