Approximate Vanishing Ideals

The vanishing ideal of a set of points is the collection of polynomials that evaluate to zero on every point in the set — a classical object in computer algebra that, in principle, gives an exact algebraic description of the data’s structure. Real data is noisy, though, so exact vanishing rarely holds; approximate vanishing ideal algorithms instead construct polynomials that vanish nearly, but not exactly, extracting nonlinear structure that can be used for feature extraction and classification.

This is a long-running line of work: from early genetic-programming and data-knotting approaches, through gradient-based and contrastive normalization schemes that make the constructed polynomials more discriminative and numerically well-behaved, to scaling these algorithms up and making them monomial-agnostic. It sits at the boundary between classical symbolic computation and the optimization tools of modern machine learning — a boundary we continue to explore alongside our newer Transformer-based approach to computational algebra.

Progress so far

We’ve worked on this problem since 2016, proposing methods to overcome the spurious vanishing problem, boost basis construction with gradient information, scale approximate vanishing ideal computation for large datasets (with Sebastian Pokutta’s group), and generalize the construction to be monomial-agnostic. This line continues with new gradient-weighted, data-driven normalization schemes for approximate border bases.