Random orthonormal embeddings are minimax optimal for sketched least squares, and rotation-invariant embeddings are minimax optimal for randomized SVD, with sharp error formulas.
The spectral norm error of the naive Nystrom extension
2 Pith papers cite this work, alongside 53 external citations. Polarity classification is still indexing.
2
Pith papers citing it
53
external citations · Pith
abstract
The naive Nystrom extension forms a low-rank approximation to a positive-semidefinite matrix by uniformly randomly sampling from its columns. This paper provides the first relative-error bound on the spectral norm error incurred in this process. This bound follows from a natural connection between the Nystrom extension and the column subset selection problem. The main tool is a matrix Chernoff bound for sampling without replacement.
fields
math.NA 2years
2026 2representative citing papers
Introduces Riemannian Nyström approximation via subspace projections and Haar-Grassmann sketching for tangent operators, plus a randomized Newton method, tested on SPD and Grassmann manifolds.
citing papers explorer
-
Sharp analysis of sketched least squares and randomized low-rank approximation
Random orthonormal embeddings are minimax optimal for sketched least squares, and rotation-invariant embeddings are minimax optimal for randomized SVD, with sharp error formulas.
-
Nystr\"om Approximation on Manifolds
Introduces Riemannian Nyström approximation via subspace projections and Haar-Grassmann sketching for tangent operators, plus a randomized Newton method, tested on SPD and Grassmann manifolds.