Clustered Nyström method for large scale manifold learning and dimension reduction.

Area of Science:

• Machine Learning
• Computational Mathematics
• Data Science

Background:

• Kernel matrices are crucial for many machine learning algorithms.
• Large-scale problems are computationally infeasible due to the cost of kernel matrix storage and manipulation.
• The Nyström method offers a sampling-based low-rank approximation to reduce computational burdens.

Purpose of the Study:

• To analyze the impact of landmark point selection on Nyström method approximation quality.
• To develop a more efficient and accurate Nyström method for large-scale kernel matrix approximation.
• To provide theoretical justification for using clustered landmark points.

Main Methods:

• Developed a non-probabilistic error analysis for the Nyström method.
• Proposed a "clustered Nyström method" utilizing k-means clustering centers as landmark points.
• Applied the method to algorithms requiring kernel matrix eigenvalue decomposition or inversion.

Main Results:

• Demonstrated that the choice of landmark points significantly affects Nyström approximation quality.
• The clustered Nyström method shows competitive performance in both accuracy and efficiency.
• The method effectively scales algorithms like kernel PCA, spectral clustering, and support vector machines.

Conclusions:

• The clustered Nyström method provides an effective strategy for handling large kernel matrices.
• K-means clustering centers are suitable landmark points for improving Nyström approximation.
• This approach enhances the scalability of various kernel-based machine learning algorithms.