How to evaluate Nystrom approximation method?

Question

I want to evaluate the Nystrom approximation method for large matrices and as mentioned in the paper, this can be done by calculating the Schur complement but is too computationally expensive for large datasets. I am using the method perform spectral clustering, so i was thinking that it may be possible to evaluate the performance of it by finding the distance of the centroids (after k-means clustering of my embedding vectors) and my embedding vectors in order to see the how the Nystrom method performs for different choices of subset size (A matrix).