最適輸送へのマルチスケールアプローチ

要旨 本論文では、ユークリッド平面において質量制約を持つ確率密度と有限の地点との間の最小二乗一致を見つけるためのAurenhammer、Hoffmann、Aronovのアルゴリズムの改善を提案します。私たちのアルゴリズムは、この最適輸送問題のマルチスケール性を活かしています。私たちはLloydのアルゴリズムを使用してターゲットを反復的に簡略化し、その簡略化された問題の解を、より複雑な問題への粗い初期解として使用します。このアプローチにより、最適輸送に関連する測度間の距離（Earth‐moverまたはWasserstein距離として知られる）の迅速な推定が可能になります。さらに、これらのアルゴリズムの実装について議論し、元のアルゴリズムとそのマルチスケール版を比較します。