Completing the rank identity for Hadamard powers of Euclidean distance matrices

技術要約：ユークリッド距離行列のアダマール冪におけるランク恒等式の完成

問題提起
本論文は、ユークリッド距離行列（EDM）$D$ の第 $n$ アダマール（要素ごとの）冪、$D^{(n)}$ のランクに関する特定の未解決問題を取り扱う。点 $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$ に達することを必ずしも強制するかどうかは不明であった。球面ケースにおける先行研究の証明は、対角行列である二乗ノルムがスカラーではないため、正規性（normality）の議論が失敗するという問題があった。

手法
著者らは、カーネル分解に基づく新しいアプローチを用いることで、正規性の障害を完全に回避し、この未解決問題を解決する。コアとなる手法は以下の通りである：

1. 多項式空間の構成： 著者らは、多項式の次数に関して互換性のある3つのブロック（$A$、$B$、$C$）に分割された多項式空間 $V$（式1）を定義する。

   • ブロック 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$ の基底上の双線形形式として表現する。$\|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 \times N$ 評価行列であり、$M$ はカーネルと基底の選択のみによって決定される $N \times N$ 行列であり、点配置には依存しない。

3. $M$ の構造解析：

   • ブロック構造： カーネルの結合同次性（次数 $2n$）により、$M$ は特定のブロック構造を持つ。非ゼロのブロックは、基底関数の次数の和が $2n$ になる場合にのみ現れる。これにより、$M$ は中央のブロック $M_{BB}$ と、オフダイアゴナル・ブロック $M_{AC}$ および $M_{CA}$（ここで $M_{CA} = M_{AC}^T$）から構成され、他のすべてのブロックはゼロとなる構造を持つ。
   • 非特異性の証明： 著者らは、各ブロック $M^{(k)}$（次数の和が $2n$ となるペアに対応）を分析することで、$M$ が非特異であることを証明する。具体的には、各ブロック $M^{(k)}$ がグラム行列の正の係数による加重和であることを示す。特に、$(-1)^k M^{(k)}$ が正定値（$\succ 0$）であることを証明する。この一様な正値性は、$\det(M) \neq 0$ を保証する。

主要な貢献と結果

• 未解決問題の解決： 本論文は、点集合 $\{x_i\}$ において消滅する $V$ 内の非ゼロ多項式が存在しないならば、$\text{rank } D^{(n)} = R^n_d$ となることを証明した。これにより、ジェネリックなケースにおけるランク恒等式が完成した。
• 普遍的な分解： $D^{(n)} = \Phi_V M \Phi_V^T$ という、配置に依存しない行列 $M$ を伴う導出は、球面対称性のような幾何学的制約に依存せずにEDMの冪を分析するための堅牢な代数的枠組みを提供する。
• 普遍的行列の非特異性： ブロック対角分析とグラム行列の加重和の正定値性を用いた $M$ の非特異性の証明は、中心的な技術的成果である。
• ランク欠損の特性付け： 本論文は、ランクの欠損が、基底関数 $V$ の線形結合のうち、すべてのデータポイントで消滅する非自明なものが存在する場合にのみ起こることを明確にしている。

意義
本論文は、一般的な点配置に対する正確なランク条件を確立することで、Horvatら（2014）の定理2を完成させると主張している。その意義は、球面ケースの結果を一般のケースへ拡張することを妨げていた「正規性の障害」を回避した点にある。ランクの問題を、普遍的行列 $M$ の非特異性と評価写像 $\Phi_V$ の単射性に帰着させることで、著者らはランク恒等性の問題に対して決定的な回答を提供している。

著者らは、ジェネリックな構成（$m \geq R^n_d$ の場合）において、評価行列 $\Phi_V$ は確率1でフル列ランクを持つこと（ランク欠損の構成は、測度ゼロの適切な代数的部分集合に位置するため）に注意を向けている。したがって、ジェネリックな点に対して、ランクは正確に $R^n_d$ となる。また、数値実装（NumPy）が、次元 $d, n \leq 7$ においてブロック構造とランク予測を確認していることにも言及している。

本研究では、一般の $d$ および $n$ に対して、既知の $d=1$ の場合の積公式に類似した $\det(M)$ の閉形式の表現を見出すという課題が残されている。