Error analysis of regularized and unregularized least-squares regression on discretized function spaces

Abstract

In this thesis, we analyze a variant of the least-squares regression method which operates on subsets of finite-dimensional vector spaces.<br /> In the first part, we focus on a regression problem which is constrained to a ball of finite radius in the search space. We derive an upper bound on the overall error by coupling the ball radius to the resolution of the search space.<br /> In the second part, the corresponding penalized Lagrangian dual problem is considered to establish probabilistic results on the well-posedness of the underlying minimization problem. Furthermore, we have a look at the limit case, where the penalty term vanishes and we improve on our error estimates from the first part for the special case of noiseless function reconstruction.<br /> Subsequently, our theoretical foundation is used to obtain novel convergence results for regression algorithms based on sparse grids with linear splines and Fourier polynomial spaces on hyperbolic crosses. <br /> We conclude the thesis by giving several numerical examples and comparing the observed error behavior to our theoretical results.