Nyström type subsampling analyzed as a regularized projection. (21st June 2017)

• Record Type: Journal Article
• Authors: Kriukova, Galyna; Pereverzyev, Sergiy; Tkachenko, Pavlo
• Is Part Of: Inverse problems. Volume 33:Number 7(2017:Jul.)
• Publication Date: 2017-06-21
• Subjects: Nyström subsampling -- big data -- linear functional strategy -- regularization -- source condition -- computational complexity; Inverse problems (Differential equations) -- Periodicals; 515.357
• DOI: 10.1088/1361-6420/33/7/074001
• Languages: English
• ISSNs: 0266-5611

Abstract

Abstract: In the statistical learning theory the Nyström type subsampling methods are considered as tools for dealing with big data. In this paper we consider Nyström 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 guaranteed for standard algorithms running with quadratic computational complexity can be obtained with subquadratic complexity by the Nyström 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.