論文の概要: A Homotopy Algorithm for Optimal Transport

• arxiv url: http://arxiv.org/abs/2112.06763v1
• Date: Mon, 13 Dec 2021 16:17:51 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-14 19:28:18.718223
• Title: A Homotopy Algorithm for Optimal Transport
• Title（参考訳）: 最適輸送のためのホモトピーアルゴリズム
• Authors: Roozbeh Yousefzadeh
• Abstract要約: 最適な輸送問題は、機械学習、物理学、生物学、経済学など、多くの応用がある。 そこで本研究では,まず,対象分布を変化させることにより,問題を簡単な形式に変換するホモトピーアルゴリズムを提案する。 その後、一連の反復を通して問題を元の形式に戻し、元の問題の最適解を見つけるまで解の経路をトレースする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The optimal transport problem has many applications in machine learning, physics, biology, economics, etc. Although its goal is very clear and mathematically well-defined, finding its optimal solution can be challenging for large datasets in high-dimensional space. Here, we propose a homotopy algorithm that first transforms the problem into an easy form, by changing the target distribution. It then transforms the problem back to the original form through a series of iterations, tracing a path of solutions until it finds the optimal solution for the original problem. We define the homotopy path as a subspace rotation based on the orthogonal Procrustes problem, and then we discretize the homotopy path using eigenvalue decomposition of the rotation matrix. Our goal is to provide an algorithm with complexity bound $\mathcal{O}(n^2 \log(n))$, faster than the existing methods in the literature.
• Abstract（参考訳）: 最適輸送問題は、機械学習、物理学、生物学、経済学などに多くの応用がある。 その目的は非常に明確で数学的に明確に定義されているが、その最適解を見つけることは、高次元空間における大きなデータセットにとって困難である。 本稿では,この問題を対象分布を変化させることで,まず問題を簡単な形式に変換するホモトピーアルゴリズムを提案する。 その後、問題を一連の反復を通じて元の形式に変換し、元の問題の最適解を見つけるまで解の経路をたどる。 ホモトピー経路を直交プロクリスト問題に基づく部分空間回転として定義し、回転行列の固有値分解を用いてホモトピー経路を識別する。 我々のゴールは、文献の既存のメソッドよりも早く、$\mathcal{O}(n^2 \log(n))$で制限された複雑さを持つアルゴリズムを提供することです。

関連論文リスト

• Beyond Discretization: Learning the Optimal Solution Path [3.9675360887122646]
  本稿では,解経路を基底関数の集合でパラメータ化し,エンフィングル最適化問題を解く手法を提案する。 我々の手法は、離散化よりも相当に複雑化している。 また、機械学習に共通する特殊なケースに対して、より強力な結果を示す。
  論文  参考訳（メタデータ） (2024-10-18T22:23:42Z)
• Flow Priors for Linear Inverse Problems via Iterative Corrupted Trajectory Matching [35.77769905072651]
  本稿では,MAP推定器を効率的に近似する反復アルゴリズムを提案し,様々な線形逆問題の解法を提案する。 本アルゴリズムは,MAPの目的を局所MAP'の目的の和で近似できるという観測によって数学的に正当化される。 我々は,超解法,デブロアリング,インペイント,圧縮センシングなど,様々な線形逆問題に対するアプローチを検証する。
  論文  参考訳（メタデータ） (2024-05-29T06:56:12Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。 1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。 有名な座標降下法に基づく新しいN-Cut解法を提案する。
  論文  参考訳（メタデータ） (2023-11-26T07:11:58Z)
• A quantum central path algorithm for linear optimization [5.450016817940232]
  中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。 このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。 標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
  論文  参考訳（メタデータ） (2023-11-07T13:26:20Z)
• Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic Algorithm [77.53604156112144]
  我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。 非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
  論文  参考訳（メタデータ） (2023-10-19T13:57:38Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Mean Field Approximation for solving QUBO problems [0.0]
  平均場焼鈍における統計物理学的アプローチと量子力学的アプローチが同じ結果をもたらすことを示す。 提案手法は連続変数を持つ単純な勾配に基づく最小化からなるため,シミュレーションが容易である。
  論文  参考訳（メタデータ） (2021-06-06T20:35:28Z)
• A Sketching Method for Finding the Closest Point on a Convex Hull [0.0]
  我々は,データセットの凸殻上の点を,その外側の問合せ点に最も近いようにスケッチするアルゴリズムを開発した。 本手法は, 既成のアルゴリズムよりも高速な凸問題の最適解を導出する。
  論文  参考訳（メタデータ） (2021-02-21T03:55:18Z)
• Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
  変換の値に関する事前情報がない点集合を整列するロバストな手法を提案する。 我々のアルゴリズムは変換の正規化を必要とせず、変換の値に関する事前情報がない状況に対処できる。 実験により,提案手法が最先端のアルゴリズムよりも高いロバスト性を示した。
  論文  参考訳（メタデータ） (2020-07-05T15:23:33Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)

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

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