Boosting Nyström Method
This work addresses the need for better matrix approximations in kernel-based learning, offering incremental improvements over existing methods.
The paper tackled the problem of improving low-rank approximations of large kernel matrices by proposing boosting Nyström algorithms, which iteratively generate and combine weak approximations adaptively, resulting in more efficient and accurate approximations compared to standard and ensemble Nyström methods, as demonstrated through simulation studies and real-world data analysis.
The Nyström method is an effective tool to generate low-rank approximations of large matrices, and it is particularly useful for kernel-based learning. To improve the standard Nyström approximation, ensemble Nyström algorithms compute a mixture of Nyström approximations which are generated independently based on column resampling. We propose a new family of algorithms, boosting Nyström, which iteratively generate multiple ``weak'' Nyström approximations (each using a small number of columns) in a sequence adaptively - each approximation aims to compensate for the weaknesses of its predecessor - and then combine them to form one strong approximation. We demonstrate that our boosting Nyström algorithms can yield more efficient and accurate low-rank approximations to kernel matrices. Improvements over the standard and ensemble Nyström methods are illustrated by simulation studies and real-world data analysis.