Border basis computation with gradient-weighted normalization
  Normalization of polynomials plays a vital role in the approximate basis
computation of vanishing ideals. Coefficient normalization, which normalizes a
polynomial with its coefficient norm, is the most common method in computer
algebra. This study proposes the gradient-weighted normalization method for the
approximate border basis computation of vanishing ideals, inspired by recent
developments in machine learning. The data-dependent nature of
gradient-weighted normalization leads to better stability against perturbation
and consistency in the scaling of input points, which cannot be attained by
coefficient normalization. Only a subtle change is needed to introduce gradient
normalization in the existing algorithms with coefficient normalization. The
analysis of algorithms still works with a small modification, and the time
complexity of algorithms remains unchanged. We also prove that, with
coefficient normalization, which does not provide the scaling consistency
property, scaling of points (e.g., as a preprocessing) can cause an approximate
basis computation to fail. This study is the first to theoretically highlight
the crucial effect of scaling in approximate basis computation and presents the
utility of data-dependent normalization.
