論文の概要: Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for
Scalar Data -- An Algorithm and A Benchmark
- arxiv url: http://arxiv.org/abs/2206.13932v1
- Date: Mon, 27 Jun 2022 10:54:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-29 13:01:31.753081
- Title: Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for
Scalar Data -- An Algorithm and A Benchmark
- Title（参考訳）: Discrete Morse Sandwich: Scalarデータに対する永続化ダイアグラムの高速計算 - アルゴリズムとベンチマーク
- Authors: Pierre Guillou, Jules Vidal, and Julien Tierny
- Abstract要約: 本稿では,d-次元単純複素数 K 上で定義される入力片方向線形スカラー場 f を与えられた永続図計算の効率的なアルゴリズムを提案する。
我々はこのアルゴリズムを離散モース理論の設定内で表現し、考慮すべき入力単純さの数を著しく削減する。
また、この問題に対して「サンドウィッチ」と呼ばれる階層化アプローチを導入する。
- 参考スコア（独自算出の注目度）: 8.648433479399857
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces an efficient algorithm for persistence diagram
computation, given an input piecewise linear scalar field f defined on a
d-dimensional simplicial complex K, with $d \leq 3$. Our method extends the
seminal "PairCells" algorithm by introducing three main accelerations. First,
we express this algorithm within the setting of discrete Morse theory, which
considerably reduces the number of input simplices to consider. Second, we
introduce a stratification approach to the problem, that we call "sandwiching".
Specifically, minima-saddle persistence pairs ($D_0(f)$) and saddle-maximum
persistence pairs ($D_{d-1}(f)$) are efficiently computed by respectively
processing with a Union-Find the unstable sets of 1-saddles and the stable sets
of (d-1)-saddles. This fast processing of the dimensions 0 and (d-1) further
reduces, and drastically, the number of critical simplices to consider for the
computation of $D_1(f)$, the intermediate layer of the sandwich. Third, we
document several performance improvements via shared-memory parallelism. We
provide an open-source implementation of our algorithm for reproducibility
purposes. We also contribute a reproducible benchmark package, which exploits
three-dimensional data from a public repository and compares our algorithm to a
variety of publicly available implementations. Extensive experiments indicate
that our algorithm improves by two orders of magnitude the time performance of
the seminal "PairCells" algorithm it extends. Moreover, it also improves memory
footprint and time performance over a selection of 14 competing approaches,
with a substantial gain over the fastest available approaches, while producing
a strictly identical output. We illustrate the utility of our contributions
with an application to the fast and robust extraction of persistent
1-dimensional generators on surfaces, volume data and high-dimensional point
clouds.
- Abstract（参考訳）: 本稿では,d-次元単純複素数 K 上で定義される入力片方向線形スカラー場 f を$d \leq 3$ で割った永続図計算の効率的なアルゴリズムを提案する。
提案手法は,3つの主加速度を導入し,半音素の"PairCells"アルゴリズムを拡張した。
まず、このアルゴリズムを離散モース理論の設定の中で表現することで、考慮すべき入力単純化の数を大幅に削減する。
第二に、この問題に対して「サンドウィッチ」と呼ばれる階層化アプローチを導入する。
具体的には、1-saddlesの不安定なセットと(d-1)-saddlesの安定なセットをUnion-Findでそれぞれ処理することにより、ミニマサドル永続ペア(D_0(f)$)とサドル最大永続ペア(D_{d-1}(f)$)を効率的に計算する。
この次元 0 と (d-1) の高速な処理により、サンドイッチの中間層である$D_1(f)$の計算について考慮すべき臨界単純さの数が大幅に減少する。
第3に,共有メモリ並列処理による性能改善について述べる。
再現性を目的としたアルゴリズムのオープンソース実装を提供する。
また,公開リポジトリからの3次元データを利用した再現可能なベンチマークパッケージをコントリビュートし,そのアルゴリズムをさまざまな公開実装と比較する。
拡張実験により,提案アルゴリズムは拡張したセミナル"PairCells"アルゴリズムの2桁の時間性能を向上することが示された。
さらに、14の競合アプローチよりもメモリフットプリントと時間パフォーマンスが向上し、最速のアプローチよりも大幅に向上し、厳密に同一の出力を生成する。
本稿では,表面,体積データ,高次元点雲上での持続的な1次元ジェネレータの高速かつロバストな抽出への応用について述べる。
関連論文リスト
- An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - UNETR++: Delving into Efficient and Accurate 3D Medical Image Segmentation [93.88170217725805]
本稿では,高画質なセグメンテーションマスクと,パラメータ,計算コスト,推論速度の両面での効率性を提供するUNETR++という3次元医用画像セグメンテーション手法を提案する。
我々の設計の核となるのは、空間的およびチャネル的な識別的特徴を効率的に学習する、新しい効率的な対注意ブロック(EPA)の導入である。
Synapse, BTCV, ACDC, BRaTs, Decathlon-Lungの5つのベンチマークで評価した結果, 効率と精度の両面で, コントリビューションの有効性が示された。
論文 参考訳（メタデータ） (2022-12-08T18:59:57Z) - Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。
これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。
我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
論文 参考訳（メタデータ） (2022-07-26T04:38:47Z) - Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。
実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。
本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-13T02:44:05Z) - A Fast PC Algorithm with Reversed-order Pruning and A Parallelization
Strategy [22.31288740171446]
PCアルゴリズムは観測データに基づく因果構造発見のための最先端のアルゴリズムである。
条件付き独立テストが実行された場合、最悪の場合、計算コストがかかる可能性がある。
これにより、タスクが数百から数千のノードを含む場合、アルゴリズムは計算的に難解になる。
本稿では、2つのノードを独立にレンダリングする条件セットが非特異であり、特定の冗長ノードを含む場合、結果の精度を犠牲にしない、という批判的な観察を提案する。
論文 参考訳（メタデータ） (2021-09-10T02:22:10Z) - RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。
我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。
最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-04T10:33:59Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳（メタデータ） (2021-04-02T16:05:00Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Fast Coherent Point Drift [4.369046007546103]
コヒーレント点ドリフト(CPD)は、非剛性点集合登録のための古典的な方法である。
単純な対応する制約を導入することで、PDの高速な実装を開発する。
3次元点雲データによる実験結果から,本手法は登録プロセスの負担を大幅に軽減できることが示された。
論文 参考訳（メタデータ） (2020-06-11T09:35:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。