Paper Info
Title
Error bound of Nyström-approximated NCut eigenvectors and its application to training size selection.
Abstract
We provide a novel error bound for NCut Nystrom-approximated eigenvectors.Nystrom is found identical to matrix multiplication approximation.Use sum of singular values of a specific matrix to measure the error.Give the training size bound for a user-designed tolerance of error. We provide an error bound for the popular Nystrm-approximated eigenvectors of the Normalized Cuts (NCut) out-of-sample problem. We then extend our approach to determine the size of training set given a tolerance of approximation error. First, we show that the Nystrm-based eigenfunction approximation is identical to the eigensystem approximation of two matrices. We then proceed to study the expected error of matrix approximation. The lower bound on sum of squared singular values of a specific matrix is proposed. Such singular values have a strong relationship to the cosines of principal angles in matrix perturbation theory. The sum of squared singular values is therefore selected to measure the error of eigenvector approximations. From our analysis, we give the training size bound for a fixed approximation error, i.e., at most how many points are required in training set with a desired error in hand. Experiments on various datasets verify the performance of error bound analysis and training size determination.
Year
DOI
Venue
2017
10.1016/j.neucom.2017.02.011
Neurocomputing
Keywords
Field
DocType
Error bound,Singular values,Nyström approximation,Kernel matrix,Pattern recognition
Applied mathematics,Eigenfunction,Singular value,Upper and lower bounds,Round-off error,Matrix (mathematics),Artificial intelligence,Eigenvalues and eigenvectors,Combinatorics,Pattern recognition,Matrix multiplication,Approximation error,Mathematics
Journal
Volume
Issue
ISSN
239
C
0925-2312
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Li He1255.52
Ray Nilanjan254155.39
Hong Zhang358274.33