How Many Landmarks Does a Nyström Kernel Machine Need? Schur-Complement Proofs, an Eigenvalue Lower Bound and Three Landmark Rules on 9,568 Power-Plant Records

Kernel ridge regression is accurate but needs memory and time that grow with the square and cube of the sample size. The Nystrom method replaces the kernel matrix by a low-rank approximation built from m landmark points. I prove three exact facts about it: the residual kernel matrix is a Schur complement and so is positive semidefinite, also when the landmarks are not data points; adding landmarks can only shrink the residual in the positive semidefinite order; and no Nystrom approximation of rank m can have a trace error below the sum of the kernel eigenvalues beyond the m-th. I then test three landmark rules (uniform sampling, greedy pivoted Cholesky and k-means centres) on the UCI Combined Cycle Power Plant data, with a Gaussian kernel on 7,000 training and 2,568 test records. Exact kernel ridge regression has a test error of 4.108 MW, against 4.690 MW for linear regression. K-means landmarks come closest to the eigenvalue bound, within a factor of 1.37 to 7.94, while uniform sampling falls to a factor of 59 at 400 landmarks. Greedy pivoting has a larger trace error than uniform sampling up to 100 landmarks but the lowest test error from 25 to 100 landmarks. With 200 landmarks all three rules are within 0.021 MW of the exact model, so trace error is a poor guide to predictive loss at small m.