Title: Gradient Boosts the Approximate Vanishing Ideal Show Chinese title

Title: 梯度提升近似消去理想

Abstract: In the last decade, the approximate vanishing ideal and its basis construction algorithms have been extensively studied in computer algebra and machine learning as a general model to reconstruct the algebraic variety on which noisy data approximately lie. In particular, the basis construction algorithms developed in machine learning are widely used in applications across many fields because of their monomial-order-free property; however, they lose many of the theoretical properties of computer-algebraic algorithms. In this paper, we propose general methods that equip monomial-order-free algorithms with several advantageous theoretical properties. Specifically, we exploit the gradient to (i) sidestep the spurious vanishing problem in polynomial time to remove symbolically trivial redundant bases, (ii) achieve consistent output with respect to the translation and scaling of input, and (iii) remove nontrivially redundant bases. The proposed methods work in a fully numerical manner, whereas existing algorithms require the awkward monomial order or exponentially costly (and mostly symbolic) computation to realize properties (i) and (iii). To our knowledge, property (ii) has not been achieved by any existing basis construction algorithm of the approximate vanishing ideal. Show Chinese abstract

Abstract: 在过去十年中，近似消去理想及其基构造算法在计算机代数和机器学习中被广泛研究，作为重建噪声数据大致位于其上的代数簇的一般模型。 特别是，机器学习中开发的基构造算法由于其无需单项式序的特性而在许多领域的应用中被广泛使用；然而，它们失去了计算机代数算法的许多理论性质。 在本文中，我们提出了通用方法，使无需单项式序的算法具备若干有利的理论性质。 具体而言，我们利用梯度来（i）在多项式时间内绕过虚假消去问题，以移除符号上平凡的冗余基，（ii）实现相对于输入平移和缩放的一致输出，并（iii）移除非平凡的冗余基。 所提出的方法完全以数值方式工作，而现有算法为了实现属性（i）和（iii），需要繁琐的单项式序或计算成本指数级高昂（且大多为符号计算）的计算。 据我们所知，属性（ii）尚未被任何现有的近似消去理想的基构造算法实现。