論文の概要: Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation

• arxiv url: http://arxiv.org/abs/2606.24011v1
• Date: Mon, 22 Jun 2026 23:33:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 22:16:48.712628
• Title: Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation
• Title（参考訳）: 時空間信号補間のための緩やかな時間変化グラフの低ランク更新
• Authors: Saghar Bagheri, Gene Cheung, Tim Eadie, Antonio Ortega,
• Abstract要約: グラフ信号処理(GSP)における重要な仮定は、ノード間のペアの類似性をキャプチャする基礎となるグラフの存在である。 ノード間類似性が時間とともに変化する時空間データに対して、静的な空間グラフは不十分である。 グラフ変化を2つの連続隣接行列$P = W(2) - W(1)$で低ランク行列としてモデル化する。
• 参考スコア（独自算出の注目度）: 36.25340747048208
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A crucial assumption in graph signal processing (GSP) is the existence of an underlying graph that captures the pairwise similarities between nodes, allowing filters to be designed based on this graph for tasks such as denoising. For spatial-temporal data in which node-to-node similarities evolve over time, a static spatial graph is insufficient. In this paper, to represent slowly time-varying pairwise relationships, we model the graph changes in two consecutive adjacency matrices $P = W^{(2)} - W^{(1)}$ across time as a low-rank matrix. % Specifically, given an initial adjacency matrix $W^{(1)}$ at time $t=1$, we jointly interpolate a signal $x_2$ and estimate $W^{(2)}$ at $t=2$ using both a graph signal smoothness prior for $x_2$ and a low-rank prior on $¶$. We alternate optimization steps. With $W^{(2)}$ fixed, $x_2$ is interpolated by solving a linear system. Alternatively, holding $x_2$ fixed, $W^{(2)}$ is updated via proximal gradient descent (PGD). The proximal mapping of the rank term $Gamma(W^{(2)} - W^{(1)})$ is approximated in linear time using a fast orthogonal matching pursuit (OMP) algorithm that selects a sparse combination of atoms from a dictionary $cR$ formed by the outer products of $W^{(1)}$'s eigenvectors. We unroll iterations of our algorithm into layers to build a lightweight neural network for limited data-driven parameter tuning. Experiments show that our joint optimization achieves better signal interpolation compared to existing time-varying graph models.
• Abstract（参考訳）: グラフ信号処理(GSP)における重要な前提は、ノード間のペアの類似性をキャプチャする基盤となるグラフの存在であり、デノイングのようなタスクのためにこのグラフに基づいてフィルタを設計することができる。 ノード間類似性が時間とともに変化する時空間データに対して、静的な空間グラフは不十分である。 本稿では、時間的に異なるペアワイズ関係を表現するために、2つの連続した隣接行列のグラフ変化を低ランク行列として時間をかけてモデル化する。 具体的には、初期隣接行列 $W^{(1)}$ at at time $t=1$ が与えられたとき、信号 $x_2$ と推定 $W^{(2)}$ at $t=2$ を共同で補間し、$x_2$ に先行するグラフ信号の滑らかさと$=$ に先行する低ランクの両方を用いて、$W^{(2)}$ を推定する。 最適化のステップを交互に行う。 W^{(2)}$固定の場合、$x_2$は線形系を解くことによって補間される。 あるいは、$x_2$を固定すると、$W^{(2)}$は近位勾配降下(PGD)によって更新される。 ランク項 $Gamma(W^{(2)} - W^{(1)})$ の近位写像は、W^{(1)}$ の固有ベクトルの外部積によって形成される辞書 $cR$ から原子のスパース結合を選択する高速直交マッチング追従アルゴリズム (OMP) を用いて線形時間で近似される。 データ駆動型パラメータチューニングを限定する軽量ニューラルネットワークを構築するために,アルゴリズムの繰り返しをレイヤに展開する。 実験の結果,既存の時間変化グラフモデルと比較して,信号補間が優れていることがわかった。

関連論文リスト

• Incremental (k, z)-Clustering on Graphs [2.3322477552758234]
  確率を一定要素近似で高い確率で維持するランダム化インクリメンタル$(k, z)$-clusteringアルゴリズムを開発した。 第1段階では、すべての対向エッジ挿入に対して、総更新時間$m1+o(1)$で、サイズ$tildeO(k)$の定数要素ビクリテリア近似解を維持できる。 第2段階では、バイクリテリア近似解によって誘導される動的重み付きインスタンス上で、定数係数近似$(k,z)$-クラスタリング解を維持する。
  論文  参考訳（メタデータ） (2026-02-09T11:43:10Z)
• Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast [28.36772736512295]
  我々は、混合グラフに基づく最適化アルゴリズムをアンロールすることで、軽量で解釈可能なトランスフォーマーのようなニューラルネットを構築する。 グラフ学習モジュールを$mathcalGu$と$mathcalGd$に挿入します。 実験により,我々の未登録ネットワークは,最先端の予測スキームとして,競争力のあるトラフィック予測性能を達成することが示された。
  論文  参考訳（メタデータ） (2025-05-19T13:32:34Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。 ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。 代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
  論文  参考訳（メタデータ） (2021-06-03T07:22:48Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)

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

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