Euclidean Distance Degrees in Macaulay2

기술 요약: Macaulay2의 유클리드 거리 차수(Euclidean Distance Degrees)

문제 정의
유클리드 거리(Euclidean Distance, ED) 차수는 대수적 최적화에서 근본적인 불변량으로, 실수 대수 다양체(real algebraic varieties)에 대한 최근접 점 문제의 복잡도를 측정한다. 구체적으로, 임의의 데이터 포인트 $u \in \mathbb{R}^n$와 다양체 $X \subseteq \mathbb{R}^n$에 대하여, ED 차수는 $X$에 제한된 제곱 유클리드 거리 함수 $\|x - u\|^2$ (또는 가중 변형 $\|x - u\|_w^2$)의 비특이 복소 임계점(nonsingular complex critical points)의 개수로 정의된다. 많은 과학 및 공학 모델이 다항식 시스템으로 표현되지만, 임의의 다양체에 대해 ED 차수를 계산할 수 있는 도구는 제한적이었다. 본 논문은 기호적(symbolic) 및 수치적(numerical) 대수 기하학 기법을 모두 사용하여 ED 차수를 계산할 수 있는 견고한 소프트웨어 구현의 필요성을 다룬다.

방법론
저자들은 Macaulay2 컴퓨터 대수 시스템을 위한 EuclideanDistanceDegree 패키지를 소개한다. 이 패키지는 입력 다양체의 성격(암시적 vs 매개변수화)과 계산 전략(기호적 vs 수치적)에 따라 분류된 네 가지 뚜렷한 알고리즘 접근 방식을 구현한다:

1. 소수 방법 (Minors Method, 기호적):

   • 접근 방식: 이 방법은 다양체 $X$를 소 아이디얼(prime ideal) $I_X$로 정의된 복소 다양체로 취급한다. 표준 야코비안(Jacobian) $J$에 가중 거리 그래디언트로부터 유도된 행 벡터를 추가하여 확장된 야코비안 행렬 $\hat{J}$를 구성한다.
   • 계산: 가중 임계 아이디얼은 포화(saturation)를 통해 계산된다: $C_{X,u,w} = (I_X + \text{minors}_{c+1}(\hat{J})) : I_{X_{sing}}^\infty$.
   • 출력: 이 아이디얼의 차수가 ED 차수를 산출한다. 이 접근 방식은 기호적으로 구현되며 임계 아이디얼의 명시적인 방정식을 반환할 수 있다.

2. 좌측 커널 방법 (Left Kernel Method, 수치적/완전 교차):

   • 접근 방식: 소수 방법이 포화 단계 및 소수의 폭발적 증가로 인해 계산적으로 매우 까다로운 큰 코디멘션(codimension)의 다양체를 위해 설계되었다. 이는 라그랑주 승수법(Lagrange multipliers)을 사용하여 임계점 방정식을 직접 해결하는 데 활용된다.
   • 계산: 완전 교차(complete intersection)인 경우, 정의 다항식 $f_1, \dots, f_k$와 라그랑주 승수 조건 $\lambda_0(x-u) + \sum \lambda_i \nabla f_i = 0$을 결합한 시스템 $G(x, \lambda) = 0$을 형성한다.
   • 구현: 이 시스템은 호모토피 연속법(homotopy continuation)을 통해 Bertini 소프트웨어 패키지를 사용하여 수치적으로 해결된다.

3. 호모토피 방법 (Homotopy Method, 수치적/완전 교차 너머):

   • 접ched 방식: 완전 교차가 아닌 다양체나 매개변수화된 가중치를 탐색하기에 적합한 좌측 커널 방법의 확장이다.
   • 계산: 두 단계의 호모토피 연속 과정을 사용한다. 먼저, 초기 경계값을 설정하기 위해 제네릭 가중치를 사용하여 "시작 시스템(start system)"을 해결한다. 그 다음, 파라미터 호모토피를 사용하여 타겟 시스템(특정 가중치 또는 데이터)으로 해를 추적한다.
   • 효율성: 이를 통해 여러 가중치 또는 데이터 구성에 대한 ED 차수를 효율적으로 계산할 수 있으며, 초기 단계는 한 번만 실행하면 된다.

