The Randomized SVD (RSVD) and improvements require multiple passes over . In some cases, it may be advantageous to use a method that only requires a single pass over .
Nyström for positive definite matrices¶
When is symmetric positive semi-definite, we can use the Nyström approximation generated by a sketching matrix .
When is a Gaussian sketching matrix, this method satisfies similar theoretical guarantees to the Randomized SVD (with respect to ), despite requiring half the number of matrix-vector products and only one pass over the data; see e.g. Corollary 8.2 in Tropp & Webber, 2023.
Block Krylov methods¶
In fact, at the cost of more passes over the data, we can replace with a basis for a Krylov subspace. As noted in Lemma 5.2 in Tropp & Webber, 2023 (below), the Nyström method always produces a low-rank approximation that is at least as good one-sided projection based methods Randomized Block Krylov Iteration.
Generalized Nyström for arbitrary matrices¶
A similar approach can be used for arbitrary . Given sketching matrices and , the Generalized Nyström approximation is the approximation
We can understand the Generalized Nyström method as approximating the adaptive step in the Randomized SVD. Indeed, note that the matrix computed by the Randomized SVD is the matrix of coefficients for the linear combination of the columns of that best approximates the columns of . That is,
Consider instead the sketched regression problem
This results in an approximation
The above procedure is summarized by the following algorithm.
Sketching dimension¶
To obtain a approximation in the Frobenius norm (similar to Theorem 5.1 for the RSVD), its not too hard to show that we must solve the regression problem (5.14) to relative accuracy . Based on the analysis on sketch-and-solve, this requires that the sketching matrix have roughly times the number of columns as .
This is in contrast to the approximation (5.11) for positive semi-definite case, which works with the same sketching dimension as the Randomized SVD.
- Tropp, J. A., & Webber, R. J. (2023). Randomized algorithms for low-rank matrix approximation: Design, analysis, and applications. https://arxiv.org/abs/2306.12418