|
Applied
Math Seminar |
|
We consider the algorithmic problem of finding a good and
short wavelet representation of a signal of N sample points, presented
in a stream. We allow the sample points to arrive in any order; furthermore,
we allow arbitrary updates to the signal values of the form "add 5 to
the current value of sample number 3." Our main result is that, if there
exists a few-term representation with small L2 error, we can efficiently
find one that is almost as good; otherwise, we can efficiently detect
this fact. Here "efficiently" means using total space and per-item time
at most polylogarithmic in N. Our randomized algorithm succeeds with high
probability over its random choices, but it works on any signal with a
good representation--we make no probabilistic assumption about the small
coefficients. On the other hand, we show that finding even an approximation
to the single largest wavelet coefficient requires space almost sufficient
to store the whole signal, in general (i.e., in case the signal does not
have a good few-term representation). |