Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model

We study sublinear-time algorithms for solving linear systems Sz = b, where S is a diagonally dominant matrix, i.e., |Sii| ≥ δ + sumj ne i |Sij| for all i ∈ [n], for some δ ≥ 0. We present randomized algorithms that, for any u ∈ [n], return an estimate zu of z^*u with additive error varepsilon or varepsilon lVert z^*rVert_∞, 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 Oleft( frac|b|_∞2 Smaxδ3 varepsilon2 log frac| b |_∞δ varepsilon right), where Smax = maxi ∈ [n] |Sii|. We also prove a matching lower bound, showing that the linear dependence on Smax 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.