🔢 mathematics

Euclidean Distance Degrees in Macaulay2

本文介绍了 EuclideanDistanceDegree，这是一个实现了用于计算欧几里得距离次数（Euclidean Distance degrees）的符号与数值方法的 Macaulay2 软件包，并通过各种示例及配套的 GitHub 仓库展示了其功能。

原作者： William Huang, Jose Israel Rodriguez

发布于 2026-07-16

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： William Huang, Jose Israel Rodriguez

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正站在一片广袤、多雾的田野中，试图在一条奇特的蜿蜒小径上，找到离你手中那棵树最近的一个点。在数学的世界里，这条路径被称为“代数簇”（variety），而那棵树就是你的“数据点”。寻找最近位置的问题不仅仅是关于行走；它更像是在解一个复杂的谜题，因为路径可能会以看不见的四维方式扭曲、转向或回环。这正是代数优化（algebraic optimization）的核心——在这个领域，数学家利用多项式（含有变量如 $x$ 和 $y$ 的方程）的规则来解决现实世界中的最优解问题。

但棘手之处在于，有时并不存在唯一的最近点。可能存在多个“局部”最近点，而数学需要计算出这些临界点（critical points）存在的数量，以了解这个谜题的求解难度。这个计数被称为欧几里得距离（ED）次数（Euclidean Distance (ED) degree）。你可以将 ED 次数理解为一种形状的“复杂度评分”。如果评分较低，说明该形状易于导航；如果评分较高，则意味着它是一个迷宫。科学家和工程师需要这个评分，来了解设计更好的相机、训练更聪明的人工智能或模拟分子如何相互契合时需要多少计算能力。直到目前为止，计算复杂形状的这一评分就像是用手去数沙滩上的沙粒一样——缓慢、易错，且往往难以实现。

本文介绍了一个名为 EuclideanDistanceDegree 的新数字工具，这是一个针对名为 Macaulay2 的计算机代数系统开发的软件包。作者 William Huang 和 Jose Israel Rodriguez 构建了一个工具箱，它扮演着高科技指南针和超快速计数器的角色。该软件包不再通过手动计算数值，而是利用巧妙的数学技巧，来计算任何给定形状上的“最近点”数量，无论该形状是由一组方程定义的，还是由一套绘图指令定义的。

该软件包提供了四种不同的计数方式，具体取决于形状是如何描述的。对于简单的形状，它使用“子式法”（Minors Method），这就像是检查镜子的每一个可能角度，看反射落在哪里。对于更复杂、高维的形状，它会切换到“左核方法”（Left Kernel Method）和“同伦方法”（Homotopy Method）。你可以将同伦方法想象成一种视频游戏策略：计算机从一个简单、容易的版本开始，解决它，然后慢慢地将游戏演变为困难版本，并追踪解随之移动的过程。这使得软件能够处理那些原本会导致普通计算机崩溃的形状。

作者在多种数学模型上测试了他们的工具，包括“丁东表面”（Dingdong surfaces）和“雏菊表面”（Daisy surfaces）（这些是特定多项式形状的华丽名称），并发现该工具能够准确计算它们的复杂度评分。例如，他们确定了特定类型的表面——“丁东表面”，在标准度量下复杂度评分为 5，而在泛型情况下为 9。他们还将该工具应用于多项式神经网络（一种人工智能模型）和多视图簇（用于计算机视觉理解相机如何观察世界的形状）。在这些测试中，软件成功计算出特定的神经网络架构具有 13 的复杂度评分。

这个软件包的特别之处在于其灵活性。它可以处理“符号”数学（精确、完美的数字）和“数值”数学（对工程学而言足够好的近似数字）。它甚至包含了一个模拟数千种随机场景的功能，以找到“平均”复杂度评分，这有助于研究人员理解这些形状在现实世界中的行为。例如，在测试椭圆（一种拉伸的圆）时，该软件包模拟了 100 个随机场景，并发现平均复杂度评分约为 3.41，这与之前的数学理论相吻合。

最终，这篇论文不仅提出了一个新的数字，它还提供了一种探索代数形状景观的新方法。通过使这些计算变得更快、更易获取，EuclideanDistanceDegree 软件包让研究人员能够更好地理解他们在科学和工程中所使用的模型的隐藏复杂度。它将一个令人生畏、抽象的计数问题变成了一项可控的任务，为从 3D 重建到机器学习等领域的更高效设计开启了大门。作者指出，虽然他们的工具功能强大，但它依赖于底层数学是“良好行为”的（例如“完全交集”），但对于绝大多数实际应用而言，它提供了一种可靠且高效的方法，来衡量在数学世界中寻找最近点的难度。

技术摘要：Macaulay2 中的欧几里得距离度 (Euclidean Distance Degree)

问题陈述
欧几里得距离（ED）度是代数优化中的一个基本不变量，衡量了最近点问题的复杂度。具体而言，对于给定的泛型数据点 $u \in \mathbb{R}^n$ 和簇 $X \subseteq \mathbb{R}^n$ ，ED 度被定义为平方欧几里得距离函数 $\|x - u\|^2$ （或其加权变体 $\|x - u\|_w^2$ ）在 $X$ 上限制后的非奇异复临界点的数量。虽然许多科学和工程模型可以用多项式系统来表达，但能够计算任意簇的 ED 度的鲁棒软件工具一直非常有限。本文旨在开发一种能够结合符号和数值代数几何技术来计算这些度的鲁棒软件实现。

