--------

Title:        NONUNIFORM SPARSE APPROXIMATION VIA HAAR WAVELETS

Speaker:      S. Muthukrishnan, Rutgers Univ. 

Homepage:     http://www.cs.rutgers.edu/~muthu


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

-----------