Estimating Wavelet Coefficients

We consider fast algorithms of wavelet decomposition of functionf when discrete observations of $$ f(\operatorname{supp} f \subseteq [0,1]) $$ are available. The properties of the algorithms are studied for three types of observation design: the regular design, when the observationsf(x_i) are taken on the regular grid $$ {{\chi }_{i}} = i/N,i = 1, \ldots ,N; $$ the case of jittered regular grid, when it is only known that for all $$ 1{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ < }}i{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ < }}N,i/N{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ < }}{{\chi }_{i}} < (i + 1)/N; $$ the random design case: $$ {{\chi }_{i}}i = 1, \ldots ,N $$are independent and identically distributed random variables on [0,1]. We show that these algorithms are in certain sense efficient when the accuracy of approximation is concerned.The proposed algorithms are computationally straightforward: the whole effort to compute the decomposition is orderN for the sample sizeN.