Accuracy and componentwise accuracy in multilinear PageRank
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912444609200128 |
|---|---|
| author | Kalyani, Mehdi Najafi Poloni, Federico |
| author_facet | Kalyani, Mehdi Najafi Poloni, Federico |
| contents | We study the stability with respect to perturbations and the accuracy of numerical algorithms for computing solutions to the multilinear PageRank problem $\mathbf{x} = (1-α)\mathbf{v} + α\mathcal{P} \mathbf{x}^2$. Our results reveal that the solution can be more stable with respect to perturbations and numerical errors with respect to the classical bounds for nonlinear systems of equations (based on the norm of the Jacobian). In detail, one can obtain bounds for the minimal solution which ignore the singularity of the problem for $α=1/2$, and one can show that the limiting accuracy of the Newton method depends not on the norm of the Jacobian but on a quantity that can be much smaller thanks to the nonnegativity structure of the equation. For the minimal solution, we also suggest subtraction-free modifications to the existing algorithms to achieve componentwise stability.
Some of the theoretical results we obtain are interesting even outside the scope of this problem: bounds for more general quadratic vector equations, and a partial inverse for M-matrices which remains bounded when the matrix to invert approaches singularity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_18356 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Accuracy and componentwise accuracy in multilinear PageRank Kalyani, Mehdi Najafi Poloni, Federico Numerical Analysis 15A69, 15B51, 65H10 We study the stability with respect to perturbations and the accuracy of numerical algorithms for computing solutions to the multilinear PageRank problem $\mathbf{x} = (1-α)\mathbf{v} + α\mathcal{P} \mathbf{x}^2$. Our results reveal that the solution can be more stable with respect to perturbations and numerical errors with respect to the classical bounds for nonlinear systems of equations (based on the norm of the Jacobian). In detail, one can obtain bounds for the minimal solution which ignore the singularity of the problem for $α=1/2$, and one can show that the limiting accuracy of the Newton method depends not on the norm of the Jacobian but on a quantity that can be much smaller thanks to the nonnegativity structure of the equation. For the minimal solution, we also suggest subtraction-free modifications to the existing algorithms to achieve componentwise stability. Some of the theoretical results we obtain are interesting even outside the scope of this problem: bounds for more general quadratic vector equations, and a partial inverse for M-matrices which remains bounded when the matrix to invert approaches singularity. |
| title | Accuracy and componentwise accuracy in multilinear PageRank |
| topic | Numerical Analysis 15A69, 15B51, 65H10 |
| url | https://arxiv.org/abs/2506.18356 |