論文の概要: Geometric Localization of Homology Cycles
- arxiv url: http://arxiv.org/abs/2406.03183v1
- Date: Wed, 5 Jun 2024 12:13:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-06 18:40:12.642896
- Title: Geometric Localization of Homology Cycles
- Title(参考訳): ホモロジーサイクルの幾何学的局在化
- Authors: Amritendu Dhar, Vijay Natarajan, Abhishek Rathod,
- Abstract要約: 時間的に計算可能で、近似的な意味で安定なサイクルの幾何的最適化を提案する。
実際、(自明な)正確なアルゴリズムは、最悪のケースランタイムがあるにもかかわらず、計算コストがかかる。
これらのアルゴリズムは、適度なサイズのデータセットに対して適切なランタイムを持ち、一貫して高品質である。
- 参考スコア(独自算出の注目度): 2.4906439728472494
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Computing an optimal cycle in a given homology class, also referred to as the homology localization problem, is known to be an NP-hard problem in general. Furthermore, there is currently no known optimality criterion that localizes classes geometrically and admits a stability property under the setting of persistent homology. We present a geometric optimization of the cycles that is computable in polynomial time and is stable in an approximate sense. Tailoring our search criterion to different settings, we obtain various optimization problems like optimal homologous cycle, minimum homology basis, and minimum persistent homology basis. In practice, the (trivial) exact algorithm is computationally expensive despite having a worst case polynomial runtime. Therefore, we design approximation algorithms for the above problems and study their performance experimentally. These algorithms have reasonable runtimes for moderate sized datasets and the cycles computed by these algorithms are consistently of high quality as demonstrated via experiments on multiple datasets.
- Abstract(参考訳): 与えられたホモロジークラスにおける最適サイクルの計算(ホモロジー局所化問題とも呼ばれる)は一般にNPハード問題として知られている。
さらに、クラスを幾何学的にローカライズし、永続ホモロジーの設定の下で安定性を持つような、既知の最適性基準は存在しない。
多項式時間で計算可能で、近似的な意味で安定なサイクルの幾何学的最適化を提案する。
探索基準を異なる設定に合わせることで、最適ホモロジーサイクル、最小ホモロジーベース、最小永続ホモロジーベースといった様々な最適化問題が得られる。
実際、(自明な)正確なアルゴリズムは、最悪の場合、多項式ランタイムを持つにもかかわらず計算コストがかかる。
そこで我々は上記の問題に対する近似アルゴリズムを設計し,その性能を実験的に研究する。
これらのアルゴリズムは、適度なサイズのデータセットに対して合理的なランタイムを持ち、これらのアルゴリズムによって計算されるサイクルは、複数のデータセットの実験を通じて示されるように、一貫して高品質である。
関連論文リスト
- A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis [17.89683724761454]
進化的多目的最適化において,ブロック座標降下が効率的である条件が存在するかを検討する。
本稿では,GSEMOのブロックコーディネートバージョンを提案し,その実行時間を標準GSEMOアルゴリズムと比較する。
論文 参考訳(メタデータ) (2024-04-04T23:50:18Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Generative modeling of time-dependent densities via optimal transport
and projection pursuit [3.069335774032178]
本稿では,時間的モデリングのための一般的なディープラーニングアルゴリズムの代替として,安価に提案する。
我々の手法は最先端の解法と比較して非常に競争力がある。
論文 参考訳(メタデータ) (2023-04-19T13:50:13Z) - Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast
Evasion of Non-Degenerate Saddle Points [8.452349885923507]
グラディエントベースの1次凸最適化アルゴリズムは、機械学習タスクを含むさまざまな領域で広く適用可能である。
最適時間の固定時間理論の最近の進歩に触発されて,高速化最適化アルゴリズムを設計するための枠組みを導入する。
非ド・サドル点を許容する関数に対しては、これらのサドル点を避けるのに必要な時間は初期条件すべてに一様有界であることを示す。
論文 参考訳(メタデータ) (2022-12-07T16:36:23Z) - Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。
適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。
決定集合の低次元構造を高次元問題に活用する。
論文 参考訳(メタデータ) (2022-11-21T18:31:43Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳(メタデータ) (2022-09-27T09:06:37Z) - First-Order Algorithms for Min-Max Optimization in Geodesic Metric
Spaces [93.35384756718868]
min-maxアルゴリズムはユークリッド設定で解析されている。
指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
論文 参考訳(メタデータ) (2022-06-04T18:53:44Z) - Minimal Cycle Representatives in Persistent Homology using Linear
Programming: an Empirical Study with User's Guide [4.46514714749204]
永続ホモロジークラスのサイクル代表は、データ内のトポロジ的特徴の説明に使用することができる。
この問題を解決するためのアプローチの1つは、データのコンテキストで意味のある尺度に対して代表者の選択を最適化することです。
論文 参考訳(メタデータ) (2021-05-14T18:38:48Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳(メタデータ) (2020-04-25T05:45:59Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。