High dimensional wavelet smoothing

Ole Moller Nielsen


A fundamental issue in Data Mining is the development of algorithms to extract some useful information from very large databases. One important technique is to estimate a smooth surface approximating the data. However, the number of observations can be of the order of millions and there may be hundreds of variables recorded so one has to deal with the so-called "curse of dimensionality". The algorithmic complexity of this process is of the order N 3d-2 where N is the number of grid points in each dimension and d is the number of dimensions. We propose a method for approximating a high dimensional surface by computing a projection onto multiresolution spaces of low density and we demonstrate that the algorithmic complexity of the multiresolution method is proportional to ((log N ) d-1 N ) 3 --a substantial reduction in computational work. In addition, we show that the approximation error is proportional to d 2 J 2 -2J , the proportionality constant depending on the smoothness of the computed surface.

Full Text:


DOI: http://dx.doi.org/10.21914/anziamj.v42i0.634

Remember, for most actions you have to record/upload into this online system
and then inform the editor/author via clicking on an email icon or Completion button.
ANZIAM Journal, ISSN 1446-8735, copyright Australian Mathematical Society.