Completing the rank identity for Hadamard powers of Euclidean distance matrices

기술 요약: 유클리드 거리 행렬의 하다마르 거듭제곱에 대한 계수 항등식 완성

문제 정의
본 논문은 유클리드 거리 행렬(EDM) $D$의 $n$차 하다마르(성분별) 거듭제곱 $D^{(n)}$의 계수(rank)에 관한 특정 미해결 문제를 다룬다. $m$개의 점 $x_1, \dots, x_m \in \mathbb{R}^d$가 주어질 때, EDM은 성분 $d_{ij} = \|x_i - x_j\|^2$로 정의되며, 그 $n$차 거듭제곱은 성분 $d_{ij}^n$을 갖는다.

Horvat 등(2014)의 선행 연구는 다음과 같은 계수의 상한을 확립하였다:
$$\text{rank } D^{(n)} \leq R^n_d := \binom{d+n}{d} + \binom{d+n-1}{d}$$
그들은 특정 다항식 공간 $V$ 내에서 모든 점 $x_i$에서 소멸하는 "소멸 다항식(annihilating polynomial)"이 존재할 경우 이 부등식이 엄격하게 성립함을 증명하였다. 그러나 그 역은 해결되지 않은 채 남아 있었다. 즉, 그러한 소멸 다항식의 부재가 반드시 계수를 상한 $R^n_d$에 도달하게 만드는지는 알려지지 않았다. 구면(spherical) 사례에 대한 이전의 증명은 대각 행렬인 제곱 노름(squared norms)이 스칼라가 아니기 때문에 실패했던 정규성(normality) 논증에 의존하였다.

방법론
저자들은 커널 인수분해(kernel factorization)에 기반한 새로운 접근 방식을 통해 정규성 장애를 완전히 우회함으로써 이 미해결 문제를 해결한다. 핵심 방법론은 다음과 같다:

1. 다항식 공간 구축: 저자들은 다항식 공간 $V$(식 1)를 정의하고, 이를 차수 호환적인 세 개의 블록($A, B, C$)으로 분할한다. 이는 동차 차수(homogeneous degrees)를 기준으로 한다.

   • 블록 A: 차수가 $0$에서$n-1$까지인 다항식들.
   • 블록 B: 차수가 $n$인 동차 다항식들.
   • 블록 C: 총 차수가 $n+1$에서 $2n$ 사이인 $\|x\|^{2r}x^\alpha$ 형태의 혼합 항들.
     이 공간의 총 차원은 $N = R^n_d$이다.

2. 커널 인수분해: 저자들은 커널 $K(x, y) = \|x - y\|^{2n}$을 $V$의 기저(basis)에 대한 쌍선형 형식(bilinear form)으로 표현한다. $\|x - y\|^{2n} = (\|x\|^2 - 2x^Ty + \|y\|^2)^n$의 삼항 전개를 사용하여, $D^{(n)}$이 다음과 같이 인수분해될 수 있음을 보여준다:
   $$D^{(n)} = \Phi_V M \Phi_V^T$$
   여기서 $\Phi_V$는 점 $x_i$들에 대한 $V$의 기저 평가 행렬이며, $M$은 커널과 기저 선택에 의해 결정되는 $N \times N$ 행렬로, 점의 배치와 무관하다.

3. $M$의 구조적 분석:

   • 블록 구조: 커널의 결합 동차성(joint homogeneity, 차수 $2n$)으로 인해, 행렬 $M$은 특정 블록 구조를 나타낸다. 즉, 기저 함수의 차수의 합이 $2n$이 되는 곳에서만 비제로(non-zero) 블록이 나타난다. 결과적으로 $M$은 중앙 블록 $M_{BB}$와 오프-대각 블록 $M_{AC}$ 및 $M_{CA}$ ($M_{CA} = M_{AC}^T$)로 구성되며, 그 외의 블록은 모두 $0$이다.
   • 비특이성(Nonsingularity) 증명: 저자들은 대각 블록을 분석함으로써 $M$이 비특이함을 증명한다. 그들은 각 블록 $M^{(k)}$(차수의 합이 $2n$인 쌍에 대응)가 양의 계수를 가진 그람 행렬(Gram matrices)의 가중 합임을 보여준다. 구체적으로, $(-1)^k M^{(k)}$이 양의 정부호($\succ 0$)임을 증명한다. 이러한 균일한 양의 성질은 $\det(M) \neq 0$임을 보장한다.

주요 기여 및 결과

• 미해결 문제 해결: 본 논문은 점 집합 $\{x_i\}$에서 소멸하는 $V$ 내의 $0$이 아닌 다항식이 존재하지 않는다면,$\text{rank } D^{(n)} = R^n_d$임을 증명한다. 이로써 일반적인 경우에 대한 계수 항등식을 완성하였다.
• 보편적 인수분해: $D^{(n)} = \Phi_V M \Phi_V^T$라는, 구성에 독립적인 행렬 $M$을 갖는 유니버설 인수분해 유도는 구면 대칭성과 같은 기하학적 제약에 의존하지 않고 EDM의 거듭제곱을 분석할 수 있는 견고한 대수적 프레임워크를 제공한다.
• 유니버설 행렬의 비특이성: 블록 대각 분석과 가중 합 그람 행렬의 양의 정부호를 통한 $M$의 비특이성 증명은 핵심적인 기술적 성취이다.
• 계수 결핍(Rank Deficiency)의 특성화: 논문은 계수 결핍이 $V$의 기저 함수들의 비자명한 선형 결합이 모든 데이터 포인트에서 소멸할 때만 발생한다는 점을 명확히 한다.

의의
본 논문은 일반적인 점 구성에 대한 정확한 계수 조건을 확립함으로써 Horvat 등(2014)의 정리 2를 완성한다고 주장한다. 그 의의는 구면 사례의 결과를 일반적인 사례로 확장하는 것을 방해했던 "정규성 장애"를 우회하는 데 있다. 계수 문제를 유니버설 행렬 $M$의 비특이성과 평가 사상 $\Phi_V$의 단사성(injectivity) 문제로 환원함으로써, 저자들은 계수 항등식 문제에 대한 결정적인 해답을 제시한다.

저자들은 제너릭 구성(generic configurations, $m \geq R^n_d$인 경우)에 대해, 평가 행렬 $\Phi_V$가 확률 1로 풀 칼럼 랭크(full column rank)를 가짐을 언급한다(계수 결핍 구성은 측도 0인 적절한 대수적 부분 집합에 속하기 때문). 결과적으로 제너릭한 점들에 대해 계수는 정확히 $R^n_d$이다. 또한, NumPy를 이용한 수치적 구현이 차원 $d, n \leq 7$에 대해 블록 구조와 계수 예측을 확인했음을 언급한다.

저자들은 $d=1$인 경우의 알려진 곱 공식과 유사하게, 일반적인 $d$와 $n$에 대한 $\det(M)$의 폐쇄형(closed-form) 표현을 찾는 문제는 여전히 과제로 남겨두었다.