論文の概要: Transport Clustering: Solving Low-Rank Optimal Transport via Clustering

• arxiv url: http://arxiv.org/abs/2603.03578v1
• Date: Tue, 03 Mar 2026 23:12:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-05 21:29:15.117147
• Title: Transport Clustering: Solving Low-Rank Optimal Transport via Clustering
• Title（参考訳）: 輸送クラスタリング:クラスタリングによる低ランク最適輸送の解決
• Authors: Henri Schmidt, Peter Halmos, Ben Raphael,
• Abstract要約: 我々は,低ランクOT計画の計算アルゴリズムであるトランスポートクラスタリングを導入し,低ランクOTを対応レートのフルテキスト型問題に還元する。 実験的に、トランスポートクラスタリングは、合成ベンチマークや大規模で高次元のデータセットにおいて、既存の低ランクOTソルバよりも優れています。
• 参考スコア（独自算出の注目度）: 0.9558392439655014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimal transport (OT) finds a least cost transport plan between two probability distributions using a cost matrix defined on pairs of points. Unlike standard OT, which infers unstructured pointwise mappings, low-rank optimal transport explicitly constrains the rank of the transport plan to infer latent structure. This improves statistical stability and robustness, yields sharper parametric rates for estimating Wasserstein distances adaptive to the intrinsic rank, and generalizes $K$-means to co-clustering. These advantages, however, come at the cost of a non-convex and NP-hard optimization problem. We introduce transport clustering, an algorithm to compute a low-rank OT plan that reduces low-rank OT to a clustering problem on correspondences obtained from a full-rank $\textit{transport registration}$ step. We prove that this reduction yields polynomial-time, constant-factor approximation algorithms for low-rank OT: specifically, a $(1+γ)$ approximation for negative-type metrics and a $(1+γ+\sqrt{2γ}\,)$ approximation for kernel costs, where $γ\in [0,1]$ denotes the approximation ratio of the optimal full-rank solution relative to the low-rank optimal. Empirically, transport clustering outperforms existing low-rank OT solvers on synthetic benchmarks and large-scale, high-dimensional datasets.
• Abstract（参考訳）: 最適輸送(OT)は2つの確率分布間の最小コスト輸送計画を見つける。 非構造点写像を推論する標準的なOTとは異なり、低ランクの最適輸送は遅延構造を推論するために輸送計画のランクを明示的に制限する。 これにより統計的安定性とロバスト性が向上し、ワッサーシュタイン距離を固有ランクに適応させるためのよりシャープなパラメトリックレートが得られ、コクラスタリングに$K$-meansを一般化する。 しかし、これらの利点は、非凸およびNP-ハード最適化問題のコストがかかる。 我々は、フルランク$\textit{transport registration}$stepから得られた対応に基づいて、低ランクOTをクラスタリング問題に還元する低ランクOT計画を計算するアルゴリズムであるトランスポートクラスタリングを導入する。 この減少は低ランクOTに対する多項式時間定数係数近似アルゴリズムをもたらすことを証明している:具体的には、1+γ)$負の値に対する近似と(1+γ+\sqrt{2γ}\,)$$のカーネルコストに対する近似であり、$γ\in [0,1]$は低ランク最適値に対する最適フルランク解の近似比を示す。 実験的に、トランスポートクラスタリングは、合成ベンチマークや大規模で高次元のデータセットにおいて、既存の低ランクOTソルバよりも優れています。

関連論文リスト

• Variational Entropic Optimal Transport [67.76725267984578]
  本稿では,ドメイン翻訳問題に対する変分エントロピー最適輸送(VarEOT)を提案する。 VarEOTは、補助正の正規化子上のトラクタブルな一般化として、log-partition $log mathbbE[exp(cdot)$の正確な変分再構成に基づいている。 合成データと画像と画像の変換に関する実験は、競争力のあるか、あるいはより良い翻訳品質を示す。
  論文  参考訳（メタデータ） (2026-02-02T15:48:44Z)
• Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling [1.8749305679160366]
  大規模データセットに最適なトランスポートを適用する上で重要な課題は、データセットのサイズと結合行列の2次スケーリングである。 我々は、$textitlatent coupling$(LC)因子化に基づいて、低ランク問題の代替パラメータ化を導出する。 グラフクラスタリングや空間転写学などの多様なアプリケーションにおいて,その解釈可能性を示しながら,優れた性能を示す。
  論文  参考訳（メタデータ） (2024-11-15T20:07:15Z)
• Fast and scalable Wasserstein-1 neural optimal transport solver for single-cell perturbation prediction [55.89763969583124]
  最適輸送(OT)理論はそのようなマッピングを構築するための原則的な枠組みを提供する。 We propose a novel solver based on Wasserstein-1 (W$) dual formulation。 我々の実験は、提案した$W$のニューラル・トランスポート・ソルバが、ユニークなモンマップを見つける際に、$W$のOTを模倣できることを実証した。
  論文  参考訳（メタデータ） (2024-11-01T14:23:19Z)
• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  我々は,ラゲールセル推定と密度支持推定の類似性を用いて,OTマップに対して$mathcalO(t-1)$の低いバウンダリレートを証明した。 所望の速さをほぼ達成するために,サンプル数に応じて減少するエントロピー正規化スキームを設計する。
  論文  参考訳（メタデータ） (2024-05-23T11:46:03Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。 SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-21T18:48:45Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• InfoOT: Information Maximizing Optimal Transport [58.72713603244467]
  InfoOTは最適な輸送の情報理論の拡張である。 幾何学的距離を最小化しながら、ドメイン間の相互情報を最大化する。 この定式化は、外れ値に対して堅牢な新しい射影法をもたらし、目に見えないサンプルに一般化する。
  論文  参考訳（メタデータ） (2022-10-06T18:55:41Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。 本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
  論文  参考訳（メタデータ） (2021-02-02T16:18:29Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。