  The Nystrom method is a popular technique that uses a small number of
landmark points to compute a fixed-rank approximation of large kernel matrices
that arise in machine learning problems. In practice, to ensure high quality
approximations, the number of landmark points is chosen to be greater than the
target rank. However, for simplicity the standard Nystrom method uses a
sub-optimal procedure for rank reduction. In this paper, we examine the
drawbacks of the standard Nystrom method in terms of poor performance and lack
of theoretical guarantees. To address these issues, we present an efficient
modification for generating improved fixed-rank Nystrom approximations.
Theoretical analysis and numerical experiments are provided to demonstrate the
advantages of the modified method over the standard Nystrom method. Overall,
the aim of this paper is to convince researchers to use the modified method, as
it has nearly identical computational complexity, is easy to code, has greatly
improved accuracy in many cases, and is optimal in a sense that we make
precise.
