Iteratively Reweighted Least Squares (IRLS), whose history goes back more than 80 years, represents an important family of algorithms for non-smooth optimization as it is able to optimize these problems by solving a sequence of linear systems. In 2010, Daubechies, DeVore, Fornasier, and G\"unt\"urk proved that IRLS for $\ell_1$-minimization, an optimization program ubiquitous in the field of compressed sensing, globally converges to a sparse solution. While this algorithm has been popular in applications in engineering and statistics, fundamental algorithmic questions have remained unanswered. As a matter of fact, existing convergence guarantees only provide global convergence without any rate, except for the case that the support of the underlying signal has already been identified. In this paper, we prove that IRLS for $\ell_1$-minimization converges to a sparse solution with a global linear rate. We support our theory by numerical experiments indicating that our linear rate essentially captures the correct dimension dependence.

翻译：历史可追溯到80多年的循环加权最低方块(IRLS)是一个重要的非移动优化算法组合,因为它能够通过解决线性系统序列优化这些问题。 2010年,Daubechies、DeVore、Fornasier和G\“unt\'urk”证明,IRLS以$\ell_1$-最小化,一个压缩遥感领域的优化方案无处不在,全球接近于稀薄的解决方案。虽然这一算法在工程和统计应用中很受欢迎,但基本算法问题仍未得到解决。事实上,现有的趋同保证只提供全球趋同,而没有任何速度,但基本信号的支持已经确定的情况除外。在这份文件中,我们证明,$\ell_1$-最小化的IRLS与全球线性率的稀薄解决方案一致。我们通过数字实验支持我们的理论,表明我们的线性率基本上可以捕捉到正确的维度依赖性。