Extrapolation methods for fixed‐point multilinear PageRank computations
From MaRDI portal
Abstract: Nonnegative tensors arise very naturally in many applications that involve large and complex data flows. Due to the relatively small requirement in terms of memory storage and number of operations per step, the (shifted) higher-order power method is one of the most commonly used technique for the computation of positive Z-eigenvectors of this type of tensors. However, unlike the matrix case, the method may fail to converge even for irreducible tensors. Moreover, when it converges, its convergence rate can be very slow. These two drawbacks often make the computation of the eigenvectors demanding or unfeasible for large problems. In this work we consider a particular class of nonnegative tensors associated to the multilinear PageRank modification of higher-order Markov chains. Based on the simplified topological -algorithm in its restarted form, we introduce an extrapolation-based acceleration of power method type algorithms, namely the shifted fixed-point method and the inner-outer method. The accelerated methods show remarkably better performance, with faster convergence rates and reduced overall computational time. Extensive numerical experiments on synthetic and real-world datasets demonstrate the advantages of the introduced extrapolation techniques.
Recommendations
- A continuation method for computing the multilinear PageRank
- Vector Aitken extrapolation method for multilinear PageRank computations
- Extrapolation methods for PageRank computations
- Convergence of the fixed‐point iteration for multilinear PageRank
- Perron-based algorithms for the multilinear PageRank
- A new extrapolation method for PageRank computations
- An extrapolation iteration and its lumped type iteration for computing PageRank
- Vector extrapolation methods with applications to solution of large systems of equations and to PageRank computations
- Multilinear PageRank: uniqueness, error bound and perturbation analysis
- An Arnoldi-extrapolation algorithm for computing pagerank
Cited in
(19)- The genesis and early developments of Aitken's process, Shanks' transformation, the \(\varepsilon\)-algorithm, and related fixed point methods
- Extrapolation methods for PageRank computations
- A survey of Shanks' extrapolation methods and their applications
- An extrapolation iteration and its lumped type iteration for computing PageRank
- Acceleration of the generalized FOM algorithm for computing PageRank
- Vector Aitken extrapolation method for multilinear PageRank computations
- Nonlocal pagerank
- Ergodicity Coefficients for Higher-Order Stochastic Processes
- A residual-based error bound for the multilinear PageRank vector
- Matrix Shanks transformations
- Higher Order Extended Dynamic Mode Decomposition Based on the Structured Total Least Squares
- Multi-linear pseudo-PageRank for hypergraph partitioning
- Truncated and sparse power methods with partially updating for large and sparse higher-order PageRank problems
- Improved uniqueness conditions of solution for multilinear pagerank and its application
- HOSVD-TMPE: an extrapolation method for multidimensional sequences
- The MFPIO iteration and the FPMPE method for multilinear PageRank computations
- Extrapolation methods for multilinear PageRank
- Accelerating the computation of tensor Z-eigenvalues
- Spliting iteration method for solving multilinear PageRank problem
This page was built for publication: Extrapolation methods for fixed‐point multilinear PageRank computations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5218989)
