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

We give a stochastic optimization algorithm that solves a dense $n\times n$real-valued linear system $Ax=b$, returning $\tilde x$ such that $\|A\tildex-b\|\leq \epsilon\|b\|$ in time: $$\tildeO((n^2+nk^{\omega-1})\log1/\epsilon),$$ where $k$ is the number of singularvalues of $A$ larger than $O(1)$ times its smallest positive singular value,$\omega < 2.372$ is the matrix multiplication exponent, and $\tilde O$ hides apoly-logarithmic in $n$ factor. When $k=O(n^{1-\theta})$ (namely, $A$ has aflat-tailed spectrum, e.g., due to noisy data or regularization), this improveson both the cost of solving the system directly, as well as on the cost ofpreconditioning an iterative method such as conjugate gradient. In particular,our algorithm has an $\tilde O(n^2)$ runtime when $k=O(n^{0.729})$. We furtheradapt this result to sparse positive semidefinite matrices and least squaresregression.  Our main algorithm can be viewed as a randomized block coordinate descentmethod, where the key challenge is simultaneously ensuring good convergence andfast per-iteration time. In our analysis, we use theory of majorization forelementary symmetric polynomials to establish a sharp convergence guaranteewhen coordinate blocks are sampled using a determinantal point process. We thenuse a Markov chain coupling argument to show that similar convergence can beattained with a cheaper sampling scheme, and accelerate the block coordinatedescent update via matrix sketching.

Solving Dense Linear Systems Faster than via Preconditioning