Polynomial approximation of noisy functions (Q6926533)

As known, the generic algorithm for the least-squares problem requires \(O(N n^2)\) operations, where \(N+1\) is the number of sample points and \(n\) is the degree of the polynomial approximant. The authors propose an \(O(N \log N)\) method for polynomial approximation of a univariate noisy function. The method is based on truncating the Chebyshev interpolant at an appropriate degree and corresponds to solving a weighted least-squares problem. Blending numerical analysis and statistics, the convergence of the method is also examined. The convergence is spectral until the error reaches \(O(\sigma \sqrt{n/N})\), where \(\sigma\) is the noise level, after which the error continues to decrease at the Monte-Carlo \(O(1/\sqrt{N})\) rate. The Mallows' \(C_p\) statistical tool is used to determine the polynomial degree without prior knowledge of the noise level \(\sigma\).\N\NThe method, called NoisyChebtrunc combines the computational efficiency with \(O(N \log N)\) operations, the stability inherent in Chebyshev interpolation, leading to \(L_{\infty}\) convergence results with high probability and the Monte-Carlo style noise reduction as more samples are taken.\N\NThe efficiency of NoisyChebtrunc is illustrated with numerical experiments.