The spectral norm error of the naive Nystrom extension

arXiv1110.5305MaRDI QIDQ6228564FDOQ6228564

Authors: Alex Gittens 

Publication date: 24 October 2011

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.

This page was built for publication: The spectral norm error of the naive Nystrom extension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6228564)