论文标题
随机Osborne算法的接近线性收敛用于基质平衡
Near-linear convergence of the Random Osborne algorithm for Matrix Balancing
论文作者
论文摘要
我们重新审视矩阵平衡，这是一种无处不在用于计算特征值和矩阵指数的预处理任务。自1960年以来，奥斯本（Osborne）的算法一直是从业者的选择算法，现在在大多数数值软件包中实施。但是，其理论属性尚不清楚。在这里，我们表明Osborne算法的简单随机变体在输入稀疏性中在接近线性的时间内收敛。具体而言，它可以平衡$ k \ in \ mathbb {r} _ {\ geq 0}^{n \ times n} $之后$ o（mε^{ - 2} \logκ）$ arithmetic Operations，其中$ m $是$ k $，$ k $，$ε$ \ε$ \ el el_1 $ el el _ ell _ ell_1 $ cecce，并且$κ= \ sum_ {ij} k_ {ij}/（\ min_ {ij：k_ {ij} \ neq 0} k_ {ij}）$测量$ k $的条件。以前的工作仅以$ \ ell_2 $的准确性（一种与应用程序相关的较弱的标准）建立了接近线性的运行时间，或者是基于（当前）不切实际的laplacian solvers的完全不同算法。 我们进一步表明，如果具有邻接矩阵$ k $的图形是中等连接的 - 例如，如果$ k $至少具有一个正排/列对，那么Osborne的算法最初会呈指数级快速收敛，从而产生改进的跑步时间$ O（Mis^{-1}} \ log-κ）$。我们还通过证明使用$ O（\ log（nκ/ε））$ - 比特数字时仍然存在这些运行时边界来解决数值精度。 我们的结果是通过直观的潜在论点确定的，该论点利用了Osborne算法的凸优化视角，并将触及卷的进展与Hellinger距离所测量的当前不平衡联系起来。与以前的分析不同，我们严重利用电势的对数符号性。我们的分析扩展到Osborne算法的其他变体：在此过程中，我们建立了循环，贪婪和并行变体的运行时界限。
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, its theoretical properties 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}_{\geq 0}^{n\times n}$ after $O(mε^{-2}\logκ)$ arithmetic operations, where $m$ is the number of nonzeros in $K$, $ε$ is the $\ell_1$ accuracy, and $κ=\sum_{ij}K_{ij}/(\min_{ij:K_{ij}\neq 0}K_{ij})$ measures the conditioning of $K$. Previous work had established near-linear runtimes either only for $\ell_2$ 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ε^{-1}\logκ)$. We also address numerical precision by showing that these runtime bounds still hold when using $O(\log(nκ/ε))$-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. Our analysis extends to other variants of Osborne's algorithm: along the way, we establish significantly improved runtime bounds for cyclic, greedy, and parallelized variants.
