A More Efficient and Practical Modified Nyström Method

Abstract

In this paper, we propose an efficient Nyström method with theoretical and empirical guarantees. In parallel computing environments and for sparse input kernel matrices, our algorithm can have computation efficiency comparable to the conventional Nyström method, theoretically. Additionally, we derive an important theoretical result with a compacter sketching matrix and faster speed, at the cost of some accuracy loss compared to the existing state-of-the-art results. Faster randomized SVD and more efficient adaptive sampling methods are also proposed, which have wide application in many machine-learning and data-mining tasks.

Keywords

• kernel method
• Nyström method
• low-rank approximation
• machine learning