Large-scale Nyström kernel matrix approximation using randomized SVD.

Area of Science:

• Numerical analysis
• Machine learning
• Data science

Background:

• The Nyström method is crucial for eigenvalue decomposition of large kernel matrices.
• Accurate Nyström approximations require substantial column sampling.
• Singular Value Decomposition (SVD) on large submatrices is computationally prohibitive.

Purpose of the Study:

• To develop an accurate and scalable Nyström scheme for large-scale eigenvalue decomposition.
• To reduce the computational complexity of the SVD step in the Nyström method.
• To leverage randomized algorithms for efficient matrix approximation.

Main Methods:

• Propose a Nyström scheme that samples a large column subset.
• Employ randomized low-rank matrix approximation for approximate SVD on the inner submatrix.
• Utilize multiprocessor and multi-GPU systems for distributed computation.

Main Results:

• The proposed algorithm achieves accuracy comparable to the standard Nyström method.
• The time complexity is reduced to that of a small SVD.
• Demonstrated encouraging results on large-scale datasets for low-rank approximation.
• Significant speedups achieved through parallel and distributed computing.

Conclusions:

• The randomized Nyström method offers an accurate and computationally efficient solution for large-scale eigenvalue problems.
• The approach is scalable and amenable to parallel and GPU acceleration.
• This method significantly enhances the feasibility of kernel matrix decomposition on massive datasets.