  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.
