We describe and analyze an efficient procedure that constructs a set of generators of a vanishing ideal. The resulting polynomials capture nonlinear structure in data, and can for example be used within supervised learning. Empirical comparison with kernel methods show that our method constructs more compact classifiers with comparable accuracy.