  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 order of
magnitude of 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.
