Adaptive Least Square Approximation of Signals

The purpose of this paper is to present an adaptive algorithm to find the best approximation in the least square sense of a given signal. The proposed method takes advantage of the fact that the least square approximation of a given signal over a chosen domain D can be directly obtained from the corresponding optimal least square approximations of this signal over any set of domains that constitute a partition of D. The approximation characteristics and a parameter that takes into account of the relative position and geometry of these domains are sufficient to provide the overall best approximation over D. This property is shown to be independent of the basis functions used in the approximation. It is also shown how the total least square error can be obtained from the least square errors that define a partition of D. The paper presents as well the computational efficiency of the algorithm. As an example, an applicaiton in the context of image segmentation is presented.