The spectral norm error of the naive Nystrom extension
By Alex Gittens. 2011
79 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Michael W. Mahoney
- Alex Gittens
- David P. Woodruff
- Shusen Wang
- Alessandro Rudi
- Lorenzo Rosasco
- A. Alaoui
- Farbod Roosta-Khorasani
In Computational Mechanics
- Michael W. Mahoney
- Alex Gittens
- David P. Woodruff
- A. Alaoui
- Shusen Wang
- Alessandro Rudi
- Lorenzo Rosasco
- Francis R. Bach
In Statistics and Probability
- Michael W. Mahoney
- Alex Gittens
- A. Alaoui
- Petros Drineas
- Tamás Sarlós
- David P. Woodruff
- Lorenzo Rosasco
- Alessandro Rudi
Citations in the corpus
- Revisiting the Nystrom Method for Improved Large-scale Machine Learning (2013, methodology): “As with previous bounds for uniform sampling, (e.g., Kumar et al., 2012; Gittens, 2012), these results for uniform sampling are much weaker than our bounds from the previous subsections, since the sampling complexity depends on the coherence of the input matrix.”
- Improved Bounds for the Nyström Method With Application to Kernel Classification (2011, unknown): “For the relative error bound given in (Gittens, 2011), the approximation error is dominated by O ( N 2 /m p +1 ) for eigenvalues following a p -power law.”