Convergence of an efficient local least-squares fitting method for bases with compact support

The least-squares projection procedure appears frequently in mathematics, science, and engineering. It possesses the well-known property that a least-squares approximation (formed via orthogonal projection) to a given data set provides an optimal fit in the chosen norm. The orthogonal projection of the data onto a finite basis is typically approached by the inversion of a Gram matrix involving the inner products of the basis functions. Even if the basis functions have compact support, so that the Gram matrix is sparse, its inverse will be dense. Thus computing the orthogonal projection is expensive. icient local least-squares algorithm for non-orthogonal projection onto smooth piecewise-polynomial basis functions is analyzed. The algorithm runs in optimal time and delivers the same order of accuracy as the standard orthogonal projection. Numerical results indicate that in many computational situations, the new algorithm offers an effective alternative to global least-squares approximation.