The Reconstruction Approach: From Interpolation to Regression
This work addresses computational efficiency in nonparametric regression for large-scale data analysis, presenting an incremental improvement by reframing existing methods.
The paper tackles the computational burden of nonparametric regression by introducing the reconstruction approach, which uses interpolation to parameterize the regression function and estimates parameters via regularized least squares, reducing complexity from O(n^3) to more efficient surrogates suitable for large datasets.
This paper introduces an interpolation-based method, called the reconstruction approach, for nonparametric regression. Based on the fact that interpolation usually has negligible errors compared to statistical estimation, the reconstruction approach uses an interpolator to parameterize the regression function with its values at finite knots, and then estimates these values by (regularized) least squares. Some popular methods including kernel ridge regression can be viewed as its special cases. It is shown that, the reconstruction idea not only provides different angles to look into existing methods, but also produces new effective experimental design and estimation methods for nonparametric models. In particular, for some methods of complexity O(n3), where n is the sample size, this approach provides effective surrogates with much less computational burden. This point makes it very suitable for large datasets.