論文の概要: Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection
- arxiv url: http://arxiv.org/abs/2010.13179v2
- Date: Thu, 18 Feb 2021 15:53:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-03 05:16:33.668378
- Title: Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection
- Title（参考訳）: 反復GLASSOと投影によるK固有ベクトルによるスパースグラフラプラシアン学習
- Authors: Saghar Bagheri, Gene Cheung, Antonio Ortega, Fen Wang
- Abstract要約: グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 58.5350491065936
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Learning a suitable graph is an important precursor to many graph signal
processing (GSP) pipelines, such as graph spectral signal compression and
denoising. Previous graph learning algorithms either i) make some assumptions
on connectivity (e.g., graph sparsity), or ii) make simple graph edge
assumptions such as positive edges only. In this paper, given an empirical
covariance matrix $\bar{C}$ computed from data as input, we consider a
structural assumption on the graph Laplacian matrix $L$: the first $K$
eigenvectors of $L$ are pre-selected, e.g., based on domain-specific criteria,
such as computation requirement, and the remaining eigenvectors are then
learned from data. One example use case is image coding, where the first
eigenvector is pre-chosen to be constant, regardless of available observed
data. We first prove that the subspace of symmetric positive semi-definite
(PSD) matrices $H_{u}^+$ with the first $K$ eigenvectors being $\{u_k\}$ in a
defined Hilbert space is a convex cone. We then construct an operator to
project a given positive definite (PD) matrix $L$ to $H_{u}^+$, inspired by the
Gram-Schmidt procedure. Finally, we design an efficient hybrid graphical
lasso/projection algorithm to compute the most suitable graph Laplacian matrix
$L^* \in H_{u}^+$ given $\bar{C}$. Experimental results show that given the
first $K$ eigenvectors as a prior, our algorithm outperforms competing graph
learning schemes using a variety of graph comparison metrics.
- Abstract（参考訳）: 適切なグラフを学習することは、グラフのスペクトル信号圧縮やノイズ除去など、多くのグラフ信号処理(gsp)パイプラインの重要な前駆体である。
以前のグラフ学習アルゴリズムも
一 接続性(例えば、グラフ空間)についていくつかの仮定をする、又は
二 正の辺のような単純なグラフエッジの仮定をすること。
本稿では、データから計算された経験的共分散行列$\bar{C}$が入力として与えられると、グラフ上の構造的仮定であるラプラシア行列$L$:$L$の最初の$K$固有ベクトルは、例えば、計算要求のようなドメイン固有の基準に基づいて事前選択され、残りの固有ベクトルはデータから学習される。
例えば、画像符号化では、観測可能なデータに関係なく、最初の固有ベクトルが定数である。
最初に、対称正半定値(PSD)行列の部分空間が$H_{u}^+$であり、定義されたヒルベルト空間における最初の$K$固有ベクトルが$\{u_k\}$であることを証明する。
次に、グラムシュミット法に触発されて与えられた正定値(pd)行列を l$ から $h_{u}^+$ に投影する演算子を構築する。
最後に、最も適切なグラフであるラプラシア行列 $L^* \in H_{u}^+$ $\bar{C}$ を計算するために、効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
実験結果から,最初の$K$固有ベクトルが先行して与えられた場合,アルゴリズムは様々なグラフ比較指標を用いて,競合するグラフ学習方式よりも優れていた。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - Compressive Recovery of Sparse Precision Matrices [5.557600489035657]
我々は,$d$変数の統計的関係を,mathbbRn times d$の$n$サンプル$Xのデータセットからモデル化するグラフの学習問題を考察する。
サイズ $m=Omegaleft((d+2k)log(d)right)$ ここで、$k$は基礎となるグラフのエッジの最大数である。
本稿では, グラフィカルラッソに基づく反復アルゴリズムを用いて, 具体的デノイザとみなす実用的リカバリを実現する可能性について検討する。
論文 参考訳（メタデータ） (2023-11-08T13:29:08Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Sign and Basis Invariant Networks for Spectral Graph Representation
Learning [75.18802152811539]
SignNetとBasisNetは、すべての必須対称性に不変な新しいニューラルアーキテクチャであり、したがって、原則化された方法で固有空間のコレクションを処理する。
我々のネットワークは理論的にはグラフ表現学習に強い -- 任意のスペクトルグラフ畳み込みを近似することができる。
実験により、スペクトルグラフフィルタの学習とグラフ位置エンコーディングの学習のためのネットワークの強みが示された。
論文 参考訳（メタデータ） (2022-02-25T23:11:59Z) - Fast Computation of Generalized Eigenvectors for Manifold Graph
Embedding [38.902986549367434]
我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。
我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
論文 参考訳（メタデータ） (2021-12-15T03:45:39Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment [46.145969174332485]
プロジェクションフリーの高速な一般メトリック学習フレームワークを提案する。
距離あたりの線形制約が考えられるため、距離学習問題におけるPDコーン制約を置き換える。
実験により,我々のグラフ距離の最適化はコーン射影方式よりもはるかに高速であることが示された。
論文 参考訳（メタデータ） (2020-06-15T23:15:12Z) - Graph Metric Learning via Gershgorin Disc Alignment [46.145969174332485]
そこで,MathcalS$ の目的 $min_textbfM は計量行列 $textbfM$ の凸微分可能な関数である。
Gershgorinディスクは、最初のeigenvector $textbfv$ of $textbfM$を使って完全に整列可能であることを証明します。
実験により, グラフ距離行列の計算効率は, 競合手法を用いて学習した指標よりも優れていた。
論文 参考訳（メタデータ） (2020-01-28T17:44:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。