Suche nach Personen

plus im Publikationsserver
plus bei BASE
plus bei Google Scholar

Daten exportieren


Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate


Verfügbarkeit überprüfen

Kümmerle, Christian ; Mayrink Verdun, Claudio ; Stöger, Dominik:
Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate.
In: Advances in Neural Information Processing Systems 34 (NeurIPS 2021). - 2021



The recovery of sparse data is at the core of many applications in machine learning and signal processing. While such problems can be tackled using l1-regularization as in the LASSO estimator and in the Basis Pursuit approach, specialized algorithms are typically required to solve the corresponding high-dimensional non-smooth optimization for large instances.Iteratively Reweighted Least Squares (IRLS) is a widely used algorithm for this purpose due to its excellent numerical performance. However, while existing theory is able to guarantee convergence of this algorithm to the minimizer, it does not provide a global convergence rate. In this paper, we prove that a variant of IRLS converges \emph{with a global linear rate} to a sparse solution, i.e., with a linear error decrease occurring immediately from any initialization if the measurements fulfill the usual null space property assumption. We support our theory by numerical experiments showing that our linear rate captures the correct dimension dependence. We anticipate that our theoretical findings will lead to new insights for many other use cases of the IRLS algorithm, such as in low-rank matrix recovery.

Weitere Angaben

Publikationsform:Aufsatz in einem Buch
Zusätzliche Informationen:(Spotlight paper)
Sprache des Eintrags:Englisch
Institutionen der Universität:Mathematisch-Geographische Fakultät > Mathematik > Juniorprofessur für Data Science
Weitere URLs:
Open Access: Freie Zugänglichkeit des Volltexts?:Ja
Begutachteter Aufsatz:Ja
Titel an der KU entstanden:Ja
Eingestellt am: 03. Mai 2022 15:00
Letzte Änderung: 09. Mai 2022 14:13
URL zu dieser Anzeige:
AnalyticsGoogle Scholar