論文の概要: A Normalized Bottleneck Distance on Persistence Diagrams and Homology Preservation under Dimension Reduction
- arxiv url: http://arxiv.org/abs/2306.06727v2
- Date: Thu, 29 Aug 2024 01:26:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-30 19:48:14.665251
- Title: A Normalized Bottleneck Distance on Persistence Diagrams and Homology Preservation under Dimension Reduction
- Title(参考訳): 次元減少下における恒常化ボトルネック距離の持続図とホモロジー保存
- Authors: Nathan H. May, Bala Krishnamoorthy, Patrick Gambill,
- Abstract要約: パーシステンスダイアグラム(PD)は、ポイントクラウドデータのシグネチャとして使用される。
PD間のボトルネック距離d_Bを用いて2つの点の雲を比較することができる。
我々は、PD間の新しいスケール不変距離を正規化ボトルネック距離d_Nと定義し、研究する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Persistence diagrams (PDs) are used as signatures of point cloud data. Two clouds of points can be compared using the bottleneck distance d_B between their PDs. A potential drawback of this pipeline is that point clouds sampled from topologically similar manifolds can have arbitrarily large d_B when there is a large scaling between them. This situation is typical in dimension reduction frameworks. We define, and study properties of, a new scale-invariant distance between PDs termed normalized bottleneck distance, d_N. In defining d_N, we develop a broader framework called metric decomposition for comparing finite metric spaces of equal cardinality with a bijection. We utilize metric decomposition to prove a stability result for d_N by deriving an explicit bound on the distortion of the bijective map. We then study two popular dimension reduction techniques, Johnson-Lindenstrauss (JL) projections and metric multidimensional scaling (mMDS), and a third class of general biLipschitz mappings. We provide new bounds on how well these dimension reduction techniques preserve homology with respect to d_N. For a JL map f that transforms input X to f(X), we show that d_N(dgm(X),dgm(f(X))) < e, where dgm(X) is the Vietoris-Rips PD of X, and pairwise distances are preserved by f up to the tolerance 0 < \epsilon < 1. For mMDS, we present new bounds for d_B and d_N between PDs of X and its projection in terms of the eigenvalues of the covariance matrix. And for k-biLipschitz maps, we show that d_N is bounded by the product of (k^2-1)/k and the ratio of diameters of X and f(X). Finally, we use computational experiments to demonstrate the increased effectiveness of using the normalized bottleneck distance for clustering sets of point clouds sampled from different shapes.
- Abstract(参考訳): パーシステンスダイアグラム(PD)は、ポイントクラウドデータのシグネチャとして使用される。
PD間のボトルネック距離d_Bを用いて2つの点の雲を比較することができる。
このパイプラインの潜在的な欠点は、トポロジカルに類似した多様体からサンプリングされた点雲は、その間に大きなスケーリングがあるときに任意に大きいd_Bを持つことができることである。
この状況は次元削減フレームワークで典型的である。
我々は、PD間の新しいスケール不変距離を正規化ボトルネック距離(d_N)と定義し、研究する。
d_N の定義において、等濃度の有限距離空間と単射とを比較するための計量分解と呼ばれるより広範なフレームワークを開発する。
我々は,d_N の安定度を,単射写像の歪みに明示的な境界を導出することにより,計量分解を用いて証明する。
次に、Johnson-Lindenstrauss(JL)プロジェクションとメートル法多次元スケーリング(MDS)という2つの一般的な次元削減手法と、一般的なビリプシッツ写像の第3級について研究する。
我々は、これらの次元還元技術が d_N に関してホモロジーをいかに保存するかの新しい境界を提供する。
入力 X を f(X) に変換する JL 写像 f に対し、d_N(dgm(X),dgm(f(X))) < e, ここで dgm(X) は X のヴィエトリス・リップ PD であり、対距離は f < \epsilon < 1 まで f で保存される。
mMDS に対して、X の PD とその射影の間の d_B と d_N の新たな境界を共分散行列の固有値の観点から提示する。
また、k-biLipschitz写像に対して、d_N は (k^2-1)/k の積と X と f(X) の直径の比で有界であることを示す。
最後に, 異なる形状から採取した点雲のクラスタリング集合に対して, 正規化ボトルネック距離を用いた計算実験を行った。
関連論文リスト
- Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳(メタデータ) (2024-04-29T15:04:07Z) - Horizon-Free Regret for Linear Markov Decision Processes [92.02082223856479]
最近の一連の研究は、強化学習における残念な境界が(ほぼ)計画的地平から独立していることを示している。
我々は、人気のある線形マルコフ決定過程(MDP)設定に対して、最初の地平面自由境界を与える。
遷移モデルを明示的に推定し、不均一な値関数を計算する先行研究とは対照的に、直接値関数と信頼集合を推定する。
論文 参考訳(メタデータ) (2024-03-15T23:50:58Z) - Scaling Riemannian Diffusion Models [68.52820280448991]
非自明な多様体上の高次元タスクにスケールできることを示す。
我々は、$SU(n)$格子上のQCD密度と高次元超球面上の対照的に学習された埋め込みをモデル化する。
論文 参考訳(メタデータ) (2023-10-30T21:27:53Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳(メタデータ) (2023-01-16T02:57:37Z) - High-dimensional limit theorems for SGD: Effective dynamics and critical
scaling [6.950316788263433]
我々は、勾配降下(SGD)の要約統計の軌跡に対する極限定理を証明する。
下記の有効弾道力学が人口減少の勾配流と一致するステップサイズにおける重要なスケーリング体制を示す。
この実効力学の固定点について、対応する拡散極限は極めて複雑であり、さらに退化することもある。
論文 参考訳(メタデータ) (2022-06-08T17:42:18Z) - Entropic Optimal Transport in Random Graphs [8.7314407902481]
グラフ解析において、古典的なタスクはノード間の(グループの)類似性の計算によって構成される。
潜在空間におけるノード群間の距離を連続的に推定することは可能であることを示す。
論文 参考訳(メタデータ) (2022-01-11T13:52:34Z) - Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。
アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
論文 参考訳(メタデータ) (2021-06-04T16:37:19Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳(メタデータ) (2021-02-05T14:02:20Z) - From Geometry to Topology: Inverse Theorems for Distributed Persistence [0.0]
正しい不変量は、X の永続化図形ではなく、多くの小さな部分集合の永続化図形の集まりであることを示す。
この不変性は、私たちが"分散永続化"と呼んでいるもので、簡単に並列化可能で、外れ値に対してより安定です。
結果は、実際に分散持続性の使用を実証する2つの合成実験によって補完される。
論文 参考訳(メタデータ) (2021-01-28T21:36:45Z) - Manifold Learning via Manifold Deflation [105.7418091051558]
次元削減法は、高次元データの可視化と解釈に有用な手段を提供する。
多くの一般的な手法は単純な2次元のマニフォールドでも劇的に失敗する。
本稿では,グローバルな構造を座標として組み込んだ,新しいインクリメンタルな空間推定器の埋め込み手法を提案する。
実験により,本アルゴリズムは実世界および合成データセットに新規で興味深い埋め込みを復元することを示した。
論文 参考訳(メタデータ) (2020-07-07T10:04:28Z) - Unsupervised Discretization by Two-dimensional MDL-based Histogram [0.0]
教師なしの離散化は多くの知識発見タスクにおいて重要なステップである。
本稿では,2次元データのより柔軟な分割を可能にする表現型モデルクラスを提案する。
本稿では,各次元を交互に分割し,隣接する領域をマージするPALMというアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-02T19:19:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。