論文の概要: A Normalized Bottleneck Distance on Persistence Diagrams and Homology
Preservation under Dimension Reduction
- arxiv url: http://arxiv.org/abs/2306.06727v1
- Date: Sun, 11 Jun 2023 17:17:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-13 17:07:31.753503
- Title: A Normalized Bottleneck Distance on Persistence Diagrams and Homology
Preservation under Dimension Reduction
- Title(参考訳): 次元減少下における恒常化ボトルネック距離の持続図とホモロジー保存
- Authors: Bala Krishnamoorthy and Nathan H. May
- Abstract要約: 我々は、正規化ボトルネック距離(d_N)と呼ばれる永続化ダイアグラム間の新しいスケール不変距離を定義する。
ジョンソン・リンデンシュトラウス(JL)投射とメートル法多次元スケーリング(mMDS)の2つの一般的な次元縮小手法について検討する。
我々は、これらの次元還元技術が d_N に関してホモロジーをいかに保存するかの新しい境界を提供する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Persistence diagrams are used as signatures of point cloud data assumed to be
sampled from manifolds, and represent their topology in a compact fashion.
Further, two given clouds of points can be compared by directly comparing their
persistence diagrams using the bottleneck distance, d_B. But one potential
drawback of this pipeline is that point clouds sampled from topologically
similar manifolds can have arbitrarily large d_B values when there is a large
degree of scaling between them. This situation is typical in dimension
reduction frameworks that are also aiming to preserve topology.
We define a new scale-invariant distance between persistence diagrams termed
normalized bottleneck distance, d_N, and study its properties. In defining d_N,
we also 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 associated 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 persistence diagram of X, and 0 < e < 1 is the tolerance
up to which pairwise distances are preserved by f. For mMDS, we present new
bounds for both d_B and d_N between persistence diagrams 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).
- Abstract(参考訳): 永続化図は、多様体からサンプリングされると思われる点雲データのシグネチャとして使われ、そのトポロジーをコンパクトに表現する。
さらに、ボトルネック距離d_Bを用いて、それらの永続化図を直接比較することにより、2つの与えられた点の雲を比較することができる。
しかし、このパイプラインの潜在的な欠点の一つは、トポロジカルに類似した多様体からサンプリングされた点雲は、その間に大きなスケーリングがあるときに、任意に大きなd_B値を持つことができることである。
この状況は、トポロジーの保存も目指している次元縮小フレームワークで典型的である。
正規化ボトルネック距離(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 のヴィートリス・リップス永続図式であり、0 < e < 1 は f によって対距離が保存されるトレランスであることを示す。
mMDS に対して、X の持続図形とその射影の間の d_B と d_N の新たな境界を共分散行列の固有値の観点から提示する。
また、k-biLipschitz写像に対して、d_N は (k^2-1)/k の積と X と f(X) の直径の比で有界であることを示す。
関連論文リスト
- Sampling and estimation on manifolds using the Langevin diffusion [48.898189211250234]
離散化マルコフ過程に基づく$mu_phi $の線形汎函数の2つの推定器を検討する。
誤差境界は、本質的に定義されたランゲヴィン拡散の離散化を用いてサンプリングと推定のために導出される。
論文 参考訳(メタデータ) (2023-12-22T18:01:11Z) - Scaling Riemannian Diffusion Models [68.52820280448991]
非自明な多様体上の高次元タスクにスケールできることを示す。
我々は、$SU(n)$格子上のQCD密度と高次元超球面上の対照的に学習された埋め込みをモデル化する。
論文 参考訳(メタデータ) (2023-10-30T21:27:53Z) - Implicit Bias of Gradient Descent for Logistic Regression at the Edge of
Stability [69.01076284478151]
機械学習の最適化において、勾配降下(GD)はしばしば安定性の端(EoS)で動く
本稿では,EoS系における線形分離可能なデータに対するロジスティック回帰のための定数段差GDの収束と暗黙バイアスについて検討する。
論文 参考訳(メタデータ) (2023-05-19T16:24:47Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。