Despite prolific success, kernel methods become difficult to use in many large scale unsupervised problems because of the evaluation and storage of the full Gram matrix.

We overcome this difficulty by proposing a novel approach: computing the optimal out of sample dictionary using a nonlinear least-squares formulation, which allows for fast approximation of the Gram matrix via the Nystrom method.

We demonstrate and compare several methods for computing the optimal dictionary and show how this method outperforms previous state of the art out of sample and in sample methods with dictionaries of similar size.

We further show how this method can be modified to use in an online setting and explore a simple extension to make the method robust to outliers in the training data.