Approximation and compression of scattered data by meshless multiscale decompositions

We introduce a class of multiscale decompositions for scattered discrete data, motivated by sensor network applications. A specific feature of these decompositions is that they do not rely on any type of mesh or connectivity between the data points. The decomposition is based on a thinning procedure that organizes the points in a multiscale hierarchy and on a local prediction operator based on least-square polynomial fitting. We prove that the resulting multiscale coefficients obey the same decay properties as classical wavelet coefficients when the analyzed function has some local smoothness properties. This yields compression capabilities that we illustrate by numerical experiments.