Error bound of Nyström-approximated NCut eigenvectors and its application to training size selection

We provide an error bound for the popular Nyström-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 Nyström-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.