# Boosting Nystr"om Method

arXiv: https://arxiv.org/abs/2302.11032 · HTML: https://mlsanity.com/paper/2302.11032/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 49 references that are in the map.
- First posted on arXiv 21 Feb 2023.

## Builds on (most cited first, 11 of 11)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data](https://mlsanity.com/paper/1706.05736/) (2017)
- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (2013)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Fast DPP Sampling for Nystr"om with Application to Kernel Methods](https://mlsanity.com/paper/1603.06052/) (2016)
- [Matrix Coherence and the Nystrom Method](https://mlsanity.com/paper/1408.2044/) (2014)
- [Improved Fixed-Rank Nystr"om Approximation via QR Decomposition: Practical and Theoretical Aspects](https://mlsanity.com/paper/1708.03218/) (2017)

## Abstract (arXiv)

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.