🔢 mathematics

Euclidean Distance Degrees in Macaulay2

This paper introduces *EuclideanDistanceDegree*, a Macaulay2 package that implements both symbolic and numerical methods for computing Euclidean Distance degrees, demonstrating its capabilities through various examples and an accompanying GitHub repository.

Original authors: William Huang, Jose Israel Rodriguez

Published 2026-07-16

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: William Huang, Jose Israel Rodriguez

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are standing in a vast, foggy field, trying to find the closest spot on a strange, winding path to a specific tree you're holding. In the world of mathematics, this path is called a "variety," and the tree is your "data point." The question of finding that closest spot isn't just about walking; it's about solving a complex puzzle where the path might twist, turn, or even loop back on itself in invisible, four-dimensional ways. This is the heart of algebraic optimization, a field where mathematicians use the rules of polynomials (equations with variables like $x$ and $y$ ) to figure out the best possible solutions to real-world problems.

But here's the tricky part: sometimes, there isn't just one closest spot. There might be several "local" closest spots, and the math needs to count how many of these critical points exist to understand how hard the puzzle is to solve. This count is called the Euclidean Distance (ED) degree. Think of the ED degree as a "complexity score" for a shape. If the score is low, the shape is easy to navigate; if it's high, the shape is a maze. Scientists and engineers need this score to know how much computing power they'll need to design better cameras, train smarter artificial intelligence, or model how molecules fit together. Until now, calculating this score for complicated shapes was like trying to count the grains of sand on a beach by hand—slow, error-prone, and often impossible.

This paper introduces a new digital tool called EuclideanDistanceDegree, a software package for a computer algebra system named Macaulay2. The authors, William Huang and Jose Israel Rodriguez, have built a toolbox that acts like a high-tech compass and a super-fast counter. Instead of manually crunching numbers, this package uses clever mathematical tricks to count the "closest spots" on any given shape, whether that shape is defined by a list of equations or a set of instructions for drawing it.

The package offers four different ways to do the counting, depending on how the shape is described. For simple shapes, it uses a "Minors Method," which is like checking every possible angle of a mirror to see where the reflection lands. For more complex, high-dimensional shapes, it switches to a "Left Kernel Method" and a "Homotopy Method." You can think of the Homotopy Method as a video game strategy: the computer starts with a simple, easy version of the puzzle, solves it, and then slowly morphs the game into the hard version, tracking the solutions as they move. This allows the software to handle shapes that would otherwise crash a normal computer.

The authors tested their tool on a variety of mathematical models, including "Dingdong surfaces" and "Daisy surfaces" (fancy names for specific polynomial shapes), and found that it could accurately calculate their complexity scores. For instance, they determined that a specific type of surface called the "Dingdong surface" has a complexity score of 5 for standard measurements and 9 for generic ones. They also applied the tool to polynomial neural networks (a type of artificial intelligence model) and multiview varieties (shapes used in computer vision to understand how cameras see the world). In these tests, the software successfully calculated that a specific neural network architecture has a complexity score of 13.

What makes this package special is its flexibility. It can work with "symbolic" math (exact, perfect numbers) and "numerical" math (approximate numbers that are good enough for engineering). It even includes a feature to simulate thousands of random scenarios to find an "average" complexity score, which helps researchers understand how these shapes behave in the real world. For example, when testing an ellipse (a stretched circle), the package simulated 100 random scenarios and found an average complexity score of roughly 3.41, which aligns with previous mathematical theories.

Ultimately, this paper doesn't just present a new number; it provides a new way to explore the landscape of algebraic shapes. By making these calculations faster and more accessible, the EuclideanDistanceDegree package allows researchers to better understand the hidden complexity of the models they use in science and engineering. It turns a daunting, abstract counting problem into a manageable task, opening the door for more efficient designs in everything from 3D reconstruction to machine learning. The authors suggest that while their tool is powerful, it relies on the underlying math being well-behaved (like a "complete intersection"), but for the vast majority of practical applications, it offers a reliable and efficient way to measure the difficulty of finding the nearest point in a mathematical world.

Technical Summary: Euclidean Distance Degrees in Macaulay2

Problem Statement
The Euclidean Distance (ED) degree is a fundamental invariant in algebraic optimization, measuring the complexity of nearest-point problems for real algebraic varieties. Specifically, for a generic data point $u \in \mathbb{R}^n$ and a variety $X \subseteq \mathbb{R}^n$ , the ED degree is defined as the number of nonsingular complex critical points of the squared Euclidean distance function $\|x - u\|^2$ (or a weighted variant $\|x - u\|_w^2$ ) restricted to $X$ . While many scientific and engineering models are expressed as polynomial systems, tools for computing ED degrees for arbitrary varieties have been limited. This paper addresses the need for a robust software implementation capable of computing these degrees using both symbolic and numerical algebraic geometry techniques.

