# Border basis computation with gradient-weighted normalization

arXiv: https://arxiv.org/abs/2101.00401 · HTML: https://mlsanity.com/paper/2101.00401/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 26 references that are in the map.
- First posted on arXiv 2 Jan 2021.

## Builds on (most cited first, 5 of 5)

- [Gradient Boosts the Approximate Vanishing Ideal](https://mlsanity.com/paper/1911.04174/) (2019)
- [Spurious Vanishing Problem in Approximate Vanishing Ideal](https://mlsanity.com/paper/1901.08798/) (2019)
- [Analytic Manifold Learning: Unifying and Evaluating Representations for Continuous Control](https://mlsanity.com/paper/2006.08718/) (2020)
- [Dual-to-kernel learning with ideals](https://mlsanity.com/paper/1402.0099/) (2014)
- [Approximate Vanishing Ideal via Data Knotting](https://mlsanity.com/paper/1801.09367/) (2018)

## Built on by (most cited first, 5 of 5)

- [Learning to Compute Gr"obner Bases](https://mlsanity.com/paper/2311.12904/) (2023)
- [Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms](https://mlsanity.com/paper/2505.23696/) (2025)
- [Approximate Vanishing Ideal Computations at Scale](https://mlsanity.com/paper/2207.01236/) (2022)
- [Evolving Architectures with Gradient Misalignment toward Low Adversarial Transferability](https://mlsanity.com/paper/2109.05919/) (2021)
- [Vanishing Component Analysis with Contrastive Normalization](https://mlsanity.com/paper/2210.16171/) (2022)

## Abstract (arXiv)

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.