Monomial-agnostic computation of vanishing ideals
share
The approximate basis computation of vanishing ideals has recently been studied extensively and exploited in computer algebra and data-driven applications such as machine learning. However, symbolic computation and the dependency on monomial ordering remain essential gaps between the two fields. In this paper, we present the first fully numerical basis computation that efficiently works in a monomial-agnostic (i.e., monomial-ordering free) manner without suffering from the spurious vanishing problem, which is a fundamental problem in evaluating polynomials to construct bases. This is realized by a newly proposed data-dependent normalization, gradient normalization, of polynomials that normalizes a polynomial based on the magnitude of gradients. The data-dependent nature of gradient normalization brings various significant advantages: (i) it resolves the spurious vanishing problem without accessing the coefficients of terms, resulting in a drastically small basis; (ii) it provides the basis computation with a scaling consistency that ensures that input scaling does not lead to an essential change in the output; and (iii) it is provably robust against input perturbations, where the upper bound of error is determined only by the magnitude of the perturbations. Existing studies did not achieve any of these. As further applications of gradient information, we propose a monomial-agnostic basis reduction method to remove redundant polynomials and a regularization method to manage positive-dimensional ideals. We confirmed the effectiveness of (i)–(iii) through numerical experiments.
READ FULL TEXT