Near-linear convergence of the random Osborne algorithm for matrix balancing

DOI10.1007/s10107-022-01825-4OpenAlexW3181224955MaRDI QIDQ2687049

Pablo A. Parrilo, Jason M. Altschuler

Publication date: 1 March 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.02837

zbMATH Keywords

convex optimizationcoordinate descentmatrix balancingnear-linear timeOsborne's algorithmrandom Osborne

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Convex programming (90C25) Preconditioners for iterative methods (65F08)

Related Items

Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory

Uses Software

• LAPACK
• EISPACK
• expm
• eig
• MATLAB expm
• balance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On complexity of matrix scaling
• Balancing sparse matrices for computing eigenvalues
• Worst-case complexity of cyclic coordinate descent: \(O(n^2)\) gap with randomized version
• Coordinate descent algorithms
• Balancing a matrix for calculation of eigenvalues and eigenvectors
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Efficiency of the Accelerated Coordinate Descent Method on Structured Optimization Problems
• On Pre-Conditioning of Matrices
• Max-Balancing Weighted Directed Graphs and Matrix Scaling
• A Comparative Study of Algorithms for Matrix Balancing
• Line-sum-symmetric scalings of square nonnegative matrices
• LAPACK Users' Guide
• The Complexity of Near-Optimal Graph Coloring
• Numerical Computation of the Matrix Exponential with Accuracy Estimate
• Scaling Matrices to Prescribed Row and Column Maxima
• On the Complexity of Matrix Balancing
• Matrix Balancing in L_p Norms: Bounding the Convergence Rate of Osborne's Iteration
• Analysis of a Classical Matrix Preconditioning Algorithm
• Reducibility among Combinatorial Problems
• Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• The Scaling and Squaring Method for the Matrix Exponential Revisited
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
• Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
• Depth-First Search and Linear Graph Algorithms
• Faster parametric shortest path and minimum‐balance algorithms
• Random permutations fix a worst case for cyclic coordinate descent
• Probability
• Encyclopedia of Distances