論文の概要: Partial Optimal Transport on the Circle for All Transported Masses in O(N log N)

• arxiv url: http://arxiv.org/abs/2608.23910v1
• Date: Mon, 24 Aug 2026 23:32:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-26 14:09:34.659839
• Title: Partial Optimal Transport on the Circle for All Transported Masses in O(N log N)
• Title（参考訳）: O(N log N)の全輸送質量の円上の部分最適輸送
• Abstract要約: 部分最適輸送は、質量の一部を未整合のまま残しながら2つの測度を比較する。 正確な$O(Nlog N)$ time, $O(N)$ memory algorithm return all $K+1$ cost, nested active set and plan in one run, with a single gap that is simultaneously for everysiteity。
• 参考スコア（独自算出の注目度）: 15.99914046130783
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Partial optimal transport compares two measures while leaving part of the mass unmatched, which is what makes it robust to outliers, occlusion, and clutter. The quantity of interest is usually the whole profile - the optimal cost at every transported cardinality - because the right amount to transport is rarely known in advance, and on the real line the PAWL algorithm returns that profile in $O(N\log N)$. Much data is periodic rather than linear: angles, phases, orientations, time of day, hue, and every direction obtained by projecting onto a great circle. On the circle the same problem acquires a global circulation, or equivalently an optimized cut, which the naive exact method handles by running the line algorithm once per support gap, at $O(N^{2}\log N)$. We show that this factor $N$ is unnecessary. The line structure survives in cut-free form, and a free-gap invariant supplies, at every step, a cut at which all previous local updates remain valid line updates. This yields PAWC: an exact $O(N\log N)$ time, $O(N)$ memory algorithm returning all $K+1$ costs, nested active sets and plans in one run, together with a single gap that is simultaneously optimal for every cardinality. Slicing over great circles extends it to $\mathbb{S}^{d-1}$. Empirically the whole profile costs $0.56$ms at $N=4096$ against $1.5$s for a single transported fraction from a general solver; on occluded, cluttered mpeg-7 shapes, holding the descriptor fixed and varying only the cost, it retains $66\%$ of the clean-data retrieval score against $16\%$ for balanced circular OT, and on $\mathbb{S}^{2}$ it halves the fitting error of spherical sliced Wasserstein against contaminated targets, synthetic and real. Code is available at https://github.com/mint-vu/Partial_Wasserstein_on_Circles.
• Abstract（参考訳）: 部分最適輸送は、質量の一部を未整合のまま残しながら2つの測度を比較する。 関心の量は通常、すべての輸送された基数に対して最適なコストであるプロファイル全体である。なぜなら、輸送する適切な量が事前に知られていることは滅多になく、実数直線上でPAWLアルゴリズムはそのプロファイルを$O(N\log N)$で返すからである。 多くのデータは線形ではなく周期的である:角度、位相、方向、日時、色、そして大円に投影することによって得られるすべての方向である。 円上では、同じ問題が大域循環(すなわち、最適化されたカット)を得るが、これは、単純で正確な方法では、サポートギャップ毎に1回ラインアルゴリズムを実行することで、$O(N^{2}\log N)$で処理する。 この係数が$N$は不要であることを示す。 ライン構造はカットフリーの形で存続し、すべてのステップにおいて、以前のローカルアップデートが有効なライン更新のままのカットがフリーギャップ不変の供給となる。 正確な$O(N\log N)$ time, $O(N)$ memory algorithm return all $K+1$ cost, nested active set and plan in one run, with a single gap that is simultaneously for everysiteity。 大円上のスライシングは$\mathbb{S}^{d-1}$まで拡張する。 実証的に、プロファイル全体のコストは、一般的なソルバから1つの輸送された分数に対して$0.56$ms、1.5$sに対して$N=4096$で$0.56$msである; 隠蔽された、散らばったmpeg-7の形状で、ディスクリプタを固定し、コストだけを変えると、バランスの取れた円形OTに対して$16\%、および$\mathbb{S}^{2}$は、汚染されたターゲット、合成および現実に対して、球状スライスされたWassersteinの適合誤差を埋める。 コードはhttps://github.com/mint-vu/Partial_Wasserstein_on_Circlesで公開されている。

関連論文リスト

• Incremental Optimal Assignment for Real-Time Crowd Tracking [0.0]
  密集した群集における多目的追跡には、各ビデオフレームにおける検出と軌跡間の二部割当問題を解く必要がある。 本稿では,群集追跡コスト行列のブロックスパース構造を利用した指数代入アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-07-23T14:34:42Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent [39.805192541498634]
  本研究では,非定常線形計算(GLBs)について検討し,期待される報酬を未知の時間変化パラメータを持つ非線形リンク関数を用いてモデル化する。 本稿では,パラメータ推定に割引オンラインミラー降下(DOMD)を利用する非定常GLBに対する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-05-25T08:40:32Z)
• Near-Exponential Savings for Mean Estimation with Active Learning [5.681847365688839]
  本稿では,$mathbbE[Y]$を推定する能動的学習アルゴリズム(PartiBandits)を提案する。 PartiBandits は UCB と反対意見に基づくアクティブラーニングのアプローチを橋渡しする。
  論文  参考訳（メタデータ） (2025-11-07T21:48:55Z)
• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
  ターンタイルストリーミングモデルにおいて、異なる要素を数えるという根本的な問題に対して、最初のサブ線形空間を微分プライベートなアルゴリズムを与える。 本結果は, 線形問題である最先端アルゴリズムの空間要求を著しく改善する。 ストリームにアイテムが現れる回数の制限付き$W$が分かっている場合、我々のアルゴリズムは$tildeO_eta(sqrtW)$ space.sqrtW)$ additive errorを提供する。
  論文  参考訳（メタデータ） (2025-05-29T17:21:20Z)
• Corner Gradient Descent [13.794391803767617]
  最大$O(t-2zeta)$までのレートは、無限メモリを持つ一般化定常SGDによって達成できることを示す。 理想コーナーアルゴリズムは有限メモリアルゴリズムによって効率よく近似できることを示す。
  論文  参考訳（メタデータ） (2025-04-16T22:39:41Z)
• Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
  誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。 我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
  論文  参考訳（メタデータ） (2024-06-10T17:48:36Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
  DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。 我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-07-26T08:47:54Z)
• Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP [31.62899359543925]
  線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。 我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。 第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
  論文  参考訳（メタデータ） (2021-12-18T06:47:31Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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