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). We discuss future directions and open problems, including implications for redundant dictionaries.