Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the Basis Pursuit (BP) optimization problem (minimal l1 norm solution to a linear system).
Iterative Reweighted Least Squares (IRLS) is a majorization minimization algorithm to solve this problem.
The paper shows that it converges *globally* and linearly, under a nullspace property assumption (with parameter <1/2).
Existing results only prove local linear convergence rates, first showing that IRLS identifies the support of the solution, after which the rate becomes linear.
The key is a new update rule for the smoothing parameter used in the majorization of |.| by a scaled Huber function.
Experiments highlight the two regimes : global convergence shown in this paper, followed by a linear convergence with a better rate once the iterate enter a basin of attraction of the solution.


main_review: The paper is well-written, the result is new as far as I know. This problem is of interest to the community, given the impact of L1 based methods on ML and signal/image processing in the last 30 years. As highlighted by the authors in their literature review, there has been a wealth of results on the topic of IRLS published at ML venues in the last years.

Comments:
L32 I don't see how BP can be solved with forwrd backward algorithm, as both terms are non smooth. Perhaps the authors meant primal-dual methods (i.e. Chambolle-Pock) ?
Same goes for ADMM, can you please detail the applicability of this method to BP ? I would say both apply to Lasso, but not to BP.

L115 this function is increasing, no ? at least at 0, the higher epsilon, the higher J_espilon(0). Also in 6, LHS, you use increasingness since e_{k+1} \leq e_{k} by 4, right ?

L127 it holds trivially with v=0, why is it needed to exclude this case ?
The formulation L132 is a bit strange to me, I would put with Ax=y *before* "is the unique solution".

L265 could you point to a more precise location in the Foucart and Rauhut book ?

Fig 1 it seems to me that you encounter numerical errors at iteration 64 1e-10 is the 0 roundoff error compared to 1e6 for float64), I would remove the last point for clarity of the graph (which is already a bit long to parse (but very informative)).
However in Fig 2 the "noisy" aspect of last iterations eems to kick in before numerical errors, can you comment on this aspect?

In Fig1 caption why do you say S_k=S is perfect support identification ? As far as I udnerstood it does not mean that x_k restricted to S^c is 0, no?

L279 can you explicitely state m and s for reproducibility ?

In Lemma B.2 you take S as the set of the largest s entries of x^*, this changes in L596 so can you speecify it  L589 ?

L596 it's epsilon not epsilon_k ?



L78 I would say the complement is with respect to \mathbb{N} not R^N ?
L116, if you have one more page, maybe a 1D graph of L1, scaled huber and Q (for k and k+1, with x_k and x_k+1) can help the reader unfamiliar with this classical MM scheme.
L115 use \mapsto not \to
L171:  obtain an multiplicative
L234 epsilon_k not ^k
several time you put an Upper case after a ":" (eg L272, other occurrences)
L322 you have a broken ref
L473 Darbon not Darbons
L587 has the l_1 -NSP holds.
L587 you use z than x in the proof, maybe you can harmonize 
limitations_and_societal_impact: .
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors study the convergence rate of the Iterative Reweighted Least Square to solve Basis Pursuit. After recalling the existing results and describing the IRLS algorithm with a specific smoothing parameter updates, the authors state their main result showing the global convergence of IRLS under the $\ell_1$-null space property. Finally, some  numerical experiments are presented to corroborate the theoretical results, showing a two stage convergence, one global described by this paper and one local, once the support is identified, which has been studied previously.
main_review: Review Summary
---------------

The paper is clear and well written. The results are correct up to my understanding of the proofs. However, I feel that the results are not really practical (**M1**) and the numerical could be improved (**M2**). Overall, I think this is a correct paper but I would recommend publishing it in an optimization venue, as its interest is mainly theoretical. For these reasons, I would recommend rejection.

Major comments and questions
----------------------------


- **M1:** The results are surprising in the sense that sparse recovery is consider to be a slow task in general, with sub-linear convergence rate (e.g. for ISTA in 1/t). However, the rate proposed in theorem.3.2 seems to be very slow. Indeed, for $\rho = 1/100$, with $N=8000$, we get $(1 - \frac{c}{\rho_1 N})^{1000} \approx 0.98$. Note that this is a favorable scenario for $\rho_1$ value and the value reported in the experiment is around $1/38$. Thus, it seems to me that this bounds are not very practical, and it hides the fact that after a finite number of iteration, the local convergence kicks in with a faster rate. This is a common observation that can be done with ISTA, where linear convergence rate have been proven [A] but are not really observed in practice.

- **M2:** The numerical results do not highlight very well the tighness of the analysis. As the results are presented on synthetic datasets, it would be interesting to compute the constant $\rho_1$ and display the theoretical linear rate with the one obtained in practice. I believe this would show that the proposed rate is not very tight but I might be mistaken. Moreover, showing results on problems smaller scale problems where $\rho_s$ can be computed and highlighting how important this assumption is in practice for the convergence of such algorithm would also improve the case of this paper.

