Abstract: The following optimization problem arises in many applications, and we shall revisit it again and again throughout this book.
Introduction to the Euclidean Distance Problem
In fields ranging from computer vision to signal processing, a recurring challenge is finding the "best" representation of observed data within a specific mathematical model. Formally, this is often framed as the Euclidean Distance (ED) Problem: given a data point $u \in \mathbb{R}^n$ and a geometric shape $X$ (an algebraic variety), find a point $x \in X$ that minimizes the distance to $u$.
While standard numerical optimization techniques like gradient descent are commonly employed to find local minima, they lack a global perspective. They cannot determine how many other critical points—maxima, minima, or saddle points—exist for a given problem. This paper, based on the work in Metric Algebraic Geometry, provides a rigorous algebraic framework to count and locate all possible critical points, introducing the Euclidean Distance (ED) degree as a fundamental measure of an optimization problem's complexity.
The Euclidean Distance Degree
A central insight of this research is that for a "generic" (randomly chosen) data point $u$, the number of complex critical points of the distance function is constant. This number is the ED degree of the variety $X$. It serves as an intrinsic geometric property that quantifies the difficulty of solving the ED problem for that specific model.
As illustrated in Figure 2, the distribution and nature of these critical points can shift based on the location of the data point $u$. While the total number of complex solutions remains stable for generic points, the number of real solutions—those relevant to physical engineering problems—can vary.
Methodology: From Calculus to Algebra
To solve the ED problem globally, the authors translate the optimization task into a system of polynomial equations using several key techniques:
- Augmented Jacobian Matrix ($AJ$): Critical points are found by constructing a matrix that combines the constraints defining the variety (the Jacobian) with the gradient of the distance function. The solutions to the equations where this matrix has reduced rank correspond to the critical points.
- Saturation: Algebraic varieties often possess singularities, such as sharp corners or self-intersections, where standard calculus fails. The authors utilize an algebraic operation called saturation to "clean" the resulting equations, ensuring the solver focuses only on meaningful critical points and ignores artifacts created by singularities.
- Homotopy Continuation: For practical computation, the paper leverages numerical algebraic geometry. Using software like
HomotopyContinuation.jl, solutions are "tracked" from a simple, known system to the complex target system, allowing for the efficient discovery of all critical points.
Geometric Insights and Duality
One of the most elegant theoretical results presented is Theorem 2.23, which establishes a symmetry between a variety $X$ and its dual variety $Y$. The theorem states that the ED problem for $X$ is identical in complexity to the ED problem for its dual. This duality implies that if an optimization problem is difficult on a certain shape, it is equally difficult on that shape's "algebraic mirror."
Furthermore, the ED degree can be calculated using polar degrees, which are topological invariants. This moves the problem from a purely computational search to an understanding of the variety's underlying topology. For example, a general plane curve of degree $d$ is shown to have an ED degree of $d^2$, demonstrating that algebraic complexity often outpaces geometric degree.
Key Results and Computational Limits
The framework provides explicit formulas for various classes of varieties. For general space curves defined by the intersection of two surfaces of degrees $d_1$ and $d_2$, the ED degree is $d_1 d_2 (d_1 + d_2 - 1)$. In the case of low-rank matrix approximation (the Eckart-Young Theorem), the paper proves that all complex critical points are real, and the ED degree is a simple combinatorial value: $\binom{m}{r}$ for an $m \times m$ matrix of rank $r$.
As shown in the table above, modern software can reliably solve and certify systems with remarkably high ED degrees. The authors demonstrate that problems with nearly 50,000 critical points can be processed on standard consumer hardware, such as a MacBook Pro, in under 15 minutes.
Limitations and Future Directions
Despite its power, the ED degree approach has limitations. It primarily counts complex solutions, whereas engineering applications require real solutions. While the ED degree provides a global upper bound, it does not yet predict the exact number of real solutions for a specific data point. Additionally, the results often assume "genericity"; structured data with specific symmetries may fall into "special" cases where the number of critical points drops.
Future work involves extending this algebraic machinery to non-Euclidean distances, such as $p$-norms, which are increasingly relevant in modern data science but significantly increase the underlying algebraic complexity.
Summary updated