4. 코노멀 다양체 방법 (Conormal Varieties Method, 매개변수화):

   • 접근 방식: 매개변수화 $\phi: \mathbb{C}^d \to \mathbb{C}^n$로 주어진 다양체를 대상으로 한다.
   • 계산: 매개변수화의 전치 야코비안(transposed Jacobian)의 커널을 찾아 아핀 코노멀 다양체를 구성한다. 임계점은 매개변수화와 커널 생성자들을 포함하는 특정 선형 시스템을 만족하는 쌍 $(x, \lambda)$로 식별된다.
   • 구현: 이는 기호적으로 계산하거나 MonodromySolver 패키지를 사용하여 수치적으로 계산할 수 있다.

주요 기여

• 소프트웨어 패키지: 주요 기여는 ED 차수 계산을 위해 기호적 및 수적 방법을 통합한 Macaulay2 패키지인 EuclideanDistanceDegree이다.
• 알고리즘의 다양성: 이 패키지는 네 가지 방법(Minors, Left Kernel, Homotopy, Conormal)의 구현을 제공하여, 사용자가 다양체의 구조(예: 코디멘션, 암시적 vs 매개로 파라미터화)와 원하는 출력(정확한 기호적 차수 vs 수치적 근사치)에 따라 가장 적절한 도구를 선택할 수 있게 한다.
• 상호 운용성: 기호적 방법은 임계 아이디얼의 생성 다항식을 반환하는 옵션을 포함하여, HomotopyContinuation.jl과 같은 다른 소프트웨어와의 재현 및 교차 검증을 용이하게 한다.
• 수치적 견고성: 이 패키지는 Bertini 및 MonodromySolver와 통합되어 경로 실패(예: 무한대로 발산하는 경로)를 처리하기 위한 구성 옵션을 제공하며, 단위(unit), 가중(weighted), 제네릭(generic) ED 차수 계산을 모두 지원한다.

결과 및 예시
논문은 다음과 같은 다양한 예시를 통해 패키지를 검증한다:

• 기호적 검증: 패키지는 Dingdong 표면에 대해 단위 ED 차수(5)와 제네릭 ED 차수(9)를 성공적으로 계산하며, 임계 아이디얼 방정식의 회복을 보여준다.
• 수치적 계산: 특정 데이터와 가중치를 사용하여 Daisy 표면에 대한 가중 ED 차수(22)를 계산한다.
• 호모토피 효율성: 패키지는 단위 ED 차수를 계산한 후, 초기 호모토피 단계를 재사용함으로써 이후의 제네릭 ED 차수를 효율적으로 계산할 수 있음을 입증한다. 타원(ellipse)에 대한 실험 결과, 100개의 샘플에 대해 평균 실수 ED 차수가 약 3.41로 나타났으며, 이는 이론적 기대치와 일치한다.
• 응용 분야:
  • 다항 신경망(Polynomial Neural Networks): 이전의 뉴로베리에티(neurovarieties) 연구를 따라, 얕은 다항 신경망(예: 특정 구조에서 차수 13)의 제네릭 ED 차수를 계산한다.
  • 다시점 다양체(Multiview Varieties): 유리 곡면(rational surfaces)에 고정된 아핀 다시점 다양체의 ED 차수를 계산하여, 특정 구성에서 8과 12의 차수를 찾아냄으로써 알려진 유리 곡선 결과의 잠재적 일반화에 대한 경험적 증거를 제공한다.

의의
본 논문은 EuclideanDistanceDegree 패키지를 계산 대수 기하학 분야의 공백을 메우는 전문 도구로 자리매김한다. 특정 환경을 위한 일반적인 기호적 패키지(AlgebraicOptimization 또는 ToricInvariants)와 수치적 해결을 위한 일반적인 호모토피 솔버(Bertini 또는 PHCpack)가 존재하지만, 이 패키지는 ED 차수에 특화된 전용 인터페이스를 제공한다. 이는 기호적 정확성과 수치적 확장성 사이의 간극을 메워, 연구자들이 이러한 불변량을 계산함으로써 자신의 모델의 대수적 복잡도를 더 잘 이해할 수 있도록 돕는다. 저자들은 이전에 전용 수치 ED 패키지가 없었음을 언급하며, 이 도구가 기존의 강력한 솔버들을 활용하여 이러한 특정 문제들을 위한 간소화된 워크플로우를 제공한다고 밝히고 있다.