Nystrom type subsampling analyzed as a regularized projection
Pereverzyev, Sergei V.
In the statistical learning theory the Nystr¨om type subsampling methods are considered as tools for dealing with big data. In this paper we consider Nystr¨om subsampling as a special form of the projected Lavrentiev regularization, and study it using the approaches developed in the regularization theory. As a result, we prove that the same capacity independent learning rates that are quaranteed for standard algorithms running with quadratic computational complexity can be obtained with subquadratic complexity by the Nystr¨om subsampling approach, provided that the subsampling size is chosen properly. We propose a priori rule for choosing the subsampling size and a posteriori strategy for dealing with uncertainty in the choice of it. The theoretical results are illustrated by numerical experiments.
Kriukova Galyna. Nystrom type subsampling analyzed as a regularized projection / Galyna Kriukova, Sergiy Pereverzyev, Pavlo Tkachenko // Applied Mathematics. - 2016. - Nr. 22, January. - 19 p.