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

The recovery of sparse data is at the core of many applications in machinelearning and signal processing. While such problems can be tackled using$\ell_1$-regularization as in the LASSO estimator and in the Basis Pursuitapproach, specialized algorithms are typically required to solve thecorresponding high-dimensional non-smooth optimization for large instances.Iteratively Reweighted Least Squares (IRLS) is a widely used algorithm for thispurpose due its excellent numerical performance. However, while existing theoryis able to guarantee convergence of this algorithm to the minimizer, it doesnot provide a global convergence rate. In this paper, we prove that a variantof IRLS converges with a global linear rate to a sparse solution, i.e., with alinear error decrease occurring immediately from any initialization, if themeasurements fulfill the usual null space property assumption. We support ourtheory by numerical experiments showing that our linear rate captures thecorrect dimension dependence. We anticipate that our theoretical findings willlead to new insights for many other use cases of the IRLS algorithm, such as inlow-rank matrix recovery.

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