方法论
作者为计算机代数系统 Macaulay2 引入了 EuclideanDistanceDegree 软件包。该包实现了四种不同的算法方法来计算 ED 度，这些方法根据输入簇的性质（隐式或参数化）以及计算策略（符号或数值）进行分类：

小因子法 (Minors Method - 符号法)：
- 方法： 该方法将簇 $X$ 视为由素理想 $I_X$ 定义的复簇。它通过在标准 Jacobian 矩阵 $J$ 中附加一个由加权距离梯度导出的行向量，构造出一个增广 Jacobian 矩阵 $\hat{J}$ 。
- 计算： 通过饱和运算计算加权临界理想： $C_{X,u,w} = (I_X + \text{minors}_{c+1}(\hat{J})) : I_{X_{sing}}^\infty$ 。
- 输出： 该理想的次数即为 ED 度。此方法以符号方式实现，并可以返回临界理想的显式方程。
左核法 (Left Kernel Method - 数值法/完全交集)：
- 方法： 专为具有较大余维数的簇设计，因为在这些情况下，由于饱和步骤和小因子爆炸，小因子法在计算上是难以承受的。它利用拉格朗日乘子来直接求解临界点方程。
- 计算： 对于由 $f_1, \dots, f_k$ 定义的完全交集，构造系统 $G(x, \lambda) = 0$ ，该系统结合了定义多项式与拉格朗日乘子条件 $\lambda_0(x-u) + \sum \lambda_i \nabla f_i = 0$ 。
- 实现： 该系统通过 Bertini 软件包利用同伦延续法进行数值求解。
同伦法 (Homotopy Method - 数值法/超越完全交集)：
- 方法： 左核法的扩展，适用于非完全交集的簇或用于探索参数化权重。
- 计算： 它采用两阶段同伦延续过程。首先，使用泛型权重求解一个“起始系统”，以建立 ED 度的初始界限。其次，利用参数同伦将这些解追踪到目标系统（特定的权重或数据）。
- 效率： 这使得为多个权重或数据配置高效计算 ED 度成为可能，因为初始阶段只需执行一次。
共形簇法 (Conormal Varieties Method - 参数化)：
- 方法： 针对由参数化 $\phi: \mathbb{C}^d \to \mathbb{C}^n$ 给出的簇。
- 计算： 通过寻找参数化转置 Jacobian 的核来构造仿射共形簇。临界点被识别为满足涉及参数化和核生成元的特定线性系统的对 $(x, \lambda)$ 。
- 实现： 这可以通过符号方式或使用 MonodromySolver 包进行数值计算。

主要贡献

软件工具包： 主要贡献是 EuclideanDistanceDegree Macaulay2 软件包，它统一了用于计算 ED 度的符号和数值方法。
算法多样性： 该包提供了四种不同方法的实现（小因子、左核、同伦、共形），允许用户根据簇的结构（例如，余维数、隐式与参数化）以及所需的输出（精确符号度数 vs. 数值近似值）选择最合适的工具。
互操作性： 符号方法包含返回临界理想生成多项式的选项，便于与 HomotopyContinuation.jl 等其他软件进行复现和交叉验证。
数值鲁棒性： 该包集成了 Bertini 和 MonodromySolver，提供了处理路径失败（例如，路径向无穷远发散）的配置选项，并支持单位、加权及泛型 ED 度的计算。

结果与示例
论文通过一系列示例验证了该包：

符号验证： 该包成功计算了 Dingdong 曲面的单位 ED 度 (5) 和泛型 ED 度 (9)，并恢复了临界理想的方程。
数值计算： 它使用特定的数据和权重计算了 Daisy 曲面的加权 ED 度 (22)。
同伦效率： 该包证明了在计算完单位 ED 度后，通过重用初始同伦阶段，可以高效地计算随后的泛型 ED 度。对椭圆形的实验表明，在 100 个样本中，平均实 ED 度约为 3.41，这与理论预期一致。
应用：
- 多项式神经网络： 该包计算了浅层多项式神经网络（例如，针对特定架构的度数为 13）的泛型 ED 度，这延续了关于神经簇（neurovarieties）的前期工作。
- 多视图几何 (Multiview Varieties)： 它计算了锚定在有理曲面上的仿射多视图簇的 ED 度，发现特定配置下的度数为 8 和 12，为已知有理曲线结果的潜在推广提供了经验证据。

意义
本文将 EuclideanDistanceDegree 软件包定位为一个填补计算代数几何领域空白的专门工具。虽然存在针对特定设置的通用符号包（如 AlgebraicOptimization 或 ToricInvariants）以及用于数值求解的通用同伦求解器（如 Bertini 或 PHCpack），但本工具提供了一个专门针对 ED 度的、用户友好的界面。它架起了符号精确性与数值可扩展性之间的桥梁，使代数优化、计算机视觉和机器学习领域的研究人员能够通过计算这些临界不变量，更好地理解其模型的代数复杂度。作者指出，尽管此前不存在专门的数值 ED 工具，但他们的工具利用现有的鲁棒求解器，为这些特定问题提供了流线型的流程。

技术摘要：Macaulay2 中的欧几里得距离度 (Euclidean Distance Degree)

类似论文