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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we study matrix scaling and balancing, which are fundamentalproblems in scientific computing, with a long line of work on them that datesback to the 1960s. We provide algorithms for both these problems that, ignoringlogarithmic factors involving the dimension of the input matrix and the size ofits entries, both run in time $\widetilde{O}\left(m\log \kappa \log^2(1/\epsilon)\right)$ where $\epsilon$ is the amount of error we are willing totolerate. Here, $\kappa$ represents the ratio between the largest and thesmallest entries of the optimal scalings. This implies that our algorithms runin nearly-linear time whenever $\kappa$ is quasi-polynomial, which includes, inparticular, the case of strictly positive matrices. We complement our resultsby providing a separate algorithm that uses an interior-point method and runsin time $\widetilde{O}(m^{3/2} \log (1/\epsilon))$.  In order to establish these results, we develop a new second-orderoptimization framework that enables us to treat both problems in a unified andprincipled manner. This framework identifies a certain generalization of linearsystem solving that we can use to efficiently minimize a broad class offunctions, which we call second-order robust. We then show that in the contextof the specific functions capturing matrix scaling and balancing, we canleverage and generalize the work on Laplacian system solving to make thealgorithms obtained via this framework very efficient.

Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods