Monomial-agnostic computation of vanishing ideals

In recent years, the approximate basis computation of vanishing ideals has been studied extensively and adopted both in computer algebra and data-driven applications such as machine learning. However, symbolic computation and the dependency on monomial ordering remain as essential gaps between the two above-mentioned fields. In this paper, we propose the first efficient monomial-agnostic approximate basis computation of vanishing ideals, where polynomials are manipulated without any information of monomials; this can be implemented in a fully numerical manner and is thus desirable for data-driven applications. In particular, we propose gradient normalization, which achieves not only the first efficient and monomial-agnostic normalization of polynomials but also provides significant advantages such as consistency in translation and scaling of data points, which cannot be realized by existing basis computation algorithms. During the basis computation, the gradients of polynomials at the given points are proven to be efficiently and exactly obtained without performing differentiation. By exploiting the gradient information, we further propose a basis reduction method to remove redundant polynomials in a monomial-agnostic manner. Finally, we also propose a regularization method using gradients to avoiding overfitting of the basis for the given perturbed points.