Methodology
The authors introduce the EuclideanDistanceDegree package for the computer algebra system Macaulay2. The package implements four distinct algorithmic approaches to compute ED degrees, categorized by the nature of the input variety (implicit vs. parameterized) and the computational strategy (symbolic vs. numerical):

Minors Method (Symbolic):
- Approach: This method treats the variety $X$ as a complex variety defined by a prime ideal $I_X$ . It constructs an augmented Jacobian matrix $\hat{J}$ by appending a row vector derived from the weighted distance gradient to the standard Jacobian $J$ of the defining polynomials.
- Computation: The weighted critical ideal is computed via saturation: $C_{X,u,w} = (I_X + \text{minors}_{c+1}(\hat{J})) : I_{X_{sing}}^\infty$ .
- Output: The degree of this ideal yields the ED degree. This approach is implemented symbolically and can return the explicit equations of the critical ideal.
Left Kernel Method (Numerical/Complete Intersections):
- Approach: Designed for varieties of large codimension where the minors method is computationally prohibitive due to the saturation step and the explosion of minors. It utilizes Lagrange multipliers to solve the critical point equations directly.
- Computation: For a complete intersection defined by $f_1, \dots, f_k$ , the system $G(x, \lambda) = 0$ is formed, combining the defining polynomials with the Lagrange multiplier condition $\lambda_0(x-u) + \sum \lambda_i \nabla f_i = 0$ .
- Implementation: This system is solved numerically using the Bertini software package via homotopy continuation.
Homotopy Method (Numerical/Beyond Complete Intersections):
- Approach: An extension of the left kernel method suitable for varieties that are not complete intersections or for exploring parameterized weights.
- Computation: It employs a two-stage homotopy continuation process. First, a "start system" is solved using generic weights to establish an initial bound on the ED degree. Second, a parameter homotopy tracks these solutions to the target system (specific weights or data).
- Efficiency: This allows for the efficient computation of ED degrees for multiple weight or data configurations, as the initial stage need only be executed once.
Conormal Varieties Method (Parameterized):
- Approach: Targeted at varieties given by a parameterization $\phi: \mathbb{C}^d \to \mathbb{C}^n$ .
- Computation: It constructs an affine conormal variety by finding the kernel of the transposed Jacobian of the parameterization. The critical points are identified as pairs $(x, \lambda)$ satisfying a specific linear system involving the parameterization and the kernel generators.
- Implementation: This can be computed symbolically or numerically using the MonodromySolver package.

Key Contributions

Software Package: The primary contribution is the EuclideanDistanceDegree Macaulay2 package, which unifies symbolic and numerical methods for ED degree computation.
Algorithmic Diversity: The package provides implementations for four distinct methods (Minors, Left Kernel, Homotopy, Conormal), allowing users to select the most appropriate tool based on the variety's structure (e.g., codimension, implicit vs. parameterized) and the desired output (exact symbolic degree vs. numerical approximation).
Interoperability: The symbolic methods include an option to return the generating polynomials of the critical ideal, facilitating replication and cross-validation with other software such as HomotopyContinuation.jl.
Numerical Robustness: The package integrates with Bertini and MonodromySolver, offering configuration options to handle path failures (e.g., paths diverging to infinity) and supporting both unit, weighted, and generic ED degree calculations.

Results and Examples
The paper validates the package through a range of examples:

Symbolic Verification: The package successfully computes the unit ED degree (5) and generic ED degree (9) for the Dingdong surface, recovering the critical ideal equations.
Numerical Computation: It computes the weighted ED degree (22) for the Daisy surface using specific data and weights.
Homotopy Efficiency: The package demonstrates that after computing a unit ED degree, subsequent generic ED degrees can be computed efficiently by reusing the initial homotopy stage. An experiment on an ellipse yields an average real ED degree of approximately 3.41 over 100 samples, consistent with theoretical expectations.
Applications:
- Polynomial Neural Networks: The package computes the generic ED degree for shallow polynomial neural networks (e.g., degree 13 for specific architectures), following prior work on neurovarieties.
- Multiview Varieties: It computes ED degrees for affine multiview varieties anchored at rational surfaces, finding degrees of 8 and 12 for specific configurations, providing empirical evidence for potential generalizations of known results for rational curves.

Significance
The paper positions the EuclideanDistanceDegree package as a specialized tool that fills a gap in the computational algebraic geometry landscape. While general symbolic packages (like AlgebraicOptimization or ToricInvariants) exist for specific settings, and general homotopy solvers (like Bertini or PHCpack) exist for numerical solving, this package offers a dedicated, user-friendly interface specifically for ED degrees. It bridges the gap between symbolic exactness and numerical scalability, enabling researchers in algebraic optimization, computer vision, and machine learning to better understand the algebraic complexity of their models by computing these critical invariants. The authors note that while no dedicated numerical ED package existed previously, their tool leverages existing robust solvers to provide a streamlined workflow for these specific problems.

Technical Summary: Euclidean Distance Degrees in Macaulay2

More like this