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

Sketch-and-project is a framework which unifies many known iterative methodsfor solving linear systems and their variants, as well as further extensions tonon-linear optimization problems. It includes popular methods such asrandomized Kaczmarz, coordinate descent, variants of the Newton method inconvex optimization, and others. In this paper, we develop a theoreticalframework for obtaining sharp guarantees on the convergence rate ofsketch-and-project methods. Our approach is the first to: (1) show that theconvergence rate improves at least linearly with the sketch size, and evenfaster when the data matrix exhibits certain spectral decays; and (2) allow forsparse sketching matrices, which are more efficient than dense sketches andmore robust than sub-sampling methods. In particular, our results explain anobserved phenomenon that a radical sparsification of the sketching matrix doesnot affect the per iteration convergence rate of sketch-and-project. To obtainour results, we develop new non-asymptotic spectral bounds for the expectedsketched projection matrix, which are of independent interest; and we establisha connection between the convergence rates of iterative sketch-and-projectsolvers and the approximation error of randomized singular value decomposition,which is a widely used one-shot sketching algorithm for low-rank approximation.Our experiments support the theory and demonstrate that even extremely sparsesketches exhibit the convergence properties predicted by our framework.

Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition