論文の概要: The decomposition of the higher-order homology embedding constructed
from the $k$-Laplacian
- arxiv url: http://arxiv.org/abs/2107.10970v1
- Date: Fri, 23 Jul 2021 00:40:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-26 14:02:31.094439
- Title: The decomposition of the higher-order homology embedding constructed
from the $k$-Laplacian
- Title（参考訳）: k$-ラプラシアンから構築された高階ホモロジー埋め込みの分解
- Authors: Yu-Chia Chen, Marina Meil\u{a}
- Abstract要約: k$-階ラプラシアン $mathbfmathcal L_k$ の零空間は、多様体やネットワークの非自明な位相を符号化する。
多様体の最も単純な位相成分に対応する部分空間に埋め込まれたホモロジーを分解するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 5.076419064097734
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The null space of the $k$-th order Laplacian $\mathbf{\mathcal L}_k$, known
as the {\em $k$-th homology vector space}, encodes the non-trivial topology of
a manifold or a network. Understanding the structure of the homology embedding
can thus disclose geometric or topological information from the data. The study
of the null space embedding of the graph Laplacian $\mathbf{\mathcal L}_0$ has
spurred new research and applications, such as spectral clustering algorithms
with theoretical guarantees and estimators of the Stochastic Block Model. In
this work, we investigate the geometry of the $k$-th homology embedding and
focus on cases reminiscent of spectral clustering. Namely, we analyze the {\em
connected sum} of manifolds as a perturbation to the direct sum of their
homology embeddings. We propose an algorithm to factorize the homology
embedding into subspaces corresponding to a manifold's simplest topological
components. The proposed framework is applied to the {\em shortest homologous
loop detection} problem, a problem known to be NP-hard in general. Our spectral
loop detection algorithm scales better than existing methods and is effective
on diverse data such as point clouds and images.
- Abstract（参考訳）: k 次ラプラシアン $\mathbf{\mathcal l}_k$ のヌル空間は、多様体やネットワークの非自明な位相を符号化する。
ホモロジー埋め込みの構造を理解することは、データから幾何学的あるいは位相的情報を明らかにすることができる。
グラフ Laplacian $\mathbf{\mathcal L}_0$ の null 空間埋め込みの研究は、理論的な保証を持つスペクトルクラスタリングアルゴリズムや確率ブロックモデルの推定器など、新しい研究や応用を刺激している。
本研究では,k$-thホモロジー埋め込みの幾何学について検討し,スペクトルクラスタリングを想起する事例に注目した。
すなわち、多様体の {\em connected sum} をそれらのホモロジー埋め込みの直和に対する摂動として解析する。
多様体の最も単純な位相成分に対応する部分空間へのホモロジー埋め込みを分解するアルゴリズムを提案する。
提案手法はNP-hardとして一般に知られている最も短い相同ループ検出問題に適用される。
スペクトルループ検出アルゴリズムは既存の手法よりもスケールが良く,点雲や画像などの多様なデータに対して有効である。
関連論文リスト
- Boundary Detection Algorithm Inspired by Locally Linear Embedding [8.259071011958254]
本稿では,広く使用されている局所的線形埋め込みアルゴリズムにインスパイアされた境界点検出手法を提案する。
本手法は,2つの近傍探索スキーム($epsilon$-radius ball scheme)と$K$-nearest neighbor scheme($K$-nearest neighbor scheme)を用いて実装する。
論文 参考訳（メタデータ） (2024-06-26T16:05:57Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Deep Invertible Approximation of Topologically Rich Maps between
Manifolds [17.60434807901964]
位相的に興味深い多様体間の写像を安定に近似できるニューラルネットワークの設計法を示す。
局所ビリプシッツ写像、被覆空間、局所同相写像の間の位相的平行性を利用して、$mathcalT circ p circ MathcalE$ という形の新しいネットワークが局所微分同相の普遍近似器であることが分かる。
また、分子の分子イメージングを対称性で処理するためのアーキテクチャの拡張の可能性についても概説する。
論文 参考訳（メタデータ） (2022-10-02T17:14:43Z) - Subspace clustering in high-dimensions: Phase transitions \&
Statistical-to-Computational gap [24.073221004661427]
部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。
広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
論文 参考訳（メタデータ） (2022-05-26T17:47:35Z) - Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。
単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:59:41Z) - Inferring Manifolds From Noisy Data Using Gaussian Processes [17.166283428199634]
ほとんどの既存の多様体学習アルゴリズムは、元のデータを低次元座標で置き換える。
本稿では,これらの問題に対処するための新しい手法を提案する。
論文 参考訳（メタデータ） (2021-10-14T15:50:38Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文 参考訳（メタデータ） (2021-05-27T23:41:01Z) - Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。
複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。
これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
論文 参考訳（メタデータ） (2021-03-25T14:35:07Z) - Data Structures & Algorithms for Exact Inference in Hierarchical
Clustering [41.24805506595378]
本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。
我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
論文 参考訳（メタデータ） (2020-02-26T17:43:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。