Title :
A novel adaptive Nyström approximation
Author :
Sheng, Lingyan ; Ortega, Antonio
Author_Institution :
Dept. of Electr. Eng., Univ. of Southern California, Los Angeles, CA, USA
Abstract :
We propose a novel perspective on the Nyström approximation method. Sampling the columns of the kernel matrix can be interpreted as projecting the data onto the subspace spanned by the corresponding columns. Thus, the quality of Nyström approximation can be quantified by the distance between the subspace spanned by the sampled columns and the subspace spanned by the data mapped to the eigenvectors corresponding to the top eigenvalues of the kernel matrix. Based on this interpretation, we design a novel adaptive Nyström approximation algorithm, BoostNyström. BoostNyström is efficient in terms of both time and space complexity. Experiments on benchmark data sets show that BoostNyström is more effective than the state-of-art algorithms.
Keywords :
approximation theory; eigenvalues and eigenfunctions; matrix algebra; BoostNyström; adaptive Nystrom approximation; eigenvalue; eigenvector; kernel matrix; space complexity; time complexity; Approximation algorithms; Approximation error; Complexity theory; Eigenvalues and eigenfunctions; Kernel; Standards; Ensemble; Kernel Method; Nyström Approximation; Projection;
Conference_Titel :
Machine Learning for Signal Processing (MLSP), 2012 IEEE International Workshop on
Conference_Location :
Santander
Print_ISBN :
978-1-4673-1024-6
Electronic_ISBN :
1551-2541
DOI :
10.1109/MLSP.2012.6349777