論文の概要: Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model

• arxiv url: http://arxiv.org/abs/2509.13112v1
• Date: Tue, 16 Sep 2025 14:13:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-17 17:50:53.120971
• Title: Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model
• Title（参考訳）: 対角線支配系のサブ線形時間アルゴリズムとFriedkin-Johnsenモデルへの応用
• Authors: Weiming Feng, Zelin Li, Pan Peng,
• Abstract要約: 線形系を解くための準線形時間アルゴリズムについて研究し、$Sz = b$, ここでは$S$は対角的に支配的な行列である。 任意の$u in [n]$に対して、加算誤差のある$z_u$ of $z*_u$を返します。 また、一致する下界を証明し、$S_max$ に対する線型依存が最適であることを示す。
• 参考スコア（独自算出の注目度）: 5.101318208537081
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study sublinear-time algorithms for solving linear systems $Sz = b$, where $S$ is a diagonally dominant matrix, i.e., $|S_{ii}| \geq \delta + \sum_{j \ne i} |S_{ij}|$ for all $i \in [n]$, for some $\delta \geq 0$. We present randomized algorithms that, for any $u \in [n]$, return an estimate $z_u$ of $z^*_u$ with additive error $\varepsilon$ or $\varepsilon \lVert z^*\rVert_\infty$, where $z^*$ is some solution to $Sz^* = b$, and the algorithm only needs to read a small portion of the input $S$ and $b$. For example, when the additive error is $\varepsilon$ and assuming $\delta>0$, we give an algorithm that runs in time $O\left( \frac{\|b\|_\infty^2 S_{\max}}{\delta^3 \varepsilon^2} \log \frac{\| b \|_\infty}{\delta \varepsilon} \right)$, where $S_{\max} = \max_{i \in [n]} |S_{ii}|$. We also prove a matching lower bound, showing that the linear dependence on $S_{\max}$ is optimal. Unlike previous sublinear-time algorithms, which apply only to symmetric diagonally dominant matrices with non-negative diagonal entries, our algorithm works for general strictly diagonally dominant matrices ($\delta > 0$) and a broader class of non-strictly diagonally dominant matrices $(\delta = 0)$. Our approach is based on analyzing a simple probabilistic recurrence satisfied by the solution. As an application, we obtain an improved sublinear-time algorithm for opinion estimation in the Friedkin--Johnsen model.
• Abstract（参考訳）: Sz = b$, ここで$S$は対角的に支配的な行列、すなわち$|S_{ii}| \geq \delta + \sum_{j \ne i} |S_{ij}|$ for all $i \in [n]$, for some $\delta \geq 0$である。 任意の$u \in [n]$に対して、$z_u$ of $z^*_u$ with additive error $\varepsilon$ or $\varepsilon \lVert z^*\rVert_\infty$を返します。 例えば、加法誤差が$\varepsilon$で$\delta>0$と仮定すると、$O\left( \frac{\|b\|_\infty^2 S_{\max}}{\delta^3 \varepsilon^2} \log \frac{\| b \|_\infty}{\delta \varepsilon} \right)$である。 また、一致する下界を証明し、$S_{\max}$に対する線型依存が最適であることを示す。 非負の対角成分を持つ対称対角行列のみに適用される従来の準線形時間アルゴリズムとは異なり、我々のアルゴリズムは一般に厳密な対角行列(\delta > 0$)と、非対称対角行列のより広いクラス$(\delta = 0)$に対して機能する。 提案手法は,本法で満たされた単純な確率的再帰を解析することに基づく。 応用として、Friedkin-Johnsenモデルにおける意見推定のための改良されたサブ線形時間アルゴリズムを得る。

関連論文リスト

• Phase transition of the Sinkhorn-Knopp algorithm [8.271753306351684]
  Sinkhorn-Knoppアルゴリズムは$O(log n - log varepsilon)$と$widetildeO(n2)$timeでほぼ2倍の行列を生成する。 すべての$gamma 1/2$に対して、密度$gammaを持つ行列が存在し、アルゴリズムは$Omegaleft(n1/2/varepsilonright)$ iterationsを必要とする。
  論文  参考訳（メタデータ） (2025-07-13T17:07:51Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  我々は注意問題のスパシフィケーションを考慮する。 超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
  論文  参考訳（メタデータ） (2023-04-10T05:52:38Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
  論文  参考訳（メタデータ） (2020-05-22T16:55:01Z)

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

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