提出快速求解对角占优线性系统的算法，可用于高效估算群体意见演化。
Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model
- 基于概率递推关系分析，设计随机化子线性时间算法
- 误差控制在ε内，运行时间与矩阵最大元成正比，且为最优
- 适用于一般对角占优矩阵，可加速社会网络意见模型计算
我们研究求解线性系统 $Sz = b$ 的子线性时间算法，其中 $S$ 为对角占优矩阵，即对所有 $i \in [n]$ 满足 $|S_{ii}| \geq δ + \sum_{j \ne i} |S_{ij}|$，$δ \geq 0$。我们提出随机算法，对任意 $u \in [n]$ 返回 $z^*_u$ 的估计值 $z_u$，误差为 $\varepsilon$ 或 $\varepsilon \lVert z^* \rVert_\infty$，且仅需读取输入 $S$ 和 $b$ 的一小部分。当误差为 $\varepsilon$ 且 $δ > 0$ 时，算法运行时间为 $O\left( \frac{\|b\|_\infty^2 S_{ ext{max}}}{δ^3 \varepsilon^2} \log \frac{\| b \|_\infty}{δ\varepsilon} \right)$，其中 $S_{\text{max}} = \max_{i \in [n]} |S_{ii}|$。我们还证明了该界是紧的，表明 $S_{\text{max}}$ 的线性依赖是最优的。与以往仅适用于对称对角占优矩阵（非负对角）的算法不同，本方法适用于一般严格对角占优矩阵（$δ>0$）和更广义的非严格对角占优矩阵（$δ=0$）。其核心思想是分析解所满足的简单概率递推关系。作为应用，我们得到了弗里德金-约翰森模型中意见估计的改进子线性时间算法。
原文摘要 · Abstract (English)
We study sublinear-time algorithms for solving linear systems $Sz = b$, where $S$ is a diagonally dominant matrix, i.e., $|S_{ii}| \geq δ+ \sum_{j \ne i} |S_{ij}|$ for all $i \in [n]$, for some $δ\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 $δ>0$, we give an algorithm that runs in time $O\left( \frac{\|b\|_\infty^2 S_{\max}}{δ^3 \varepsilon^2} \log \frac{\| b \|_\infty}{δ\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 ($δ> 0$) and a broader class of non-strictly diagonally dominant matrices $(δ= 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。