Boosting Nystr"om Method

The Nystr"om 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"om approximation, ensemble Nystr"om algorithms compute a mixture of Nystr"om approximations which are generated independently based on column resampling. We propose a new family of algorithms, boosting Nystr"om, which iteratively generate multiple ``weak'' Nystr"om 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"om algorithms can yield more efficient and accurate low-rank approximations to kernel matrices. Improvements over the standard and ensemble Nystr"om methods are illustrated by simulation studies and real-world data analysis.