論文の概要: Spectral Clustering via Orthogonalization-Free Methods
- arxiv url: http://arxiv.org/abs/2305.10356v1
- Date: Tue, 16 May 2023 16:01:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-18 14:52:09.263934
- Title: Spectral Clustering via Orthogonalization-Free Methods
- Title(参考訳): 直交化フリー手法によるスペクトルクラスタリング
- Authors: Qiyuan Pang and Haizhao Yang
- Abstract要約: スペクトルクラスタリングにおける次元性低減に使用されるグラフ信号フィルタは通常、高価な固有値推定を必要とする。
本研究では,スペクトルクラスタリングの次元化として目的関数を最適化し,直交化のない4つの手法を提案する。
提案手法はクラスタリング品質において理想的なグラフ信号フィルタと等価であると数値的に仮定する。
- 参考スコア(独自算出の注目度): 2.995087247817663
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph Signal Filter used as dimensionality reduction in spectral clustering
usually requires expensive eigenvalue estimation. We analyze the filter in an
optimization setting and propose to use four orthogonalization-free methods by
optimizing objective functions as dimensionality reduction in spectral
clustering. The proposed methods do not utilize any orthogonalization, which is
known as not well scalable in a parallel computing environment. Our methods
theoretically construct adequate feature space, which is, at most, a weighted
alteration to the eigenspace of a normalized Laplacian matrix. We numerically
hypothesize that the proposed methods are equivalent in clustering quality to
the ideal Graph Signal Filter, which exploits the exact eigenvalue needed
without expensive eigenvalue estimation. Numerical results show that the
proposed methods outperform Power Iteration-based methods and Graph Signal
Filter in clustering quality and computation cost. Unlike Power Iteration-based
methods and Graph Signal Filter which require random signal input, our methods
are able to utilize available initialization in the streaming graph scenarios.
Additionally, numerical results show that our methods outperform ARPACK and are
faster than LOBPCG in the streaming graph scenarios. We also present numerical
results showing the scalability of our methods in multithreading and
multiprocessing implementations to facilitate parallel spectral clustering.
- Abstract(参考訳): スペクトルクラスタリングの次元減少として用いられるグラフ信号フィルタは通常、高価な固有値推定を必要とする。
最適化条件でフィルタを解析し,スペクトルクラスタリングの次元化として目的関数を最適化し,直交化のない4つの手法を提案する。
提案手法では,並列計算環境ではスケーラビリティが不十分であることが知られている直交化を一切利用しない。
本手法は理論上、正規化されたラプラシアン行列の固有空間への重み付き変更である適切な特徴空間を構築する。
提案手法は, 高価な固有値推定を必要とせず, 正確な固有値を利用する理想的なグラフ信号フィルタと, クラスタリング品質において等価であると仮定した。
数値計算の結果,提案手法はクラスタリングの品質と計算コストにおいて,電力反復法やグラフ信号フィルタよりも優れていた。
ランダムな信号入力を必要とするPower Iteration法やGraph Signal Filterとは異なり,本手法はストリーミンググラフのシナリオで利用可能な初期化を利用できる。
さらに,本手法はストリーミンググラフのシナリオではLOBPCGよりも高速であり,ARPACKよりも高速であることを示す。
また,並列スペクトルクラスタリングを容易にするマルチスレッディングおよびマルチプロセッシング実装における手法のスケーラビリティを示す数値計算結果を示す。
関連論文リスト
- Closed-form Filtering for Non-linear Systems [83.91296397912218]
我々は密度近似と計算効率の面でいくつかの利点を提供するガウスPSDモデルに基づく新しいフィルタのクラスを提案する。
本研究では,遷移や観測がガウスPSDモデルである場合,フィルタリングを効率的にクローズド形式で行うことができることを示す。
提案する推定器は, 近似の精度に依存し, 遷移確率の正則性に適応する推定誤差を伴って, 高い理論的保証を享受する。
論文 参考訳(メタデータ) (2024-02-15T08:51:49Z) - MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion [0.6906005491572401]
スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。
我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。
本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
論文 参考訳(メタデータ) (2023-12-07T06:19:39Z) - Adaptive Graph Convolutional Subspace Clustering [10.766537212211217]
スペクトル型サブスペースクラスタリングアルゴリズムは多くのサブスペースクラスタリングアプリケーションにおいて優れた性能を示している。
本稿では,グラフ畳み込みネットワークにヒントを得たグラフ畳み込み手法を用いて特徴抽出法と係数行列制約を同時に開発する。
AGCSCを用いることで、元のデータサンプルの集合的特徴表現がサブスペースクラスタリングに適していると主張する。
論文 参考訳(メタデータ) (2023-05-05T10:27:23Z) - A Distributed Block Chebyshev-Davidson Algorithm for Parallel Spectral
Clustering [7.632758664232665]
スペクトルクラスタリングにおけるスペクトル解析のための大規模先行固有値問題の解法として,分散Block Chebyshev-Davidsonアルゴリズムを開発した。
チェビシェフ・ダビッドソンアルゴリズムの効率は、推定にコストがかかる固有値スペクトルの事前の知識に依存している。
分散バージョンと並列バージョンは、魅力的なスケーラビリティで開発されている。
論文 参考訳(メタデータ) (2022-12-08T18:06:13Z) - Computational Doob's h-transforms for Online Filtering of Discretely
Observed Diffusions [65.74069050283998]
本研究では,Doobの$h$-transformsを近似する計算フレームワークを提案する。
提案手法は、最先端粒子フィルタよりも桁違いに効率的である。
論文 参考訳(メタデータ) (2022-06-07T15:03:05Z) - An application of the splitting-up method for the computation of a
neural network representation for the solution for the filtering equations [68.8204255655161]
フィルタ方程式は、数値天気予報、金融、工学など、多くの現実の応用において中心的な役割を果たす。
フィルタリング方程式の解を近似する古典的なアプローチの1つは、分割法と呼ばれるPDEにインスパイアされた方法を使うことである。
我々はこの手法をニューラルネットワーク表現と組み合わせて、信号プロセスの非正規化条件分布の近似を生成する。
論文 参考訳(メタデータ) (2022-01-10T11:01:36Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-30T19:17:35Z) - A Manifold Proximal Linear Method for Sparse Spectral Clustering with
Application to Single-Cell RNA Sequencing Data Analysis [9.643152256249884]
本稿では,SSCモデルを非滑らかかつ非客観的な最適化モデルとして広く採用している。
本研究では,従来のSSC問題を解く新しい手法(ManPL)を提案する。
提案手法の結果が得られた。
論文 参考訳(メタデータ) (2020-07-18T22:05:00Z) - Scalable Spectral Clustering with Nystrom Approximation: Practical and
Theoretical Aspects [1.6752182911522515]
本研究は、サンプリングされた点に関連付けられた類似度行列のスペクトル特性を利用して、精度と効率のトレードオフを制御したスペクトルクラスタリングアルゴリズムを提案する。
この研究の包括的な目標は、スペクトルクラスタリングを加速する将来の研究方向のための改善されたベースラインを提供することである。
論文 参考訳(メタデータ) (2020-06-25T15:10:56Z) - Local Graph Clustering with Network Lasso [90.66817876491052]
局所グラフクラスタリングのためのネットワークLasso法の統計的および計算的性質について検討する。
nLassoによって提供されるクラスタは、クラスタ境界とシードノードの間のネットワークフローを通じて、エレガントに特徴付けられる。
論文 参考訳(メタデータ) (2020-04-25T17:52:05Z) - Optimization of Graph Total Variation via Active-Set-based Combinatorial
Reconditioning [48.42916680063503]
本稿では,この問題クラスにおける近位アルゴリズムの適応型事前条件付け手法を提案する。
不活性エッジのネスト・フォレスト分解により局所収束速度が保証されることを示す。
この結果から,局所収束解析は近似アルゴリズムにおける可変指標選択の指針となることが示唆された。
論文 参考訳(メタデータ) (2020-02-27T16:33:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。