Spectral methods in machine learning and new strategies for very large datasets

Area of Science:

• Statistics and Machine Learning
• Data Science
• Computational Mathematics

Background:

• Spectral methods are foundational in statistics and machine learning, underpinning algorithms from Principal Component Analysis (PCA) to manifold learning.
• A key challenge is computing low-rank approximations of positive-definite kernels, essential for many algorithms.
• Exact spectral decomposition is computationally prohibitive for very large or high-dimensional datasets due to cubic scaling complexity.

Purpose of the Study:

• To develop novel, efficient algorithms for approximating positive-semidefinite kernels applicable to massive datasets.
• To provide improved error bounds compared to existing literature for kernel approximation.
• To address the computational limitations of exact spectral decomposition in big data scenarios.

Main Methods:

• Introduced two new algorithms based on the Nyström method for efficient kernel approximation.
• Developed a randomized algorithm using kernel-induced probability distributions on data partitions (sampling-based).
• Developed a deterministic algorithm for data partition selection based on sorting.

Main Results:

• Presented two new strategies for approximating positive-semidefinite kernels that are scalable to massive datasets.
• Achieved error bounds that surpass existing results in the literature.
• Demonstrated improved performance over existing methods through simulations on various statistical data analysis problems.

Conclusions:

• The proposed Nyström-based algorithms provide efficient and accurate solutions for kernel approximation in large-scale machine learning.
• These methods effectively reduce computational complexity, making spectral analysis feasible for big data.
• The sampling and sorting strategies offer flexible and powerful tools for modern data analysis challenges.