Title: Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects,
Abstract: The Nyström method is a popular technique for computing fixed-rank
approximations of large kernel matrices using a small number of landmark
points. In practice, to ensure high quality approximations, the number of
landmark points is chosen to be greater than the target rank. However, the
standard Nyström method uses a sub-optimal procedure for rank reduction
mainly due to its simplicity. In this paper, we highlight the drawbacks of
standard Nyström in terms of poor performance and lack of theoretical
guarantees. To address these issues, we present an efficient method for
generating improved fixed-rank Nyström approximations. Theoretical analysis
and numerical experiments are provided to demonstrate the advantages of the
modified method over the standard Nyström 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, and has greatly improved
accuracy in many cases.