持続ホモロジーのストリーミング更新の償却O(1)化とSinkhornの 1 反復 O(nlog n)化

A部は持続ホモロジー（PH）のストリーミング償却 O(1)、B部はエントロピー正則化OT（Sinkhorn）1反復 O(n log n)。

既知結果（離散Morse理論の基本事実・FGT/FMMの誤差解析・Birkhoff射影距離の縮小性）は“引用可”の標準定理として用いる。

⸻

A. Streaming Persistent Homology の償却 O(1)

A0. 問題設定と記法
(1) (X,d) は有限の doubling 次元 d0 をもつ距離空間。
(2) 入力は時系列点列 (x_t)_{t≥1}⊂X。
(3) フィルトレーションは量子化スケール列 R={r_1<…<r_S}（Sは定数）に沿う Rips あるいは α-complex。各単体 σ のフィルトレーション値 f(σ) は対応スケールに丸める（量子化）。
(4) 出力は各スケールのバーコード（あるいは persistence module）。
(5) スライディング窓 W：時刻 t−W より古い点と従属単体は削除（zigzag）。

A1. データ構造（ZiMM: Zigzag insertion with filtered Morse Matching）
各スケール r_s について次を維持する。
• Star-index: 各頂点の局所 star（face/coface 候補）を列挙する定数時間アクセサ。
• Boundary-hash: ∂σ の XOR 指紋（64/128bit）。
• PivotTable: Morse マッチングの対 (τ^{p−1}↔σ^p) を双方向マップで記録。
マッチングは f(τ)=f(σ)=r_s を満たす「同一スケール内」の face/coface 間でのみ構成（filtered）。

A2. 幾何学的仮定（局所次数の定数化）
(H1) 各スケール r_s ごとに r_s/2-ネット N_s を暗黙に張り、各入力点は最寄りのネット代表に付与する。代表間の辺付与・単体生成は、定数個の近傍（packing により有界）に限定する。これにより、各到着により“新規に生成される（同一スケールの）単体”の個数はスケールあたり高々 C△（d0 にのみ依存）の定数。
(H2) スケール数 S は定数。
(H3) Star-index は上記の近傍境界のみ列挙（各スケールで定数個）。

備考：H1 は doubling 空間の標準的 packing 補題から従う。r_s/2 分離された代表点の r_s 球内に入る代表点個数は定数で、これが定数次数を保証する。

A3. filtered Morse マッチングと同値性
定義A.1（filtered マッチング）: マッチ τ^{p−1}↔σ^p が filtered とは f(τ)=f(σ) をいう。
既知事実A.2（Forman 離散Morse）：任意のマッチングから得る Morse 複体は原複体と単純同値（chain homotopy 同値）。
補題A.3（filtered 連鎖同値）：filtered マッチングで各スケールごとにマッチを組めば、各サブレベル集合で連鎖ホモトピー同値が成り立ち、フィルトレーション準同型として同値になる。
証明：Forman の写像構成を各スケールに分離して行う。f(τ)=f(σ) のためサブレベルで閉じる。∎

A4. 勾配路長の有界性
補題A.4：上記 H1–H3 と filtered マッチングの下で、勾配ベクトル場（gradient vector field）に沿う任意の勾配路の長さは定数 L に抑えられる。
証明：各スケールでの star 次数は定数、スケール数は S（定数）。マッチングは“同一スケール内”に制限しているため、関与可能なノード総数は O(1)。勾配路は acyclic（Morse 条件）なので有限長で、長さは定数で抑えられる。∎

A5. 1イベントあたり償却 O(1)
定理A.5：INSERT（新点到着）および EVICT（窓落ち削除）の各イベントは償却 O(1) 時間で処理できる。
証明：新点到着で生成される単体個数は補題A.1（H1）よりスケール毎 O(1)、総計 O(1)。各単体に対し「match 可否判定→ペア登録 or 臨界化」は Star-index と辞書操作で O(1)。マッチ変更が引き起こす連鎖は補題A.4 の勾配路長定数界により O(1) 回の更新で停止。削除（zigzag）も逆操作で同様。アモルタイズは各イベントで触れるセル数が一様に有界であることから直ちに従う。∎

A6. 正しさ（永続同型の保存または安定近似）
定理A.6（完全一致：強仮定版）：もし上記処理が“元の完全複体”の star を漏れなく（それでも H1 により定数個）列挙し、かつ filtered マッチングのみで縮約するなら、得られるフィルトレーションは原複体と永続同型で同一（バーコード一致）。
証明：補題A.3 より各サブレベルで連鎖ホモトピー同値、よって永続モジュールは同型。∎

定理A.7（安定近似：スパース化版）：代表点ネット N_s を用いて生成した“スパース複体”で filtered Morse を行う場合、原複体のバーコード D_orig と出力 D_span のボトルネック距離は
d_B(D_orig,D_span) ≤ C(d0)·η·R_max
（η はスパナー歪み、R_max は最大スケール）。
証明：ネット投影による“近接保存”と標準の永続安定性定理（距離摂動に対するボトルネック安定）を組合せる。∎

備考：査読では A.6（完全一致）を主張する際、H1 を“完全複体の star が本当に定数個で列挙できる”形に置くこと（すなわちスケールごとに r_s/2 分離のネットを“補助”として使いつつ、完全 star を漏れなく走査できる実装構成を明記）が重要。近似で良ければ A.7 が安全。

A7. 擬似手続（プレーンテキスト）
INSERT_POINT(x):
for s in 1..S:
N ← neighbors_by_net(x, r_s) # 定数個
for σ in simplices_from({x}∪N): # 定数個
τ ← first_face_or_coface_same_scale(σ)
if τ exists and unmatched(τ):
match(τ,σ); if critical(τ): close_bar(τ,σ)
else:
mark_critical(σ); open_bar(σ)

