We develop two approaches for analyzing the approximation error bound for the Nyström method that approximates a positive semidefinite (PSD) matrix by sampling a small set of columns, one based on a concentration inequality for integral operators, and one based on random matrix theory. We show that the approximation error, measured in the spectral norm, can be improved from to in the case of large eigengap, where is the total number of data points, is the number of sampled data points, and is a positive constant that characterizes the eigengap. When the eigenvalues of the kernel matrix follow a -power law, our analysis based on random matrix theory further improves the bound to under an incoherence assumption. We present a kernel classification approach based on the Nyström method and derive its generalization performance using the improved bound. We show that when the eigenvalues of the kernel matrix follow a -power law, we can reduce the number of support vectors to , which is sublinear in when , without seriously sacrificing its generalization performance.