論文の概要: Efficient Sparsification of Simplicial Complexes via Local Densities of States

• arxiv url: http://arxiv.org/abs/2502.07558v2
• Date: Mon, 06 Oct 2025 11:39:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 14:28:09.362536
• Title: Efficient Sparsification of Simplicial Complexes via Local Densities of States
• Title（参考訳）: 状態の局所密度による単純コンプレックスの効率的なスペーシング
• Authors: Anton Savostianov, Michael T. Schaub, Nicola Guglielmi, Francesco Tudisco,
• Abstract要約: Simplicial Complex (SC) は、複雑なデータを分析するための一般的な抽象化となっている。 本研究では,状態の局所密度を用いたSCの確率的スパーシフィケーションのための新しい手法を開発した。 ビエトリス族上での我々のフレームワークの性能を実証する。
• 参考スコア（独自算出の注目度）: 18.733437653246543
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Simplicial complexes (SCs) have become a popular abstraction for analyzing complex data using tools from topological data analysis or topological signal processing. However, the analysis of many real-world datasets often leads to dense SCs, with many higher-order simplicies, which results in prohibitive computational requirements in terms of time and memory consumption. The sparsification of such complexes is thus of broad interest, i.e., the approximation of an original SC with a sparser surrogate SC (with typically only a log-linear number of simplices) that maintains the spectrum of the original SC as closely as possible. In this work, we develop a novel method for a probabilistic sparsification of SCs that uses so-called local densities of states. Using this local densities of states, we can efficiently approximate so-called generalized effective resistance of each simplex, which is proportional to the required sampling probability for the sparsification of the SC. To avoid degenerate structures in the spectrum of the corresponding Hodge Laplacian operators, we suggest a ``kernel-ignoring'' decomposition to approximate the sampling probability. Additionally, we utilize certain error estimates to characterize the asymptotic algorithmic complexity of the developed method. We demonstrate the performance of our framework on a family of Vietoris--Rips filtered simplicial complexes.
• Abstract（参考訳）: Simplicial Complex (SC) は、トポロジカルデータ分析やトポロジカル信号処理のツールを用いて複雑なデータを分析するための一般的な抽象化となっている。 しかし、多くの実世界のデータセットの分析は、しばしば高階の単純化を伴う密集したSCにつながり、時間とメモリ消費の観点から計算上の要求が禁止される。 このような錯体のスパシフィケーションは広い関心を集めており、すなわち、元のSCのスペクトルを可能な限り密に維持するスペーサーサロゲートSC(通常、対数線数のみ)との近似である。 本研究では,状態の局所密度を用いたSCの確率的スパーシフィケーションのための新しい手法を開発した。 この局所的な状態密度を用いることで、SCのスパース化に必要なサンプリング確率に比例する、各単純体のいわゆる一般化有効抵抗を効率的に近似することができる。 対応するホッジラプラシア作用素のスペクトルにおける退化構造を避けるために、サンプリング確率を近似するために ``カーネル無視' 分解を提案する。 さらに,提案手法の漸近的アルゴリズム的複雑性を特徴付けるために,特定の誤差推定値を利用する。 ビエトリス族上での我々のフレームワークの性能を実証する。

関連論文リスト

• Frequency-domain alignment of heterogeneous, multidimensional separations data through complex orthogonal Procrustes analysis [0.0]
  多次元分離データには、複雑な生物学的サンプルに関する詳細な情報を明らかにする能力がある。 データ分析は、化学因子を表わすピークが、いくつかの分析実行の過程で漂流する可能性があるため、この分野で進行中の課題である。 この研究は、合成多次元分離データの周波数領域表現のProcrustes解析を通じて、アライメント問題に対する非常に単純な解を提供する。
  論文  参考訳（メタデータ） (2025-02-18T12:14:14Z)
• Discovering physical laws with parallel combinatorial tree search [57.05912962368898]
  記号回帰は、データから簡潔で解釈可能な数学的表現を発見する能力のおかげで、科学研究において重要な役割を果たす。 既存のアルゴリズムは10年以上にわたって精度と効率の重大なボトルネックに直面してきた。 制約データから汎用数学的表現を効率的に抽出する並列木探索(PCTS)モデルを提案する。
  論文  参考訳（メタデータ） (2024-07-05T10:41:15Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Generalized Simplicial Attention Neural Networks [22.171364354867723]
  我々はGSAN(Generalized Simplicial Attention Neural Networks)を紹介する。 GSANは、マスク付き自己意図層を用いて、単純な複合体に生きるデータを処理する。 これらのスキームは、タスク指向の方法で、連続した順序の隣り合う単純さに関連するデータを組み合わせる方法を学ぶ。
  論文  参考訳（メタデータ） (2023-09-05T11:29:25Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• 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)
• Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning [81.1071978288003]
  特に,情報理論の原理を用いて,反復型SSLアルゴリズムのエミュレータ一般化誤差の振る舞いを理解することを目的とする。 我々の理論的結果は、クラス条件分散があまり大きくない場合、一般化誤差の上限は反復数とともに単調に減少するが、すぐに飽和することを示している。
  論文  参考訳（メタデータ） (2021-10-03T05:38:49Z)
• Self-paced Principal Component Analysis [17.333976289539457]
  本稿では,SPCA (Self-paced PCA) と呼ばれる新しい手法を提案する。 各サンプルの複雑さは、単純からより複雑なサンプルをトレーニングに統合するために、各イテレーションの開始時に計算されます。
  論文  参考訳（メタデータ） (2021-06-25T20:50:45Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。 我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
  論文  参考訳（メタデータ） (2020-11-17T05:41:50Z)
• Sparse Generalized Canonical Correlation Analysis: Distributed Alternating Iteration based Approach [18.93565942407577]
  Sparse Canonical correlation analysis (CCA) はスパース構造を用いた潜伏情報検出に有用な統計ツールである。 本稿では,多視点データとスパース構造との潜在関係を検出可能な一般標準相関解析(GCCA)を提案する。
  論文  参考訳（メタデータ） (2020-04-23T05:53:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。