PDF
\(\newcommand{\footnotename}{footnote}\) \(\def \LWRfootnote {1}\) \(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\) \(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\) \(\let \LWRorighspace \hspace \) \(\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }\) \(\newcommand {\mathnormal }[1]{{#1}}\) \(\newcommand \ensuremath [1]{#1}\) \(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \) \(\newcommand {\setlength }[2]{}\) \(\newcommand {\addtolength }[2]{}\) \(\newcommand {\setcounter }[2]{}\) \(\newcommand {\addtocounter }[2]{}\) \(\newcommand {\arabic }[1]{}\) \(\newcommand {\number }[1]{}\) \(\newcommand {\noalign }[1]{\text {#1}\notag \\}\) \(\newcommand {\cline }[1]{}\) \(\newcommand {\directlua }[1]{\text {(directlua)}}\) \(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\) \(\newcommand {\protect }{}\) \(\def \LWRabsorbnumber #1 {}\) \(\def \LWRabsorbquotenumber "#1 {}\) \(\newcommand {\LWRabsorboption }[1][]{}\) \(\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }\) \(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\) \(\def \mathcode #1={\mathchar }\) \(\let \delcode \mathcode \) \(\let \delimiter \mathchar \) \(\def \oe {\unicode {x0153}}\) \(\def \OE {\unicode {x0152}}\) \(\def \ae {\unicode {x00E6}}\) \(\def \AE {\unicode {x00C6}}\) \(\def \aa {\unicode {x00E5}}\) \(\def \AA {\unicode {x00C5}}\) \(\def \o {\unicode {x00F8}}\) \(\def \O {\unicode {x00D8}}\) \(\def \l {\unicode {x0142}}\) \(\def \L {\unicode {x0141}}\) \(\def \ss {\unicode {x00DF}}\) \(\def \SS {\unicode {x1E9E}}\) \(\def \dag {\unicode {x2020}}\) \(\def \ddag {\unicode {x2021}}\) \(\def \P {\unicode {x00B6}}\) \(\def \copyright {\unicode {x00A9}}\) \(\def \pounds {\unicode {x00A3}}\) \(\let \LWRref \ref \) \(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\) \( \newcommand {\multicolumn }[3]{#3}\) \(\require {textcomp}\) \(\newcommand {\intertext }[1]{\text {#1}\notag \\}\) \(\let \Hat \hat \) \(\let \Check \check \) \(\let \Tilde \tilde \) \(\let \Acute \acute \) \(\let \Grave \grave \) \(\let \Dot \dot \) \(\let \Ddot \ddot \) \(\let \Breve \breve \) \(\let \Bar \bar \) \(\let \Vec \vec \)

Optimal accuracy for linear sets of equations with the graph Laplacian

Rich Lehoucq, Jon Berry, Danny Dunlavy, Natalie Wellen & Michael Weylandt

Abstract

An approximate solution \(\hat x\) for a linear set of equations \(L x = b\) has roughly \(d\) digits of accuracy when \(\| \hat x - x\|/\|x\| \approx 10^{-d}\). The classical two-sided inequality

\begin{align} \label {unif-stab} \frac {1}{\kappa (L)} \frac {\|b-L \hat {x} \|}{\|b\|} \leqslant \frac {\| x - \hat {x}\|}{\|x\|} \leqslant \kappa (L) \frac {\|b-L \hat {x} \|}{\|b\|}\quad x,b \neq 0 \end{align} implies that the relative error is norm-equivalent to the relative residual error \(\|b-L \hat {x} \|/\|b\|\) with constants given by the condition number \(\kappa (L)\) and its reciprocal. For us, the matrix \(L\) is a graph Laplacian and the vector \(x\) represents a network centrality measure indicating the importance of the vertices, e.g., the PageRank [1] vector or the vector of mean hitting-times. Unfortunately, the condition number \(\kappa (L)\) increases with graph size or with the PageRank teleportation parameter rendering (1) useless in practice. We establish improved variants of the two-sided inequality and explore their profound computational implications.

We focus our analysis on the relationship between the relative error and the relative residual. This relationship is key to assessing the quality of \(\hat {x}\) because it relates the observable quantity \(\|L\hat {x} -b\|\) with the unobservable quantity \(\|\hat {x} - x\|\). We show that the strength of this relationship is determined by the angle between \(b\) and the vector of all ones on an undirected graph. This relationship is also dependent on the so-called Markov chain discount, a classical concept that we find is equivalent to the PageRank teleportation parameter for undirected graphs. This provides an elegant probabilistic basis for the degree-normalized PageRank variant and the simple characterization of PageRank on an undirected graph sought by Gleich [2, p.356].

Our contributions are twofold: i) we establish a more informative variant of (1) using a data-dependent condition number and ii) we reframe graph centrality measures in the language of discrete potential theory and show how certain potentials can achieve asymptotically optimal accuracy. We discuss the application of these results to PageRank and conclude with numerical simulations highlighting the impact of our improved bounds. We refer the reader to the associated report Optimal accuracy for linear sets of equations with the graph Laplacian available at https://arxiv.org/.

References