Efficient numerical methods to solve sparse linear equations with application to PageRank
From MaRDI portal
Abstract: In this paper, we propose three methods to solve the PageRank problem for the transition matrices with both row and column sparsity. Our methods reduce the PageRank problem to the convex optimization problem over the simplex. The first algorithm is based on the gradient descent in L1 norm instead of the Euclidean one. The second algorithm extends the Frank-Wolfe to support sparse gradient updates. The third algorithm stands for the mirror descent algorithm with a randomized projection. We proof converges rates for these methods for sparse problems as well as numerical experiments support their effectiveness.
Recommendations
Cites work
- A sublinear-time randomized approximation algorithm for matrix games
- Adaptive methods for the computation of PageRank
- Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
- Clustering with Bregman divergences.
- Complexity bounds for primal-dual methods minimizing the model of objective function
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Convex optimization: algorithms and complexity
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Enhancing sparsity by reweighted \(\ell _{1}\) minimization
- Fast distributed PageRank computation
- Finding the stationary states of Markov chains by iterative methods
- Google's PageRank and beyond. The science of search engine rankings
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Introduction to algorithms.
- Lectures on convex optimization
- Linear coupling: an ultimate unification of gradient and mirror descent
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
- On efficient randomized algorithms for finding the PageRank vector
- On the efficiency of a randomized mirror descent algorithm in online optimization problems
- Prediction, Learning, and Games
- Primal-dual subgradient methods for convex problems
- Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the PageRank problem
- Regularization-based solution of the PageRank problem for large matrices
- Robust Stochastic Approximation Approach to Stochastic Programming
- Subgradient methods for huge-scale optimization problems
- The elements of statistical learning. Data mining, inference, and prediction
- Universal method for stochastic composite optimization problems
Cited in
(5)- Duality gap estimates for weak Chebyshev greedy algorithms in Banach spaces
- Solving Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
- Extended separating plane algorithm and NSO-solutions of PageRank problem
- Weak dangling block reordering and multi-step block compression for efficiently computing and updating PageRank solutions
- Adaptive variants of Frank-Wolfe method with relative inexact gradient information
This page was built for publication: Efficient numerical methods to solve sparse linear equations with application to PageRank
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5043846)