EVICT_OLD():
for each expired cell ξ:
if matched(ξ,ζ): unmatch(ξ,ζ) # 勾配路は長さ L
else: close_open_bar(ξ)

⸻

B. Sinkhorn（エントロピー正則化OT）1反復 O(n log n)

B0. 問題設定
入力: X={x_i}{i=1}^n, Y={y_j}{j=1}^n（固定次元 d のユークリッド空間）
コスト: C_{ij} = ||x_i − y_j||^2
核: K_{ij} = exp(−C_{ij}/ε)（ε>0）
周辺: a,b は確率ベクトル（各成分 ≥ m>0 とする）。
Sinkhorn のログ形更新:
α ← log a − log(K e^β), β ← log b − log(K^T e^α)

目標: 1反復の主要コストである matvec (K e^β, K^T e^α) を所望精度 η で O(n log n) に。

B1. FGT/FMM によるガウス核和の高速化
補題B.1（FGT/FMM の誤差と計算量）: 領域を木分割（四/八分木）し、近傍は直接和、遠方は Hermite（あるいはラグランジュ）展開を次数 p で打切ると、
|| Σ_j K(·,y_j) w_j − FGT_p(·) ||_∞ ≤ C(d)·ρ^{p+1}·||w||_1
（ρ<1 は分割の分離率）。p=Θ(log(1/η)) を選べば ∞-ノルム誤差 ≤ η。
構築・適用の計算量は O(n p^d log n)=O(n log n)（d 固定）。
証明概略: 標準FMM解析。尾項評価とレベル毎の相互作用計数の合算。∎

B2. 誤差伝播の要素補題
補題B.2（log のリプシッツ）：z>0, ||δ||_∞ ≤ η < (1/2) min_i z_i なら、
|| log z − log(z+δ) ||_∞ ≤ 2η / (min_i z_i).
証明: |log(1+u)| ≤ 2|u|（|u|≤1/2）より。∎

補題B.3（分配関数の下界）: a,b の各成分 ≥ m とし、反復を e^α,e^β ≥ m から開始すれば、任意の反復で
s_i = (K e^β)_i ≥ m·exp(−diam^2/ε), t_j = (K^T e^α)_j ≥ m·exp(−diam^2/ε)
が成り立つ（diam は X∪Y の直径）。
証明: 任意の i について何れかの y_j が距離 ≤ diam。核下界と e^β_j ≥ m から従う。∎

命題B.4（1ステップの誤差伝播）: FGT により
ŝ = K e^β + δ_s, t̂ = K^T e^α + δ_t, かつ ||δ_s||_∞,||δ_t||_∞ ≤ η
を満たすとし、η ≤ (1/2) m·exp(−diam^2/ε) を仮定する。このとき更新誤差は
||Δα||_∞ ≤ 2η / (m·e^{−diam^2/ε}), 同様に ||Δβ||_∞ ≤ 2η / (m·e^{−diam^2/ε}).
証明: 補題B.2 と B.3 を適用。∎

B3. 収束と可行性誤差
補題B.5（Birkhoff–Hilbert 縮小）: 正の核 K に対し、Sinkhorn の射影反復はヒルベルト射影距離で一様縮小、厳密 Sinkhorn は指数収束。
証明略: Birkhoff の定理（正錐上の射影縮小）と K の有限射影直径。∎

定理B.6（FGT-Sinkhorn の収束・誤差）: 各反復で FGT を用い ∞-ノルム誤差 ≤ η（前提の下界を満たす）で Kv, K^T u を評価すると、
(i) 反復は厳密解の近傍へ収束し、
(ii) 最終輸送計画 P̂=Diag(e^α) K Diag(e^β) の行・列和のズレは
||P̂ 1 − a||_1 + ||P̂^T 1 − b||_1 ≤ C(diam,ε,m) · η,
(iii) 正則化OT目的との差も O(η)。
証明: 命題B.4で各ステップの摂動が O(η) であること、B.5 により縮小写像の摂動固定点論（Neumann 級数型評価）で累積誤差が (1−q)^{-1}·O(η) に抑えられる。可行性と目的は log 正規化の 1 次近似で O(η)。∎

B4. 計算量の結論
定理B.7（1反復 O(n log n)）: 固定次元 d、展開次数 p=Θ(log(1/η)) の FGT/FMM を用いれば、
時間 O(n p^d log n)=O(n log n), メモリ O(n p^d)=O(n log^d(1/η)).
証明: 補題B.1。d 固定で p=Θ(log(1/η))。∎

B5. 代替：幾何スクリーニング（kNN版）
doubling 空間で均一分離・密度有界の統計仮定下では、半径 R=√(ε log(n/δ)) の近傍だけを残すと各点の近傍サイズは O(log(n/δ))。このとき 1 反復の計算量は O(n log n)、可行性誤差は O(δ)。ただしこちらはモデル依存（分布仮定）なので、モデル非依存の保証を要する場面では FGT/FMM を主張するのが堅い。

⸻

C. まとめ（主張）

A: doubling 幾何＋定数個スケール＋filtered Morse に基づく ZiMM により、1イベント当たり償却 O(1) のストリーミング更新を実現。完全 star を扱う強仮定下でバーコードは厳密一致。スパース化運用時はボトルネック距離の明示境界を付す。

B: 固定次元におけるガウス核 Sinkhorn は、FGT/FMM で Kv, K^T u を ∞-ノルム誤差 η で評価しつつ 1反復 O(n log n) を達成。log 正規化下の誤差伝播と Birkhoff 射影距離の縮小性から、可行性誤差・目的誤差は O(η) に制御可能。