Minor comments, nitpicks and typos
----------------------------------

- **m1:** (*l.78*) I think that $\mathbb R^N$ should be $[N]$ here?

- **m2:** (*l.115*) I think what the authors means is that $\epsilon \to \mathcal J_\epsilon(z)$ is monotonously non-decreasing, and $\epsilon_k$ is non-increasing so $k \to \mathcal J_{\epsilon_k}(z)$ is non-increasing with $k$.

- **m3:** (*l.607*) I don't think the assumption "Moreover, assume that $A$ has the $\ell_1$-NSP of order 1 with constant $\rho_1 < 1$." is necessary in Lemma.B.3 as $\rho_1 \le \rho_s$ no?

- **m4:** I think how you obtain the last line in equation block bellow *l.631* could be clarified. It indeed comes from the fact that $Ax^* = Ax$ but this is not obvious form the text. Making the argument explicit somewhere would make the proof easier to read.

- **m5:** In the 2nd equation of the block bellow *l.635*, the $=$ should be a $\le$ I think.

Extra references
----------------

[A] Yen, I. E. H., Hsieh, C. J., Ravikumar, P., & Dhillon, I. S. (2014, March). Constant Nullspace Strong Convexity and Fast Convergence of Proximal Methods under High-Dimensional Settings. In NIPS (pp. 1008-1016).
limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose an iteratively reweighted least squares (IRLS) algorithm for the basis pursuit (BP) problem. The proposed algorithm differs from existing IRLS variants for basis pursuit mainly in terms of the iterative update of the smoothing parameter $\varepsilon_k$. Provided that the measurement matrix $A$ satisfies the null space property (NSP) of order $s$ with constant $\rho_s = \frac12$, the authors prove that their method converges globally at a linear rate and can recover any $s$-sparse vector $x^*$ from an arbitrary initial point $x_0$. The main contribution of the paper is the establishment of a global linear convergence rate for an IRLS algorithm for BP.
main_review: From my point of view, this paper is very clearly and well written. It features a comprehensive introduction to IRLS algorithms and the BP problem, and it provides an appropriate review of related work and theory. To the best of my knowledge, the above-mentioned global convergence result can be considered novel in the sense that for previous IRLS algorithms for BP only local convergence could be established. Moreover, the authors provide an additional theoretical result concerning the locality condition that was previously required to establish local convergence. Namely, they show that this locality condition necessarily requires that the support of the optimal solution has already been identified. I think that this is also an interesting insight.

All in all, I could not identify any serious flaws. Only, in my opinion, it would be desirable that the authors add a comment on the choice of $s$ in step (4) of Algorithm 1.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The contribution of this paper is to prove a global convergence rate under a null space property -- previous results only established global convergence without a rate, and  a local linear convergence rate.
main_review: On the strengths:
- This is indeed a new result. 
- The global rate deteriorates with $N$ the dimension of the problem, and the authors demonstrate numerically that there are two phases one where their global rate applies and one where the faster local rate of Daubechies et al apply. Numerically, the authors argue that this dependency on $N$ is unavoidable -- I find this interesting (although this seems to come from your $1/N$ factor in the choice of $\epsilon_k$, could a different choice of $\epsilon_k$ lead to better dependency on $N$?).

On the flip side, as a contribution on its own, this does feel somewhat narrow. The NSP is a strong condition in practice and would not hold for typical problems arising in ML and inverse problems. The paper could be improved by drawing some connections to previous convergence results on proximal methods where this two phase convergence property is also established (e.g. Liang et al, "Activity Identification and Local Linear Convergence of Forward--Backward-type Methods." SIAM Journal on Optimization 27.1 (2017): 408-437). Would the result apply under the weaker non-degeneracy assumptions of these works? Finally, as the authors mention, IRLS is applicable beyond just $\ell_1$ regularisation and is extendible to other regularisers such as subquadratic norms, nuclear norm or $\ell_q$ quasi-norms. My general impression is that the results here could be placed in a more general framework (the proof relies on extension of compressed sensing inequalities which are also established beyond the $\ell_1$ setting) to provide a complete picture on the performance of IRLS.

Edit after author responses: Overall, I think this is a nice addition to the literature, and there are possibly interesting followups that the authors could do for a journal version.
limitations_and_societal_impact: yes
review_title: null

Meta-review: All the reviewers stressed that this paper presents strong theoretical and numerical contributions, and it should be accepted. They commented that the strengths of the paper (in terms of quality of the exposition and numerical evaluation) outweigh its weaknesses (in particular the use of the NSP). This being said, I strongly recommend that the author follow the recommendations of the reviewers to improve the quality of the paper. 
Decision: Accept (Spotlight)