Performance analysis of an algorithm from computational algebra for implicit regression

Recently new class of algorithms has been developed that construct polynomials that almost vanish at a finite number of d-dimensional points D. Such polynomials can be interpreted in terms of implicit regression models of the form f(x1,..., xd) = 0, where in the regression equation there is no distinction between dependent and independent factors. One such algorithm based on two steps is considered. In Step 1 it returns a polynomial f which almost vanishes at D and is based on a version of the Buchberger-Möller algorithm from Computational Commutative Algebra. In Step 2 by Newton’s method it modifies the coefficients of f to obtain f1 so that each point in D is near to a zero of f1 within a fixed tolerance. An estimate of the goodness of this approximation of D by the zeros of f1 is based on Kantorovich theorem on the convergence of Newton’s method. An auxiliary set of points D1 needs to be computed, of which we shall give an interpretation. An evaluation and performance study of this algorithm is presented on a number of datasets with different characteristics and performance indices are discusses/introduced.