Numerical Stability of the Nyström Method
Alberto Bucci, Yuji Nakatsukasa, Taejun Park · 2025
Read Numerical Stability of the Nyström Method by Alberto Bucci, Yuji Nakatsukasa, Taejun Park (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-15583.txt.
Introduction
Alberto Bucci, Yuji Nakatsukasa, and Taejun Park settle when a popular shortcut for kernel methods is numerically safe. The Nyström method approximates a large kernel matrix from a small set of columns, helping methods like kernel ridge regression, spectral clustering, and Gaussian processes scale up. Its weak point is inverting that small submatrix, which is often badly conditioned and can wreck accuracy.
Bucci and co-authors give conditions under which the method stays stable. Good column choice and a careful way of computing the pseudoinverse are the key ingredients. Their theory is backed by experiments, giving users both justification and practical guidance for stable large-scale kernel work.
Catalog record
| CREATOR | Alberto Bucci, Yuji Nakatsukasa, Taejun Park |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-15583
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Numerical Stability of the Nyström Method Thanks: Submitted to the editors DATE. Alberto Bucci, Yuji Nakatsukasa, Taejun Park Abstract 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. keywords Nyström method, stability analysis, locally maximum-volume indices, maximum-volume indices, kernel methods Funding. AB is member of the INdAM Research Group GNCS and supported by the UK’s Engineering and Physical Sciences Research Council (EPSRC grant EP/Z533786/1), YN is supported by EPSRC grants EP/Y010086/1 and EP/Y030990/1. TP is supported by the RandESC project, funded by the Swiss Platform for Advanced Scientific Computing (PASC). † † runningheads: Numerical Stability of the Nyström Method / A. Bucci, Y. Nakatsukasa, T. Park MSC 15A23, 65F55, 65G50 1 Introduction Low-rank techniques play an important role in improving scalability of many algorithms. Matrices that are low-rank are ubiquitous across data science and computational sciences [ 45 ] . Among these techniques, the Nyström method [ 37 ] stands out as a key tool in machine learning [ 21 ] for enhancing scalability in applications such as kernel ridge regression [ 1 ] , kernel support vector machine [ 10 ] , spectral clustering [ 47 ] , Gaussian processes [ 48 , 31 ] , and manifold learning [ 43 ] . Beyond machine learning, the Nyström approximation also finds use in statistics [ 4 ] , signal processing [ 40 ] , and computational chemistry [ 20 ] . Given a symmetric positive semi-definite (SPSD) matrix A\in\mathbb{R}^{n\times n} , the Nyström method [ 48 , 37 , 21 ] constructs a rank- r approximation of A as: A\approx A_{N}:=AS(S^{T}AS)^{\dagger}S^{T}\!A, where S\in\mathbb{R}^{n\times r} is a column-sampling matrix that selects a subset of A ’s columns, that is, S is a column submatrix of the identity matrix I , and † denotes the Moore-Penrose pseudoinverse. The approximation depends on the pseudoinverse of the core matrix S^{T}AS , which is almost always ill-conditioned for matrices well-approximated by a low-rank matrix. This may result in reduced accuracy due to roundoff errors, particularly if the implementation is not carefully designed. While these issues are not always critical, they can degrade the quality of the approximation to the point where we lose all accuracy, making the approximation pointless. Algorithm 1 First implementation of Nyström’s method 1: Symmetric positive semidefinite matrix A\in\mathbb{R}^{n\times n} , a sketching matrix S\in\mathbb{R}^{n\times r} 2: B\in\mathbb{R}^{n\times r} such that A\approx BB^{T} 3: Compute C\leftarrow AS , W\leftarrow S^{T}\!C , 4: Compute Cholesky factor R^{T}R=W , 5: Solve B=C/R To investigate potential numerical issues, we examine the implementation of the Nyström method presented in Algorithm 1 . In exact arithmetic, the algorithm produces A_{N} exactly. However, in finite-precision arithmetic, roundoff errors may render the procedure numerically unstable. In particular, Step 2 of Algorithm 1 , which involves computing the pseudoinverse of W , is a potential source of instability when W is highly ill-conditioned, which is typically the case when A is well-approximated by a low-rank matrix. This motivates the need for an alternative algorithm and a numerically robust implementation of the Nyström method. To illustrate the issue, consider the matrix A=\diag(1,\gamma^{2},0) , where \gamma is on the order of machine precision. In exact arithmetic, selecting the first two columns of A yields the optimal Nyström approximation of A : \displaystyle\left\|{A-A_{N}}\right\| \displaystyle=\left\|{\begin{bmatrix}1&0&0\\ 0&\gamma^{2}&0\\ 0&0&0\end{bmatrix}-\begin{bmatrix}1&0\\ 0&\gamma^{2}\\ 0&0\end{bmatrix}\begin{bmatrix}1&0\\ 0&\gamma^{2}\end{bmatrix}^{\dagger}\begin{bmatrix}1&0&0\\ 0&\gamma^{2}&0\end{bmatrix}}\right\|=0. However, in Step 2 if we get a slightly perturbed Cholesky factor due to roundoff errors, we get \hat{R}=\begin{bmatrix}1&0\\ 0&\gamma+\tilde{\gamma}\end{bmatrix}, where \tilde{\gamma} is in the order of machine precision, instead of R=\diag(1,\gamma) in exact arithmetic. Note that \hat{R}^{T}\hat{R}=R^{T}R+\text{O}(\gamma^{2})=S^{T}\!AS+\text{O}(\gamma^{2}) , so \hat{R} is a good substitute for R , in particular it is a backward stable Cholesky factor of S^{T}AS . With \hat{R} we obtain \hat{B}=AS\hat{R}^{-1}=\begin{bmatrix}1&0\\ 0&\gamma^{2}\\ 0&0\end{bmatrix}\begin{bmatrix}1&0\\ 0&\gamma+\tilde{\gamma}\end{bmatrix}^{-1}=\begin{bmatrix}1&0\\ 0&\frac{\gamma^{2}}{\gamma+\tilde{\gamma}}\\ 0&0\end{bmatrix}. Let the computed Nyström approximation be \widehat{A}_{N}:=\hat{B}\hat{B}^{T} . Then we get \displaystyle\left\|{A-\widehat{A}_{N}}\right\|=\left\|{A-\hat{B}\hat{B}^{T}}\right\| \displaystyle=\left|\gamma^{2}-\frac{\gamma^{4}}{(\gamma+\tilde{\gamma})^{2}}\right|. Now set \tilde{\gamma}=-(1-\delta)\gamma for \delta\in(0,0.5) so that \tilde{\gamma}=\text{O}(\gamma) , then \left\|{A-\widehat{A}_{N}}\right\|=\gamma^{2}\left(\frac{1}{\delta^{2}}-1\right)=\text{O}\!\left(\frac{\gamma^{2}}{\delta^{2}}\right), making the Nyström error arbitrarily large as \delta\rightarrow 0 . Therefore, the Nyström approximation may give an extremely poor approximation if the pseudoinverse of the core matrix is not computed with care. Essentially, the issue arises from very small entries in the diagonal of the Cholesky factor, making the Nyström approximation arbitrarily large when solving C/R in line 3 of Algorithm 1 . This issue has also been raised in prior works; see Section 1.1 . In this work, we propose an alternative stabilization strategy based on \epsilon -truncation of the singular values of the core matrix, S^{T}\!AS . By discarding singular values below a prescribed tolerance \epsilon , this method ensures that the singular values of the core matrix remain sufficiently large before computing its pseudoinverse. We refer to this procedure as the stabilized Nyström method, formally defined as follows: A_{N}^{(\epsilon)}:=AS(S^{T}\!AS)_{\epsilon}^{\dagger}S^{T}\!A, where (S^{T}\!AS)_{\epsilon} denotes the truncated version of S^{T}\!AS , obtained by setting all singular values smaller than \epsilon to zero. This stabilized formulation is central to our subsequent analysis. In particular, we investigate its approximation accuracy and establish its numerical stability guarantees under a carefully designed implementation, as outlines in Algorithm 2 . Algorithm 2 presents our implementation of Nyström method, which differs fundamentally from Algorithm 1 in that it may produce a different output even in exact arithmetic. The main difference lies in Step 2 , where we replace the standard Cholesky factor with an \epsilon -truncated Cholesky factor. In this approach, the Cholesky process is terminated once the largest remaining diagonal element falls below the threshold \epsilon . In our implementation, this procedure is performed in MATLAB using the cholp function from the Matrix Computation Toolbox [ 26 ] . Similar to Algorithm 1 , Algorithm 2 provides the option to retain the large low-rank factor as a subset of columns of A by skipping Step 3 and outputting C and R_{\epsilon} as the low-rank factors. Algorithm 2 Stable implementation of Nyström’s method 1: Symmetric positive semidefinite matrix A\in\mathbb{R}^{n\times n} , a sketching matrix S\in\mathbb{R}^{n\times r} , truncation parameter \epsilon (recommendation: \epsilon=10u ) 2: B\in\mathbb{R}^{n\times r} such that A\approx BB^{T} 3: Compute C\leftarrow AS , W\leftarrow S^{T}\!AS , 4: Compute \epsilon -truncated Cholesky factor R_{\epsilon}^{T}R_{\epsilon}\leftarrow W where R_{\epsilon}\in\mathbb{R}^{\hat{r}\times r} with \hat{r}\leq r , 5: Compute B\leftarrow CR_{\epsilon}^{\dagger} via backward stable solve for the overdetermined system 1.1 Existing methods Prior works have investigated the potential numerical instability of the Nyström method when computing the pseudoinverse of the core matrix S^{T}\!AS . In particular, Tropp et al. [ 44 ] proposed introducing a small shift to the core matrix before computing its pseudoinverse; see Algorithm 3 in [ 44 ]