要旨: 本論文では、ランダム幾何グラフから d 次元リーマン多様体の潜在的な幾何構造を復元する問題を研究する。最近の研究では、ランダム幾何グラフからの多様体復元、より一般にはノイズを含む距離からの復元において、大きな進展が見られている。しかし、対となる距離の推定精度は、本質的に体積的な障壁、すなわち自然なサンプル間隔のスケール n^{-1/d} によって根本的に制約されてきた。これは、（一般的には）多様体上の典型的な点が、最も近いサンプル点からの距離として次数 n^{-1/d} の距離に位置することに由来する。本論文では、新しい手法である直交リング距離推定ルーチン（ORDER）を導入し、ポリログ因子を除いた範囲で、点ごとの距離推定精度を n^{-2/(d+5)} のオーダーで達成し、計算時間は多項式時間であることを示す。これは、次元 d > 5 において体積的な障壁を厳密に上回る。
その結果として、距離 n^{-1/d} よりも良い点ごとの精度を得られることから、復元されたメトリック測度空間と真の潜在多様体との間のグロモフ—ワッサースタイン距離は n^{-1/d} のオーダーであることを証明する。これは経験測度のワッサースタイン収束率と一致し、復元したグラフの距離が、サンプル点に関する全ての対距離行列にアクセスできる場合と漸近的に同等に良いことを示している。我々の結果は、ノイズを含む対距離の一般的なモデル、疎なランダム幾何グラフ、未知の接続確率関数を含む、非常に一般的な設定で証明される。
体積バリアを超えた距離のデノイジング
arXiv stat.ML / 2026/4/2
💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research
要点
- 本論文は、ランダム幾何グラフからd次元リーマン多様体の潜在幾何（latent geometry）を復元する問題を扱い、ノイズ下でのペアごとの距離推定の精度がどこまで可能かに焦点を当てる。
- 近傍点サンプリングが典型的にその程度の隔たりになるため、点ごとの距離精度を自然なサンプル間隔スケール n^{-1/d} のオーダーにまで制限する「体積バリア（volumetric barrier）」を特定する。
- 著者らは、点ごとの距離推定精度を（多項式対数因子を除き）n^{-2/(d+5)} のオーダーへと改善する多項式時間手法 ORDER（Orthogonal Ring Distance Estimation Routine）を導入し、d>5 の場合には体積バリアを厳密に上回ることを示す。
- 改善された点ごとの推定値を用いて、本論文は、復元されたメトリック測度空間が真の多様体に対しGromov–Wasserstein距離で n^{-1/d} のオーダーで近似されることを証明し、経験的測度における Wasserstein の収束率と整合することを示す。
- これらの結果は、ノイズ付き距離モデル、疎なランダム幾何グラフ、未知の接続確率関数を含む幅広い枠組みで成り立ち、このアプローチの頑健な一般性を示唆している。
