Learning Guarantees for Approximate Vanishing Ideal Computations

The approximate vanishing ideal of a set of points $X\subseteq {\text{R}}^n$ is the set of polynomials that approximately evaluate to $0$ over all points $\mathbf{\text{x}}\in X$ and admits an efficient representation by a finite set of polynomials called generators. The constructed generators capture polynomial structures in data and give rise to a feature map that can, for example, be used in combination with a linear classifier for supervised learning. Generator-constructing algorithms are widely studied, but their computational complexities remain expensive and the methods lack learning guarantees. We introduce a generator-constructing algorithm that admits several learning guarantees and whose computational complexity is linear in the number of samples.