Numerical Stability of the Nyström Method
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915644456304640 |
|---|---|
| author | Bucci, Alberto Nakatsukasa, Yuji Park, Taejun |
| author_facet | Bucci, Alberto Nakatsukasa, Yuji Park, Taejun |
| contents | The Nyström method is a widely used technique for improving the scalability of kernel-based algorithms, including kernel ridge regression, spectral clustering, and Gaussian processes. Despite its popularity, the numerical stability of the method has remained largely an unresolved problem. In particular, the pseudo-inversion of the submatrix involved in the Nyström method may pose stability issues as the submatrix is likely to be ill-conditioned, resulting in numerically poor approximation. In this work, we establish conditions under which the Nyström method is numerically stable. We show that stability can be achieved through an appropriate choice of column subsets and a careful implementation of the pseudoinverse. Our results and experiments provide theoretical justification and practical guidance for the stable application of the Nyström method in large-scale kernel computations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_15583 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Numerical Stability of the Nyström Method Bucci, Alberto Nakatsukasa, Yuji Park, Taejun Numerical Analysis 15A23, 65F55, 65G50 The Nyström method is a widely used technique for improving the scalability of kernel-based algorithms, including kernel ridge regression, spectral clustering, and Gaussian processes. Despite its popularity, the numerical stability of the method has remained largely an unresolved problem. In particular, the pseudo-inversion of the submatrix involved in the Nyström method may pose stability issues as the submatrix is likely to be ill-conditioned, resulting in numerically poor approximation. In this work, we establish conditions under which the Nyström method is numerically stable. We show that stability can be achieved through an appropriate choice of column subsets and a careful implementation of the pseudoinverse. Our results and experiments provide theoretical justification and practical guidance for the stable application of the Nyström method in large-scale kernel computations. |
| title | Numerical Stability of the Nyström Method |
| topic | Numerical Analysis 15A23, 65F55, 65G50 |
| url | https://arxiv.org/abs/2511.15583 |