Harmonic Analysis and Signal Processing Seminar
Nonuniform Sparse Approximation via Haar Wavelets
S. Muthukrishnan, Rutgers
Wednesday, September 15, 2004, 2-3:00pm, WWH 1314
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 NONUNIFORM 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(N2B/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".