Source-linked AI summary
The Euclidean distance degree of an algebraic variety
Jan Draisma, Emil Horobet, Giorgio Ottaviani, Bernd Sturmfels, Rekha R. Thomas
TL;DR
Nearest-point problems on real algebraic varieties lack a systematic general treatment despite their applications. The paper develops Euclidean distance degree and related computational-algebraic tools for exact computation, including critical-point equations, ED correspondences, and geometric formulas. It shows that real critical-point counts depend on the data distribution and geometry, while special parametrizations or coordinates can reduce the resulting degree.
Problem
The paper addresses the absence of a systematic study of Euclidean-distance minimization on algebraic varieties in the generality needed for applications.
Method
The paper develops ED degree through polynomial critical-point equations, ED correspondences, algebraic-geometry formulas, and computational methods for application-relevant varieties.
Results
For the cardioid, EDdegree(X)=3 for general data, while its average ED degree can take any real value between 1 and 3 depending on data sampling.
Takeaways & Limitations
ED degree provides an algebraic-complexity measure and a framework for exact nearest-point computations across varieties studied in applications.
Takeaways & Limitations
For specific parametrizations, generic Bézout counts provide only upper bounds, and special coordinates can reduce ED degree.
Abstract
from arXiv · showhide
The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. For instance, for varieties of low rank matrices, the Eckart-Young Theorem states that this map is given by the singular value decomposition. This article develops a theory of such nearest point maps from the perspective of computational algebraic geometry. The Euclidean distance degree of a variety is the number of critical points of the squared distance to a generic point outside the variety. Focusing on varieties seen in applications, we present numerous tools for exact computations.
1 Introduction
The paper establishes Euclidean distance degree as an algebraic measure of nearest-point problems on real algebraic varieties and develops computational-algebraic tools for evaluating it. It also studies real critical-point counts, geometric discriminants, duality, projections, Chern classes, and application-specific formulas.
- Motivation: Polynomial models in science and engineering motivate minimizing squared Euclidean distance from data u to a real algebraic variety X.Under Gaussian noise, the nearest point is the maximum likelihood estimate.
- ED degree: The algebraic approach solves all complex critical points of the squared distance function on the nonsingular part of X.Lagrange multipliers characterize them by requiring u−x to be perpendicular to the tangent space at x.
- ED degree: EDdegree(X) is the constant number of such critical points for general data and measures the algebraic complexity of expressing the nearest point.The paper develops its basic properties and formulas using computational and classical algebraic geometry.
- Examples: 3 critical points occur for general data on the cardioid, so its ED degree is three.All three are real outside the evolute, which the paper calls the ED discriminant.
- Examples: Inside the cardioid’s evolute, two critical points become complex and the unique real critical point maximizes the squared distance.Thus, the number of real critical points varies across regions separated by the ED discriminant.
- Real critical points: The average ED degree aEDdegree(X) measures the expected number of real critical points and depends on the probability distribution of data.For the cardioid, it can be any real number between 1 and 3.
- Scope and contributions: The paper derives new ED-degree formulas and studies ED correspondences, duality, projections, intersections, ED discriminants, Chern classes, and applied varieties.Applications include control theory, geometric modeling, computer vision, low-rank matrix completion, and rank-one tensors.
- Scope and contributions: The paper addresses the lack of a systematic study of Euclidean nearest-point problems in the generality required for applications.Its stated aim is to lay foundations using algebraic geometry and computational algebra.
2 Equations defining critical points
This section formulates ED-degree computation through polynomial critical-point equations, handles affine and projective varieties, and gives implicit, parametric, and computational methods. It illustrates the framework with linear spaces, low-rank matrices, cones, toric surfaces, and bounds from Bézout-type arguments.
- Implicit equations: An implicit variety is analyzed by deriving polynomial equations for critical points of the squared distance function.The critical equations retain only regular points and remove contributions from the singular locus.
- Implicit equations: Lagrange multipliers impose that u−x is perpendicular to the tangent space of X at each regular critical point.The Jacobian matrix supplies the tangent-space constraints, with saturation removing singular-locus contributions.
- Implicit equations: For general u, the critical ideal is finite and consists precisely of critical points on the nonsingular manifold X\Xsing.Its cardinality defines EDdegree(X).
- Examples: Linear spaces have ED degree 1, with the unique critical point equal to the closest point in the real Euclidean problem.The equations reduce to x∈X and u−x⊥X.
- Examples: The Eckart-Young theorem identifies the closest rank-r matrix by truncating the singular value decomposition.All critical points arise by selecting r singular values, yielding the ED-degree formula described in the example.
- Examples: For a 2×2 rank-one matrix, Euclidean distance requires solving a quadratic equation, whereas maximum-likelihood estimation gives a rational rank-one solution.The Euclidean solution arises from the singular value decomposition.
- Computational implementation: Macaulay2 computes the ED degree of the Fermat quintic cone as 23 from its critical ideal.The computation constructs the Jacobian constraints and saturates by the singular locus.
- Bounds: For a codimension-c variety defined by ordered polynomial degrees, the section gives a general upper bound on ED degree, with equality for general complete intersections.The codimension assumption is essential for the stated bounds.
3 First applications
The section applies Euclidean distance degree to geometric modeling, computer vision, power systems, control theory, matrix approximation, and several structured varieties. These examples show how parametrizations, classical optimization results, and algebraic-geometric constructions yield exact ED-degree formulas or expose unresolved conjectures.
- Geometric modeling: Nearest-point problems for parametrized surfaces reduce to solving critical equations in the parameters, with resultants based on moving surfaces providing an algebraic method.For a birational surface map of bidegree (d1, d2), the relevant intersection number refines the Bézout bound.
- Structured matrix approximation: For symmetric rank-constrained matrices, different Euclidean formulations have dramatically different ED degrees, and the Eckart-Young formulation supplies the critical points through singular-value decomposition.The alternative parametrized formulation has a much larger ED degree; for s = 3 and r = 1 or 2, the section gives explicit comparisons.
- Computer vision: In multiview triangulation, maximum-likelihood recovery with Gaussian image noise is the nearest-point problem on an affine multiview variety.For two cameras, the variety is a hypersurface defined by a bilinear polynomial, while the general ED-degree formula is presented as a conjecture.
- Engineering and control: Power-system voltage-collapse detection and polynomial stability testing both become nearest-point problems to algebraic varieties or closures of stability loci.For Hurwitz determinants, the ED degree and average ED degree can be computed from homogeneous and non-homogeneous determinant constructions.
- Engineering and control: Hurwitz-determinant ED degrees oscillate with parity, whereas average ED degrees do not exhibit this oscillation.Theorem 3.6 gives formulas for the ED degrees of the Hurwitz determinants, and the accompanying table reports small cases.
- Distance geometry: For the Cayley-Menger variety, a linear coordinate change identifies the variety with a rank-one symmetric-matrix variety, enabling a Veronese-based ED-degree calculation.The calculation reduces to analyzing transversality with the isotropic quadric; when the parameter is divisible by 3, isolated nodes must be accounted for.
4 ED correspondence and average ED degree
The ED correspondence organizes critical points of squared distance as a variety over both the variety and data space, enabling algebraic and integral approaches to ordinary and average ED degree. Its projections, parametrizations, discriminants, and fiber structures support exact computation while imposing geometric conditions and numerical-integration considerations.
- ED correspondence: The ED correspondence EX is the closure of pairs (x, u) where x is a nonsingular critical point for the squared distance to u.Its first projection is an affine vector bundle of rank c over the smooth locus, while its total dimension is n.
- ED correspondence: Over general data points, the second projection has finite fibers whose cardinality equals EDdegree(X).For affine cones, the projective ED correspondence is an n-dimensional irreducible variety, and its projection over the variety has a vector-bundle structure away from singular and isotropic loci.
- Parametrization: Rational parametrizations of X induce rational parametrizations of EX, with birationality preserved between the two parametrizations.This converts tangent-space orthogonality conditions into parametrized representations suitable for computation.
- Average ED degree: The average ED degree averages the number of real critical points over data space using a chosen measure, and EX yields an integral formula for this quantity.For rationally parametrized varieties, numerical evaluation of the integral can be more efficient than sampling data and counting real critical points.
- Average ED degree: The ED discriminant is the algebraic hypersurface across whose complement the number of real critical points is constant on connected components.For the ellipse, the evolute is the ED discriminant; numerical integration gives average ED degree 3.04658... under the stated Gaussian measure.
- Average ED degree: If all complex critical points are real for every data point, then the average ED degree equals EDdegree(X) for any data-space measure.The rank-bounded matrix variety Xr is given as one instance of this property.
5 Duality
The section develops duality for Euclidean distance critical points: critical points on a variety correspond to those on its dual, preserving ED degree and average ED degree while reversing proximity. It connects this correspondence to conormal varieties, polar classes, Chern classes, toric formulas, and matrix examples.
- Critical-point duality: For general data u, x ↦ u − x bijects critical points of the squared distance on an irreducible cone X with those on its dual Y = X∗.For real u, the bijection preserves real critical points and therefore preserves the average ED degree.
- Critical-point duality: EDdegree(X) = EDdegree(Y), and the same duality gives aEDdegree(X, ω) = aEDdegree(Y, ω) for real data.The correspondence is proximity-reversing: closer critical points on one variety map to farther critical points on the other.
- Conormal geometry: The conormal variety encodes pairs (x, y) with y orthogonal to the tangent space at x, and its second projection defines the dual variety.Biduality makes the construction symmetric and supplies the reverse map needed for the bijection.
- Polar-class formula: Under the stated diagonal-disjointness condition, EDdegree(X) is the sum of polar classes and equals the reversed sum for the dual variety.The resulting identity is EDdegree(X) = δ0(X) + ··· + δn−2(X) = EDdegree(Y).
- Examples and scope: In special coordinates, the ED degree may drop to n, and for the corresponding toric example the average ED degree is the square root of 3n − 2.The section also illustrates duality for low-rank matrix varieties, where complementary-rank varieties have equal ED degree and SVD-indexed critical points.
6 Geometric Operations
This section studies how ED degree changes under projection, linear sections, homogenization, and translation. General projections often preserve ED degree, while sections and affine/projective changes obey formulas or inequalities governed by duality, polar classes, and behavior at infinity.
- Homogenization: Homogenization passes from an affine variety to its projective closure, but ED degree can increase or decrease under this operation.The section introduces homogenization through a new variable representing the hyperplane at infinity.
- Projection: For a general linear projection, ED degree is preserved when the variety has codimension at least two; hypersurfaces project to the full target space with ED degree 1.The preservation follows from equality of polar classes under projection.
- Projection: Projecting high-codimension varieties to dimension above their intrinsic dimension reduces ED-degree computations to lower-dimensional images, especially for smooth toric varieties.The projected variety retains the hypotheses needed for the sectional formulas.
- Linear sections: For a general hyperplane section, EDdegree(X ∩ H) equals EDdegree(X) minus degree(X∗) when X∗ is a hypersurface, and otherwise equals EDdegree(X).This follows from the polar-class shift δi(X ∩ H) = δi+1(X).
- Linear sections: A general hyperplane can change ED degree substantially in examples: for symmetric 3 × 3 rank varieties, one section has ED degree 13 while the dual-related section has ED degree 10.The unsectioned varieties X2 and X1 both have ED degree 13, but EDdegree(X1 ∩ H) = 10.
- Translation and limits: For affine translation by a general vector, EDdegree(X) ≤ EDdegree(Xv), with equality under smoothness conditions on the variety and its intersection at infinity.A second inequality is controlled by the conormal variety, reflecting possible loss of critical points under specialization.
7 ED discriminant and Chern Classes
The section develops the ED discriminant and Chern-class tools for computing Euclidean distance degrees, with formulas, examples, and computational constructions.
- ED discriminant: The ED discriminant is the locus of data points where critical points coincide, typically forming a hypersurface whose degree and defining polynomial can be studied.It is also the branch locus of the ED-correspondence map and consists of data with fewer than EDdegree(X) complex critical points.
- Examples and formulas: For a general plane curve of degree d, EDdegree(X) = d^2 and degree(ΣX) = 3d(d−1); for a general surface in P3, they are d(d^2−d+1) and 2d(d−1)(2d−1).For quadrics, the corresponding values are 6 and 12; a plane quartic has values 16 and 36.
- Examples and formulas: For determinantal varieties, the ED discriminant is the discriminant of the characteristic polynomial of UUt and is independent of the rank parameter r.For s = 2, it is reducible: two components when t ≥ 3 and four when t = 2.
- Duality and applications: The ED discriminant agrees for a variety and its dual variety, while the closest real point may be unique outside a hypersurface larger than ΣX.The uniqueness statement is given as an application-relevant scope boundary rather than as an identification with the ED discriminant.
- Chern-class formulas: Intersection-theoretic vector-bundle methods realize critical points as zeros of a section and compute their number from a top Chern class.Whitney’s sum formula and pullback properties support these calculations, especially for varieties of codimension at least two.
- Chern-class formulas: For smooth projective varieties meeting the isotropic quadric transversally, ED degree is computed through Chern classes.The paper gives two equivalent expressions and supplies an independent Chern-class proof of the main formula.
8 Tensors of Rank One
The section extends Euclidean distance degree from matrices to rank-one and partially symmetric tensors, using singular-vector equations, ED correspondences, and Chern-class formulas.
- Rank-one tensors: Rank-one tensors form the cone over a Segre variety, and their ED degree is given by a coefficient formula for arbitrary tensor formats.For matrices, the formula specializes to the Eckart-Young value EDdegree(X) = min(m1, m2).
- Singular-vector equations: Tensor critical points satisfy singular-vector equations whose proportionality conditions define quadratic equations and an ED correspondence.For p = 2, these equations reduce to the familiar singular-vector characterization for rectangular matrices.
- Examples: For the Segre variety P1 × P1 × P1, direct substitution verifies EDdegree(X) = 6, whereas a scaled embedding transverse to the isotropic quadric gives EDdegree(X) = 34.The two values correspond to the natural embedding and the rescaled embedding, respectively.
- Duality and approximation: If the dual variety is a hypersurface, the residual tensor u −u∗ lies on that dual variety, so the corresponding hyperdeterminant or A-discriminant vanishes.This gives the tensor statement that the residual of a best rank-one approximation satisfies a dual-variety equation.
- Partially symmetric tensors: For partially symmetric tensors, the Segre-Veronese ED degree is also given by a coefficient formula; an example with embedding O(3, 2) has ED degree 27.The result includes the Veronese case as a specialization.
- Average ED degree: Under the Gaussian distribution, the average ED degree of the Segre variety reduces to an expected absolute determinant of a random matrix.This replaces sampling in the full tensor space with determinant computations on smaller random matrices, although no closed form is expected for the determinant expectation.
Epilogue
The epilogue orders simple planar curves by Euclidean distance degree, from lines through general conics.
- Epilogue: The line, circle, parabola, and general conics have ED degrees 1, 2, 3, and 4, respectively.These examples are presented as an increasing sequence of planar curve complexity.