English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We revisit Matrix Balancing, a pre-conditioning task used ubiquitously forcomputing eigenvalues and matrix exponentials. Since 1960, Osborne's algorithmhas been the practitioners' algorithm of choice and is now implemented in mostnumerical software packages. However, its theoretical properties are not wellunderstood. Here, we show that a simple random variant of Osborne's algorithmconverges in near-linear time in the input sparsity. Specifically, it balances$K\in\mathbb{R}_{\geq 0}^{n\times n}$ after $O(m\epsilon^{-2}\log\kappa)$arithmetic operations, where $m$ is the number of nonzeros in $K$, $\epsilon$is the $\ell_1$ accuracy, and $\kappa=\sum_{ij}K_{ij}/(\min_{ij:K_{ij}\neq0}K_{ij})$ measures the conditioning of $K$. Previous work had establishednear-linear runtimes either only for $\ell_2$ accuracy (a weaker criterionwhich is less relevant for applications), or through an entirely differentalgorithm based on (currently) impractical Laplacian solvers.  We further show that if the graph with adjacency matrix $K$ is moderatelyconnected--e.g., if $K$ has at least one positive row/column pair--thenOsborne's algorithm initially converges exponentially fast, yielding animproved runtime $O(m\epsilon^{-1}\log\kappa)$. We also address numericalprecision by showing that these runtime bounds still hold when using$O(\log(n\kappa/\epsilon))$-bit numbers.  Our results are established through an intuitive potential argument thatleverages a convex optimization perspective of Osborne's algorithm, and relatesthe per-iteration progress to the current imbalance as measured in Hellingerdistance. Unlike previous analyses, we critically exploit log-convexity of thepotential. Our analysis extends to other variants of Osborne's algorithm: alongthe way, we establish significantly improved runtime bounds for cyclic, greedy,and parallelized variants.

Near-linear convergence of the Random Osborne algorithm for Matrix Balancing