A Perturbation-Based Kernel Approximation Framework
This work addresses scalability issues in kernel methods for data analysis, offering incremental improvements over existing approximation techniques.
The authors tackled the computational inefficiency of kernel methods for large datasets by developing a perturbation-based kernel approximation framework, which generalizes the Nyström method and introduces new tunable schemes, supported by theoretical error analysis and numerical demonstrations on synthetic and real-world data.
Kernel methods are powerful tools in various data analysis tasks. Yet, in many cases, their time and space complexity render them impractical for large datasets. Various kernel approximation methods were proposed to overcome this issue, with the most prominent method being the Nystr{ö}m method. In this paper, we derive a perturbation-based kernel approximation framework building upon results from classical perturbation theory. We provide an error analysis for this framework, and prove that in fact, it generalizes the Nystr{ö}m method and several of its variants. Furthermore, we show that our framework gives rise to new kernel approximation schemes, that can be tuned to take advantage of the structure of the approximated kernel matrix. We support our theoretical results numerically and demonstrate the advantages of our approximation framework on both synthetic and real-world data.