ON THE COMPUTATION OF WAVELET COEFFICIENTS

We consider fast algorithms of wavelet decomposition of a function f w hen discrete observations of f (supp f subset of or equal to[0,1](d)) are available. The properties of the algorithms are studied for three types of observation design which for d=1 can be described as follows: the regular design, when the observations f(xi) are taken on the regu lar grid x(i)=i/N, i=1, ..., N; the case of a jittered regular grid, w hen it is only known that for all 1 less than or equal to i less than or equal to N, i/N less than or equal to x(i)<i+1)/N; and the random d esign case; in which x(i), i=1, ..., N, are independent and identicall y distributed random variables on [0,1]. We show that these algorithms are in a certain sense efficient when the accuracy of the approximati on is concerned. The proposed algorithms are computationally straightf orward; the whole effort to compute the decomposition is order N for t he sample size N. (C) 1997 Academic Press