nach oben

BIT Numerical Mathematics

Erschienen in:

01.12.2015

On the relation between the randomized extended Kaczmarz algorithm and coordinate descent

verfasst von: Bogdan Dumitrescu

Erschienen in: BIT Numerical Mathematics | Ausgabe 4/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this note we compare the randomized extended Kaczmarz (EK) algorithm and randomized coordinate descent (CD) for solving the full-rank overdetermined linear least-squares problem and prove that CD needs fewer operations for satisfying the same residual-related termination criteria. For the general least-squares problems, we show that first running CD to compute the residual and then standard Kaczmarz on the resulting consistent system is more efficient than EK.

Vorheriger Artikel One-sided direct event location techniques in the numerical solution of discontinuous differential systems

Nächster Artikel A posteriori error analysis for finite element methods with projection operators as applied to explicit time integration techniques

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Hanke, M., Niethammer, W.: On the acceleration of Kaczmarzs method for inconsistent linear systems. Linear Algebra Appl. 130, 83–98 (1990)CrossRefMathSciNetMATH

Leventhal, D., Lewis, A.S.: Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res. 35(3), 641–654 (2010)CrossRefMathSciNetMATH

Needell, D.: Randomized Kaczmarz solver for noisy linear systems. BIT Numer. Math. 50, 395–403 (2010)CrossRefMathSciNetMATH

Nesterov, Yu.: Efficiency of coordinate descent methods on huge scale optimization problems. SIAM J. Optim. 22(2), 341–362 (2012)CrossRefMathSciNetMATH

Popa, C.: Least-squares solution of overdetermined inconsistent linear systems using Kaczmarzs relaxation. Int. J. Comput. Math. 55, 79–89 (1995)CrossRefMATH

Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262–278 (2009)CrossRefMathSciNetMATH

Zouzias, A., Freris, N.M.: Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl. 34(2), 773–793 (2013)CrossRefMathSciNetMATH

Titel: On the relation between the randomized extended Kaczmarz algorithm and coordinate descent
verfasst von: Bogdan Dumitrescu
Publikationsdatum: 01.12.2015
Verlag: Springer Netherlands
Erschienen in: BIT Numerical Mathematics / Ausgabe 4/2015
Print ISSN: 0006-3835
Elektronische ISSN: 1572-9125
DOI: https://doi.org/10.1007/s10543-014-0526-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 4/2015

Spectral method for solving high order nonlinear boundary value problems via operational matrices

One-sided direct event location techniques in the numerical solution of discontinuous differential systems

Order conditions for G-symplectic methods

Faster SDC convergence on non-equidistant grids by DIRK sweeps

Local discontinuous Galerkin methods for fractional ordinary differential equations

A type of multi-level correction scheme for eigenvalue problems by nonconforming finite element methods