Near-linear convergence of the Random Osborne algorithm for Matrix Balancing
研究了随机Osborne算法在矩阵平衡问题中的收敛性，证明其在期望和高概率下以近线性时间收敛，并改进了循环、贪心和并行变体的运行时间界。
Abstract We revisit Matrix Balancing, a pre-conditioning task used ubiquitously for computing eigenvalues and matrix exponentials. Since 1960, Osborne’s algorithm has been the practitioners’ algorithm of choice, and is now implemented in most numerical software packages. However, the theoretical properties of Osborne’s algorithm are not well understood. Here, we show that a simple random variant of Osborne’s algorithm converges in near-linear time in the input sparsity. Specifically, it balances $$K \in {\mathbb {R}}_{\ge 0}^{n \times n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>∈</mml:mo> <mml:msubsup> <mml:mi>R</mml:mi> <mml:mrow> <mml:mo>≥</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msubsup> </mml:mrow> </mml:math> after $$O(m \varepsilon ^{-2} \log \kappa )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:msup> <mml:mi>ε</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>log</mml:mo> <mml:mi>κ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> arithmetic operations in expectation and with high probability, where m is the number of nonzeros in K , $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> is the $$\ell _1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> accuracy, and $$\kappa = \sum _{ij} K_{ij} / ( \min _{ij : K_{ij} \ne 0} K_{ij})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>κ</mml:mi> <mml:mo>=</mml:mo> <mml:msub> <mml:mo>∑</mml:mo> <mml:mrow> <mml:mi>ij</mml:mi> </mml:mrow> </mml:msub> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mi>ij</mml:mi> </mml:mrow> </mml:msub> <mml:mo>/</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mo>min</mml:mo> <mml:mrow> <mml:mi>i</mml:mi> <mml:mi>j</mml:mi> <mml:mo>:</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mi>ij</mml:mi> </mml:mrow> </mml:msub> <mml:mo>≠</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:msub> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mi>ij</mml:mi> </mml:mrow> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> measures the conditioning of K . Previous work had established near-linear runtimes either only for $$\ell _2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> accuracy (a weaker criterion which is less relevant for applications), or through an entirely different algorithm based on (currently) impractical Laplacian solvers. We further show that if the graph with adjacency matrix K is moderately connected—e.g., if K has at least one positive row/column pair—then Osborne’s algorithm initially converges exponentially fast, yielding an improved runtime $$O(m \varepsilon ^{-1} \log \kappa )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:msup> <mml:mi>ε</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>log</mml:mo> <mml:mi>κ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . We also address numerical precision issues by showing that these runtime bounds still hold when using $$O(\log (n\kappa /\varepsilon ))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>κ</mml:mi> <mml:mo>/</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -bit numbers. Our results are established through an intuitive potential argument that leverages a convex optimization perspective of Osborne’s algorithm, and relates the per-iteration progress to the current imbalance as measured in Hellinger distance. Unlike previous analyses, we critically exploit log-convexity of the potential. Notably, our analysis extends to other variants of Osborne’s algorithm: along the way, we also establish significantly improved runtime bounds for cyclic, greedy, and parallelized variants of Osborne’s algorithm.