Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate
Authors: Christian Kümmerle
Claudio Mayrink Verdun
Dominik Stöger
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: compressed sensing
sparse models
signal processing
iteratively reweighted least squares
convex optimization
linear convergence

Abstract: 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 $\ell_1$-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.

Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate
Christian Kümmerle
Department of Applied Mathematics & Statistics Johns Hopkins University
Claudio Mayrink Verdun
Department of Mathematics and Department of Electrical and Computer Engineering Technical University of Munich
Dominik Stöger
Department of Mathematics KU Fichstätt-Ingokstadt
Abstract
The recovery of sparse data is at the core of many applications in machine learning and signal processing. While such problems can tackled using é f1rregularization as in the LASSO estimator and in the Basis Pursuit approach, specialized algorithms are typically required solve the corresponding high-dimensional non-smooth optimization for large instances. Iteratively Reweighted Least Squares (IRLS) is 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. this paper, we prove that a variant of IRLS converges with a global linear rate 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 theory by numerical experiments showing that our linear rate captures the correct dimension dependence. We anticipate that theoretical findings will lead insights for many other use cases the IRLS algorithm, such as low-rank matrix recovery.
Introduction
The field of sparse recovery deals with the problem of recovering an (approximately) sparse vector from only few linear measurements, presented by underdetermined system of linear equations of the form y = Ar. One approach solve this problem to consider the fn-minimization under linear constraints, which is NP-hard in general (4(55) For computational reasons, instead of fo-minimization, it common practice to consider its convex relaxation
min NER
||x||
subject to Ar = y,
(Pt)
kuemmerle @ jhu.edu
verdun @ ma. tum.de
dominik, stoeger ku.de
The name order of the authors is alphabetical.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

where A E R R b I" are given, which is referred to as (1(-norm) minimization 20 27 64 or basis pursuit 19 in the literature.
Unlike fn-minimization, the optimization program is computationally tractable in general. and a close relationship of their minimizers has been recognized and well-studied in the theory of compressive sensing (6 In statistics and machine learning, an unconstrained variant of (P.). often called LASSO, amounts to the most well-studied tractable estimator for variable selection in high-dimensional inference [37 48 65]. & #1-minimization has many other applications and it was
even called the modern least squares 14
The tractability of (1P becomes evident from the fact that it can be reformulated as a linear program [66]. However, many problems of interest in applications are high-dimensional and therefore challenging for standard linear programming methods, many specialized solvers for (79 have been proposed, such as the Homotopy Method (28), primal-dual methods [15 52). Alternating Direction regulaiiat
Method of Multipliers (9). Bregman iterative regularization [71] and Semismooth Newton Augmented
Lagragian Methods (46) and Iteratively Reweighted Least Squares (IRLS), the latter of which is in
the focus of this paper.
Iteratively Reweighted Least Squares corresponds to family of algorithms that minimizes non- smooth objective functions by solving a sequence of quadratic problems, with its idea going back to a method proposed by Weiszfeld for the Fermat- Weber problem [9]. A variety of different problems such as robust regression in statistics (39,53] total variation regularization in image processing
2 33 (5),, joint learning of neural networks (72), robust subspace recovery (45) and the recovery
of low-rank matrices [31 42 43 51] can be solved efficiently by IRLS in practice, as it relies on simple linear algebra to solve the linear systems arising from the quadratic problems at each iteration, without the need of a careful initialization or intricate parameter tuning. On the other hand, the analysis of IRLS methods typically challenging: General convergence results are often weak, and stronger convergence results are only available in particular cases; see Section 2.3 for more details.
IRLS for sparse recovery. In the sparse recovery context, the first variants of IRLS were introduced in [34 [59] for the E, -u-qusinormm minimization problem (Pp) with 0 < p I 1 that is similar to (Pi) but with Tællp instead of ||^||| as objective. In [16). modifications of the method of [34 59) using specific smoothing parameter update rules were observed to exhibit excellent numerical performance for solving (Pp), retrieving the underlying sparse vector when most of the methods fail. A useful fact
is that IRLS one of the few methods (ADMM being the other one (9) that provides a framework to solve both constrained and unconstrained formulations of e, --inimizationn problems.
major step forward in the theoretical understanding of IRLS was achieved in (23). where the authors showed that a variant of IRLS for PPP converges globally to fi-minimizer if the measurement operator A fulfills the null space property of sufficient order, which essentially ensures that an fi-minimizer is actually sparse. However, since this proof relies on the existence of convergent subsequence, their proof does not reveal any rate for global convergence. The analysis of [23) provides, furthermore, locally linear convergence rate, but this local linear rate has the drawback that it only applies if the support of the true signal has been discovered, which is arguably the difficult part of to com-mmimiaaiion-eee cf. Proposition 3.1 below and Section 4.1
While several extensions and modifications of the IRLS algorithm in (23) have been proposed (see, e.g., 3 30), ), this following fundamental algorithmic question has remained unanswered:
What is the global convergence rate of the IRLS algorithm for Ey-minimzaation?
Our contribution. We resolve this question, formally stated in 62 and present new IRLS algorithm that converges linearly to a sparse ground truth, starting from any initialization, as stated in Theorem 3.2 Our algorithm returns feasible solution with 5-accuracy, i.e., || 1²111 5, where x, is the underlying s-sparse vector, in A O(N / (log N) log(1/8) iterations. Analogous to (23), it is assumed that the measurement matrix A satisfies the so-called null space property [2].. We also provide a similar result for approximately sparse vectors. Our proof relies on a novel quantification of the descent of a carefully chosen objective function in the direction of the ground truth. Additionally, we support the theoretical claims by numerical simulations indicating that we capture the correct dimension dependence. We believe that the new analysis techniques in this paper are of independent interest and will pave the way for establishing global convergence rates for other variants of IRLS such as in low-rank matrix recovery 31
2

---

Notation. We denote the cardinality of a set I by [Z] and the support of a vector r E RN, i.e. the index set of its nonzero entries, by supp(z)
{j [N] 3j * 0}. We call vector s-sparse if at most 8 of its entries are nonzero. We denote by æı the restriction of onto the coordinates indexed by I, and use the notation 1 := [N] \
to denote the complement of set Furthermore, a oz(x)), denotes the l -error of the best s-term approximation of vector I E R.N, i.e., a, (2)) inffllz [| - =|l1 E N is s-sparse}.
2
IRLS for sparse recovery
We now present a simple derivation of the Iteratively Reweighted Least Squares (IRLS) algorithm for & 4-minimization which is studied in this paper. IRLS algorithms can be interpreted as variant of a Majorize-Minimize Minimize (MM) algorithm [63], as we will lay out in the following, It mitigates the non-smoothness of the || |I-rm by using the smoothed objective function Jg B + R, which is
defined, for given >> 0, by
|x] (2)
if 1 > E, if a S.
J=(2) Ee(x.) with fe(x)
( +E).
(1)
The function Jg can be considered as a scaled Huber loss function which is widely used in robust regression analysis 40]50) Moreover, the function Js is continuously differentiable and fulfills |or] je (1r) < |x| ++|+2 for each x R. Instead of minimizing the function Ig directly, the idea of IRLS is to minimize instead suitable chosen quadratic function Q+(-.z), which majorizes Jj such that Qs (z.z) 2 Js (z) for all
RV This function furthermore chosen such that Q. (z, .) = T. (x) holds, which implies that min Qe (z, S Te (I). The latter incquality implics =ERR
that by minimizing Qe(.,)). x)) IRLS actually achieves improvement in the value of Te well. More specifically, Qs (,,)) is defined by
(2(2,)) =
== [x) (VJ((z),, x) + 2 ((= z), diag (x)) x))
=T((x) (z, diag(w>())))) (z. diag we (x))x),
if |f
where VIz(x)
E.
is the gradient of Tg at and the weight vector if | = i=1
We (x) E R-V is vector of weights such that wx(x)); == [nxx([=;|,,)1-- for i E [M]. The following lemma shows that Q+ (---) has indeed the above-mentioned properties. We refer to the supplementary material for a proof.
Lemma 2.1. Let > 0, let Je Rº + R. be defined in ① and Qs : R. x XBN
IR defined
in (2) Then, for any 2, E R.,, the following affirmations hold:
diag(w, (x))x J
V. (x).
ä. Qe(x, x)) (x), in. Qe(2, 2 Jz(2).
As can be seen from the equality in 2 mminimizinn Qc(:, corresponds to minimization of (re- treighee least squares objective that unlike a classical MM approach, however, IRLS comes with an update step of the smoothing parameter at each iteration. We provide an outline of the method in Algorithm I
which lends its name to the method. Note
The weighted least squares update (3) can be computed such that 1+1 with W₁ = diag (wx). with the solution of the (m x m) linear system (AW,- (AW-'A')= = as a main computational step. This linear system is positive definite and suitable for the use of iterative solvers. In [30]. an analysis of how accurately the linear system of a similar IRLS method needs to be solved to ensure overall convergence. We note that for small Sk. the can be used so that the calculation of z boils down to solving a smaller linear system that is well-conditioned, c.f. the supplementary material for details. This numerically advantageous property is not shared by the methods of [3]23 30). as our smoothing update 44) is slightly different from the ones proposed in these papers. We refer to Section 2.2 for discussion.
'A"(AW,' Ay)-
-Woodbur formula (70)
The update step of the smoothing parameter & for the IRIS algorithm under consideration requires an priori estimate of the sparsity of the ground truth of the signal, a piece of information that is
3

---

Algorithm Iteratively Reweighted Least Squares for & {1mmiimmization
Measurement matrix A RRmx data vector y IR" initial weight vector wo E RR (default: wp .1.1,...)))..
Input:
Set E0 = OC. for 0, 2,,.. do
xx k+1 arg min (2, diag (wx) 2)
subject to Az y,
(3)
ZER
Ts (a(att)) 1
Ek+1 == min Eki
(4)
N
(w++1);
for each i [M]
(5)
max [,,_t11,xx (xt11
end for return Sequence (a* )211-
also needed by most of the methods for sparse reconstruction. In practice, overestimation of not a problem for similar numerical results if the overestimation remains within small multiples of the sparsity of the signal. We note, however, that there are also versions of IRLS which do not require a- a-priori knowledge of s, e.g. 68)68, . as the update rule for the smoothing parameter is chosen differently. An interesting future research direction is to extend the analysis presented here to IRLS with such a smoothing parameter update.
A consequence of Lemma 2.1 step (4), the fact that - J=(z) is monotonously non-decreasing,
and that h +> EK is non-increasing that ht Je(2) is non-increasing k. This implies that the iterates xh ++1 of Algorithm fulfill
Tests (2 (1 S Jes (x+t)) S Qea (2 ,I²) S Qcc (x Tea. (x*).
(6)
This shows in particular that the sequence (Je, }== is non-increasing, For this reason, it can be shown that each accumulation point the sequence of iterates )x>0 a (first-order) stationary point of the smoothed ooobjcccive J-(+) subject to the measurement constraint imposed by A and y. where oom En (see [23 Theorem 5.3]).
2.1 Null space property
As in [23). the analysis we present is based on the assumption that the measurement matrix A satisfies the so-called null space property (21]36]. which is key concept in the compressed sensing literature (see, e.g., (32 Chapter 4] for an overview).
Definition 2.2. A matrix E RmxNN said to satisfy the fn-null space property (f2-NSP) of order N with constant 0 < Pa 1 if for any set S [N] of cardinality |S| S it holds that | la S us Il for all E ker(A).
In 32 Chapter 4], the property of Definition 2.2 was called stable null space property. The importance of the null space property is due to the fact that it gives a necessary and sufficient criterion for the success of basis pursuit for sparse recovery, the following theorem shows.
Theorem 2.3 (32) Theorem 4.5]). Given a matrix A E mm= N every vector x E TR. such that |arloo is the unique solution of P1 with Ar y if and only if A satisfies the null space property of order 8 for some < <s <.
The NSPN is implied by the restricted isometry property (see, e.g., (II), which is fulfilled by a large class of random matrices with high probability. For example, this includes matrices with (sub-)gand jaausjga entries and random partial Fourier matrices [6]60]
2.2 Existing theory
predecessor of IRLS for the sparse recovery problem P1 and more generally, for f,-quusinorm
minimization with 0 < 1, is the FOCal Underdetermined System Solver (FOCUSS) as proposed by Gorodnitsky, Rao and -reggzo [34 59]. Asymptotic convergence of FOCUSS to
stationary point from any initialization was claimed in (59] but the proof not entirely accurate, as

---

pointed out by [17]. One limitation of FOCUSS is that, unlike in IRLS as presented in Algorithm no smoothing parameter is used, which leads ill-conditioned linear systems.
To mitigate this, [16] proposed an IRLS method that uses smoothing parameters e (such as used in Q: defined above) that are updated iteratively. It was observed that this leads to better condition number for the linear systems to be solved in each step of IRLS and, furthermore, that this smoothing strategy has the advantage of finding sparser vectors the weights of IRLS are chosen to minimize non-convex E, ep-quasinorm for p 1.
Further progress for IRLS designed to minimize f1-norm was achieved in the seminal paper [23] In [23, it was shown that if the measurement operator fulfills a suitable ε f1-null space property as in Definition 2.2 an IRLS method with iteratively updated smoothing converges to s-sparse solution, coinciding with the mi-iiimmier, if there exists one that is compatible with the measurements. This method uses not exactly the update rule of 4 but rather updates the smoothing parameter such that Ck+11 = min(Ex, R(**+1)))))))))))) )=+e+)))+/a/ IN), where ((a**))<+) is the (s + 1) larggett element of the set {|a k+1 1,j E [M]] Furthermore, a local linear convergence rate of IRLS was established 23 Theorem 6.1] under same conditions.
However, the analysis of [23] has its limitations: First, there is gap in the assumption of their convergence results between the sparsity of vector to be recovered and the order 3 of the NSP of the measurement operator. Recently, this gap was circumvented in (3] with an IRLS algorithm that uses a smoothing update rule based on an -norm, namely, Ek+1 min(Ck: 77(1 pa)o, (x*+t),,))))))))
where E (0, 1). and Ps is the NSP constant of the order of the NSP fulfilled
by the measurement matrix A-this rule quite similar to the rule (4) that we use Algorithm | In particular, (3] Theorem [I1.6] establishes convergence with local linear rate similar to [23 without the gap mentioned above. The main limitation, however, of the theory of (23) (which is shared by (3) is that the linear convergence rate only holds locally, i.c., in situation where the support of the sparse
vector has already been identified, see also Section 3 and Section 4.1 for a discussion.
We finally mention three relevant papers for the theoretical understanding of IRLS. (5) established the correspondence between the IRLS algorithms and the Expectation- ExpectationMMxxinzzatioi algorithm for constrained maximum likelihood estimation under Gaussian scale mixture distribution. By doing so, they established similar results as those from [23), i.e., the global convergence of IRLS with local linear convergence rate (as can be seen from their equation (38), which similar to 7 below) but by using different techniques based on such correspondence. [62] explores the relationship of IRLS for e --minimization and a slime mold dynamics, interpreting both as instance of the same meta-algorithm. Without requiring any connection between sparse recovery and l f--inimmzattin, (29) shows that an IRLS- algorithm for P... requires O log(1/5)/ /52/3 + (N)(88))) iterations to obtain multiplicative error of 1 + ò on the minimizer ||<|| i. Unlike our result Theorem 3.2, this corresponds not to a linear, but to a sublinear convergence rate.
2.3 Related work
As mentioned in the introduction, IRLS has long history and has appeared under different names within different communities, e.g., similar algorithms are usually called half-quudratic algorithmss in image processing [2 and the Kačanov method in numerical PDEs (25). Probably the most common usage of IRLS has been in robust regression (3,,9]] c.f. (10) for a survey that also covers applications in approximation theory. For p-norm regression, [ proposed version of IRLS for which convergence results for E [2, oo) were established, solving a problem that was open for over thirty years. Also, for robust regression, by using an f-oojecctive on the residual, (53) showed recently global convergence of IRLS with a linear rate, with high probability for sub-Gaussian data. We note that our proof strategy is different from the one of [53 due to structural difference of from robust regression.
In [57) the authors provide a general framework for formulating IRLS algorithms for the optimization of quite general class of non-convex and non-smooth functions, however, without updated smoothing. They use techniques developed in [4] to show convergence of the sequence of iterates to critical point under the presented.
property 8). However, no results about convergence rates were
For the sparse recovery problem, the topic discussed in this paper, the references 30
68
analyzed IRLS for unconstrained version of P which is usually a preferable formulation if
5

---

the measurements are corrupted by noise. Additionally, the work [30] addressed the question of how to solve the successive quadratic optimization problems. The authors developed a theory that shows, under the NSP, how accurately the quadratic subproblems need to he solved via the conjugate gradient method in order to preserve the convergence results established in (23)
Finally, for the related problems of low-rank matrix recovery and completion, IRLS strategies have emerged as one of the most successful methods in terms of data-efficiency and scalability
31 42 43,51.
While
writing this paper, the manuscript [58] appeared providing new insights about IRLS. deseribes a surprisingly simple reparametrization of the IRLS formulation for lp m--iiimmzzttinn (with (2/3, 1)) that leads smooth bilevel optimization problem without any spurious minima, i.e., the stationary points of this new formulation are either global minima or strict saddles. It is an interesting future direction to explore the connection between this approach and our global convergence theory.
3 IRLS for Basis Pursuit with Global Linear Rate
As discussed in Section 2.2 the main theoretical advancements for IRLS for the sparse recovery problem were achieved in the work (23).
Proposition 3.1. [23 Theorem 6.1] Assume that A E RRxN satisfies the NSP of order 3 > with 7+2
20z hold. Lei E RR be an s-sparse vector constant such that 0 < P3 < 1 2 and á > + I-ps
and set = Ar.. Assume that there exists an integer Ko 2 1 and a positive number & >> such that
-I Fz 1|1
8: : mintss (x.))d
<1
Then the iterates (s , ho+t bott ....} the all k 2 ko, the kth tteration of IRIS satisfies
the IRLS method in
23
converge linearly Tas ie., for
|1 xx111 S
P= p= + ps)
(1 1
1
1|
xx111.
(8)
1-
1
The main contribution of this paper is that we overcome a local assumption such as 7 and show that IRLS defined by Algorithm O exhibits global linear convergence rate, i.e., there is linear convergence rate starting from any intiialization, as early as in the first iteration.
Exactly sparse case. Our first main result, Theorem 3.2 deals with the scenario that the ground truth vector v. is exactly s-sparse. Our second result, presented in the supplementary material, generalizes the first one to the more realistic situation of approximately sparse vectors.
Theorem 3.2. Consider the problem of recovering an unknown s-sparse vector I. R. from known measurements of the form Ar.. Assume that the measurement matrix A E RuxN fulfills the -NS of order with constant Ps 1/2. Let the IRLS iterates { {2* by and {EK}a be defined by the IRLS algorithm
3 and (4) with initialization z.. Then, for all E N, it holds that
[en( -11xa111 S (1-piN) )))
(1=
piN)
- ||<x~11)
(9)
as well as
k
- - 5 1- c
11:00
xeell-
(10)
P1 N
Here 1/768 is abxolute constant and p1 1/2 denotes the -NSP constant of order 1.
Inequality 99 says that the difference Jr, ( -|= || converges linearly with uniform upper bound of N on the linear convergence factor. As our proof, which is detailed in the supplementary
material, shows, this implies inequality (TO). which implies that also ||x. x*111 exhibits linear convergence in the number of iterations k. In particular, this means that for some error tolerance
8 > we obtain | - 111 S after O
(pr (piN log
[|. [1.-=-||1
iterations.

---

Remark 3.3. Note that it follows directly from Definition 2.2 that the constant of the EI-NSP of or- der satisfies P1 S Ps S which implies that ò-accuracy is obtained after N log [1=e=0""l
iterations. This bound can be improved in many scenarios where one obtain more explicit bounds on Pr, for f: example, when A is a Gaussian matrix. Namely, inspecting (32, p. 142 and Thm. 9.2], we observe in this scenario that P1 S Vlog N)/m with high probability. Hence, in this scenario, at
most V
(
log
log
||.-- [1x--=001] = iterations are needed to achieve 6-accuracy.
8
The key idea in our proof is to use fact that the quadratic functional Qea (-,2*) approximates the f--norm a neighborhood of the current iterate x² For this reason, we also expect that for / sufficiently small, we have that Qa (x* + tu ,x*) < Qsa (x* .x*) if wh = It x is the vector between z and the ground truth Tx. Then by choosing properly, we can guarantee sufficient decrease of the functional Jz. (z*) in each iteration.
In Section we conduct experiments that indeed verify the linear convergence in ( and (TO) Moreover, we study numerically whether on the problem parameters N, 8 and m. We construct a worst-case example which indicates that the convergence rate indeed may depend on the dimension N in way as described by ( In certain sense, this indicates that there are two convergence phases, a global one, where a dimension- dependent constant cannot be avoided and a local convergence phase, where a local convergence result such as described in Proposition 3.I kicks in.
can observe dependence of the convergence rate
Finally, let us mention that have undertaken no efforts to optimize the constant 1/766 in Theorem 3.2 Nevertheless, we note that the constant e can be replaced by the sharper constant Cp. as defined in Proposition B.3
4 Numerical experiments
In this section, we support our theory with numerical experiments. First, we examine whether IRLS indeed exhibits two distinct convergence phases, "global" one, described in this paper, and local one, as described in (3), corresponding to different linear convergence rate factors. Second, explore to which extent the dimension dependence in the convergence rates and (TO) indicated by Theorem 3.2 is necessary, or we rather can expect a dimension-free linear convergence rate iMac computer with 4 GHz Quad-Core Intel Core i7
factor. All experiments conducted CPU, using MATLAB R2020b.
4.1 Local and global convergence phase
We first note that the local convergence result of 23 Theorem 6.1] depends on the locality condition
{(k) = mingcy ( < 1, cf. 77. Under this condition (and an appropriate null space condition), Proposition 3.1 stated above implies that ||æ x. 1 S * æ2,111 with an absolute constant < 1 which, in particular, does not depend on the dimension N, m, and s. This corresponds to a locally linear rate for IRLS. A very similar condition to (7) is required by the comparable and more recent local convergence statement 3 Theorem 111.6, inequality (III. 14)] for the IRLS variant considered
||z
However, a closer look at the locality condition 7 reveal that its basin of attraction is very restrictive: This condition means that the support identification problem underlying the sparse recovery has already been solved, as can be seen from the following proposition, whose proof we provide in the supplementary material.
Proposition 4.1. Let x I. N, let S C [N] be the support set of x, of size |S|= 7
holds, i.e., if | 2211 miness (x.)el, then the set S₃ [N] of the largest coordinates of x coincides with S.
We now explore the behavior of the IRLS algorithm for é-minimmzaaiin,. Algorithm [ and the sharpness of Proposition 4.1 in experiments that build on those of [23 Section 8. For this purprose, for N = 8000, we sample independently a 200-sparse vector x. E R with random support S c [N], 200 |S]. chosen uniformly at random such that (z.)s is chosen according the Haar measure
7

---

106
Estisnts limerr ritesrsssss rIESS
10
0.8
10
0.6
10
10 2
0.4
- Hr, (k)
0.2
((k)
10
0
8 12 16 20 24 28 32 36
40
44
48
52 56
60
iteration
Figure 1: Instantaneous linear convergence rates of IRLS for & Ei-minimization (N = 8000): Linear convergence factors Me, (k) := | x. x..1 11/l===11 x--li 1l (in blue), filled blue circle if Sp S with Sp of Proposition 4.1 (support identification), and error parameter {(k) == || - =1/11/ minks (x=)al Jal (in red). Horizontal (red) line: Threshold Ç = 1. Vertical (red) line: First iterate k with ((k) <
-2,11111
on the sphere of a 200-dimensional unit fz-ball, and measurement matrix A E R=*N with i.i.d. Gaussian entries such that A, (0, 1/m), while setting = [2s log([//s)] Such matrix is known to fulfill with high probability the fi-illl space property of order s with constant Ps < Theorem 9.29].
32
In Figure 1 we track the decay of the fi-error ||. x,I11 I of the iterates x² returned by Algorithm 1
via the values of ((k) = || /la minje ((x=)al. depicted in red, and the behavior of the factor (4e, (k+) := || -. ||:/ /1//|1==~11 s. lla, depicted in blue. We observe that the condition 7 for local convergence with the fast, dimension-less linear rate S is satisfied after A = 33 iterations, as indicated by the vertical dashed red line.
In the first few iterations, (A+) is larger than by several orders of magnitudes, suggesting that the local convergence rate results of (323] do not apply until the later stages of the simulation: In fact, we observe that the support S of x, is already perfectly identified via the s largest coordinates of x soon & 2 18. For iterations 18 k S 50, the linear rate μız, (k) remains very stably around se 0.7, after which an accelerated linear rate can be observed 5 Before lo = 18, for this example, the rate μa(k) hovers around 0.7 with slight variations. For all iterations k. ((k) is smaller than 1, in line with the global linear convergence rate implied by Theorem 3.2
Repeating similar experiment for larger ambient space dimension N = 16000 and a smaller measuremennt-t--spanee
ratio such that m [1.75s log(N//s) /)] results in a qualitatively similar situation, as seen in Figure 2[a): In Figure 2 aaa), we add also plot of the linear convergence factor Je, (a ) [a. l|:
((A)= Jea-1 (a
[| that tracks the behavior of the linear convergences in the smoothed
fi-orrm objective J. ef. (17) In addition to what have been observed in Figure I
we see that μ(k)
and Me, (k) exhibit a very similar behavior for this example.
Hence, these experiments indicate that we can distinguish two phases. In the first, global phase linear convergence already sets in, but the instantaneous linear convergence rate has not yet stabilized. In the second one, when the support identification problem has been solved, the instantaneous linear convergence stabilizes.
Remark 4.2. There are other methods in the literature, such as proximal algorithms, for which convergence results with two phase behaviour were already established. For example, (47) showed that a and that after a finite number of iterations, the region of fast convergence is reached. In particular, [47] Proposition 3. 3.6(i)) provides bound on this number of iterations, which scales proportionally with ||x.- 1/2 On the other hand, (3.2) for IRLS provides a bound the number of iterations until the fast linear convergence rate is reached that scales proportionally with log(I|r, [x_ - x="le)), but also proportionally with the dimension N. Moreover, most of these results require stronger assumptions than the NSP, such as the restricted isometry property or a restricted strong comvexity/smortiness property.
method applied to the Lasso problem exhibits local linear convergence,
'The latter phenomenon cannot be observed for the IRLS algorithm of objective function than Algorithm
23 as it uses a slightly different
8

---

106
Estimutes liner rates
0.8
0.8
104
10a
Brox pirander C
0.6
0.6
100
0.4
14, (k)
0.4
144 (k)
10
θ ((R
10
0.2
0.2
10
((k)
((k)
10
0 10 20 30 40 50 60 70 80 90100
10 20 30 40 50 60 70 80 90100
iteration
Steration
(a) Standard initialization (uniform weights (wo); 1 for all i).
(b) Adversary initialization (weights (wo): as in (II.
Figure 2: Instantaneous linear convergence rates of IRLS for fy-minimization (N 16000):
1=*-zzlis (in blue) and p(k) := Ter- (x 1-1
Jr, (x*) --1=)=111-___ 11= (in
Linear convergence factors Me, (k) = T=--1-a-11 green), filled circles if Sş S (perfect support identification), and error parameter ((k) == || --.11/1/mmm minkes (xx=)a] || (in red), horizontal and vertical red lines as in Figure
4.2 Global convergence rate and its dimension dependence
In this section, explore which extent the dependence on N in the convergence rates TT) and (14) is necessary or we can rather expect dimension-free linear convergence rate factor. To this end, we rum a variation of IRLS that initializes the weight vector uip E R not uniformly as in Algorithm|l but based on an adversary initialization, here denoted by zddv More specifically, first compute a minimizer
adv arg min #ERS *ER5*.Ageamy
||=|||
of the l, fg-minimization problem restricted to the off-support coordinates of x. indexed by S and set then x² E RR such that x- := =dvv and zy = O. Based on this initialization x", we compute
eo = (.(x") and set the first weight vector such that for all i E [N]. N
(wo); == max (1=)),50)'
(11)
before proceeding with the IRLS steps
and 5 until convergence.
We observe in Figure b)b that this initialization, which is adversary as it sets very large initial weights on the coordinates of S that correspond to the true support of z,, eventually results in the same behavior of Algorithm [ as for the standard initialization by uniform weights, identifying the true support at iteration k = 39 compared to = 30. However, in the first few iterations, we see that the instantaneous linear convergence factor μu() is close to 1 with v(1) 0.980, decreasing only slowly before stabilizing around 0.79 after around = 30.
While this is just one example, this already indicates that in general, a linear rate such as ( i.e., without dependence on dimension N (which has been proven locally in (3 Theorem 6. and Theorem III.6)) might not hold in general.
3
In our next experiment, we further investigate numerically the dimension dependence of the worst-
Jr, (a*)) ||--||
case linear convergence factor μ(k) Jz, (x* ( I which is upper bounded by the result of Theorem 3.2 We saw that in the experiment using the adversary initialization mentioned above and
depicted in Figure bb), the maximal value was attained the first iteration, i.e., for ((1), as the effect of the adversary initialization is most eminent for k 1.
We now run IRLS starting from the adversary initialization for different ambient dimensions 125 24/2 for = 0, l,..., 14. For each of values of N, we sample vectors v. E R N of sparsity 40 from the same random model as above, and scale the number of i.i.d. Gaussian measurements with m = [2s log(N/s)J. We average the resulting values for p(1) across 500 independent realizations of the experiment.

---

150
(1)
100
N
100
50
5002000 4000
8000
16000
Dimension
Figure 3: Comparison of and 1-x(1) (for which Proposition B.3 provides un upper bound of
100
P for different dimension parameters N, where yd(1) Jep (2 2-
is the linear convergence factor, for IRLS initialized from adversary initialization.
J., (z 2. ll
In Figure 3 see that dependence N of linear convergence factor μu(1 that is observed for this experiment is quite well described by the upper bound (9) provided by our main result Theorem 3.2 1-)(1) scales almost linearly with N. As footnote in Section indicates, the constant P1 of the
null space property of order scales with log and therefore precise dependence all the m
parameters such as m and might be more complicated than what can be observed in this experiment.
Nevertheless, we interpret Figure as strong evidence that the linear convergence rate factor of Proposition iB.3 tight its dependence N, and that dimension factor μ cannot be expected in general.
Conclusion
In this paper, we solved an open problem in the algorithmic theory for sparse recovery. In particular, we established a new variant of the IRLS algorithm for Basis Pursuit or f--minimization for which we show global linear convergence rate under suitable and sharp assumption, namely, the null-space property. Moreover, we have corroborated our theory with numerical experiments that, first, discussed the difference between the local and global convergence phase and, second, that elucidated the optimality of the dimension dependence of convergence rate given by our main theorem.
We think that the results in this paper give rise to number of interesting research directions for follow-up work. While the numerical experiments in Section S substantiate the hypothesis that the dependence of the convergence rate on N and p1 in our theory is not an artifact of our proof, also observed this section that for a generic initialization no such dependence can be observed. iintension-independdee
In view of this, it is interesting to investigate whether rate possible, for example via a smoothed analysis [12.61]. Furthermore, there are currently no convergence rates available for IRLS optimizing nuclear norm-type objective, which is of great interest for low-rank matrix recovery [31 43 51 and we expect that our analysis may be generalizable this setting as well.
global convergence
Finally, was observed that sparse vectors can be recovered from even fewer measurements via the optimization of non-convex l, ey-quasinorm (with 0 p < 1), and that IRLS exhibits excellent performance in this case [36[2]. While thorough understanding has remained elusive so far for this non-convex case, we consider our results first step towards global convergence theory for IRLS for the optimization of l, quasinorms or similar non-convex surrogate objectives.
Acknowledgments and Disclosure of Funding
The authors want to thank Massimo Fornasier for inspiring discussions and the anonymous reviewers for their detailed comments. C.K. is grateful for support by the NSF under the grant ASSF-IIS-83778 C.M.V. is supported by the German Federal Ministry of Education and Research (BMBF) in context of the Collaborative Research Project SparseMRI3D+ and by the German Science Foundation (DFG) in the context of the project KR 4512/1-1. D.S. was supported by the Air Force Office of Scientific Research under award #FA9550- 18- 1-00888
10

---

References
[1] Deeksha Adil, Richard Peng, and Sushant Sachdeva, Fast, provably convergent irls algorithm for p-norm linear regression, Advances in Neural Information Processing Systems (NeurIPS), 2019, pp. 14189-14200.
[2] Mare Allain, Jerome Idier, and Yves Goussard, On global and local convergence of half-quadratic algoritums, IEFE Trans. Image Process. 15 (2006), no. 5, 1130-1142.
Aleksandr Aravkin, James V Burke, Daiwei He, IRLS for Sparse Recovery Revisited: Examples of Failure and Remedy, arXiv preprint arXiv:1910.070000 (2019).
[4] Hedy Attouch, Jerome Bolte, and Benar Fux Svaiter, Convergence of descent methods for semi-algebree and tame problems: Proximal algorithms,, forwand-backward splitting, and regularized gauss-seidel meth- ods, Math, Programming 137 (2013), 91-129.
[5] Demba Ba, Behtash Babadi, Patrick L Purdon, and Emery N. Brown, Convergence and stability of iteratively re-weighted least squares algorithms, IEEE Transactions Signal Processing 62 (2013), no. 1, 183-195.
[6] Richard Baraniuk, Mark Davenport, Ronald Vore. and Michael Wakin, A simple proof of the restricted isometry property for rundom matrices, Constr. Approx. 28 (2008), 253-263.
[7] Amir Beck and Shoham Sabach, Weiszfeld's method: Old and new results, J. Optim. Theory Appl. 164 (2015), 1-40.
[8] Jérôme Bolte, Aris Daniilidis, and Adrian Lewis, The tojasiewicz inequality for nonsmooth subanalytic finnctions with applications to subgradient dynamical systems, SIAM J. Optim. 17 (2007), no. 4, 1205 1223.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Pelcato, and Jonathan Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends@ in Machine Learning (2011) 1), 1-122.
[10] Charles S. Burrus, Iterative reweighted least squares, OpenStax CNX: Available http://cnx.oogg/ hatp://mmm2220072222222----222-3
online:
(2012).
[11] Jameson Cahill, Xuemei Chen, and Rongrong Wang, The gup between the null space property and the restricted isometry property. Linear Algebra Appl. 501 (2016), 363-375.
[12] Emmanuel J. Candès, Justin K. Romberg, and Terence Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math. 59 (2006), no. 8, 1207-1223.
[13] Emmanuel Candès and Terence N Near-Optinee Signal Recovery From Random Projections: Universal Encoding Strategies?, IEEE Trans. Inf. Theory 52 (2006), no. 12, -4255.
[14] Emmanuel J. Candès, Michael B. Wakin, and Stephen P. Boyd, Enhancing sparsity by reweighted & minimization, Journal of Fourier analysis and applications 14 (2008), no. 5-6, 877-905
[15] Antonin Chambolle and Thomas Pock, A first-order primal- dual algorithu for convex problems with applications to imaging, Journal of mathematical imaging and vision 40 (2011), no. 1, 2200-45.
[16] Rick Chartrand and Wotao Yin, Iteratively reweighted algorithmss for compressive sensing, IEEE Interna- tional Conference on Acoustics, Speech and Signal Processing (ICASSP), 2008, pp. 3869-3872.
[17]
Noncomvex sparse regularization and splitting algorithmss, Splitting methods in communication, imaging, science, and engineering. 2016, pp. 237-249.
[18] Scott Shaobing Chen, David L Donoho, and Michael A Saunders, Atomic decomposition by hasis pursuit, SIAM Rev. 43 (2001), no. 1, 129-159.
[19] Shaobing Scott Chen and David L. Donoho, Basis pursuit, Proc. of 1994 28th Asilomar Conference on Signals, Systems and Computers, 1994, pp. 41-44.
[20] Jon F. Claerbout and Francis Muir. Robust modeling with erratic data, Geophysics 38 (1973), no. 5. 826-844.
[21] Albert Cohen, Wolfgang Dahmen, and Ronald DeVore, Compressed sensing and best k-term approximation. Amer. Math. Soc. 22 (2009). 211-231.
[22] Daniel Dadush and Sophie Huiberts. A friendly smoothed analysis of the simplex method, SIAM J. Comput. 49 (2018), no. 5, STOC18 449--STO18 499.

---

[23] Ingrid Daubechies, Ronald DeVore, Massimo Fornasier, and Sinan Güntürk, Iteratively reweighted least squares minimization for sparse recovery, Comm. Pure Appl. Math. 63 (2010). 1-38.
[24] Geoffrey Davis, Stephane Mallat, and Marco A greedy approximations, Constr. Approx. 13 (1997), no. 57-98.
[25] Lars Diening, Massimo Fornasier, Tomasi Roland, and Maximilian Wank, A Relaxed Kačanov iteration for the p-poisson problem, Numer. Math. 145 (2020), no. 1-34.
[26] David L. Donoho, Compressed sensing, IEEE Trans. Inf. Theor. 52 (2006), no. 4, 1189-1881151 2289-1306.
[27] David L Donoho and Benjamin F Logan, Signal recovery and the large sieve, SIAM J. Appl. Math. 52
(1992), no. 2, 577-591.
[28] David L. Donoho and Yaakov Tsaig, Fast solution of fi-norm minimization problems when the solution may be sparse, TEEE Trans. Inform. Theory 54 (2008), 4789-4812.
[29] Alina Ene and Adrian Vladu, Improved convergence for & and f_ _oo regression via iteratively reweighted least squares, Proceedings of 2019 International Conference on Machine Learning (ICML' 19), 2019, pp. 1794-1801.
[30] Massimo Fomasier, Steffen Peter, Holger Rauhut, and Stephan Worm, Conjugate gradient acceleration of iteratively re-weighted least squares methods, Comput. Optim. Appl. 65 (2016), no. 1, 205-259.
[3]] Massimo Fornasier, Holger Rauhut, and Rachel Ward, Low-rank matrix recovery via iteratively reweighted least squares minimization, SIAM J. Optim. 21 (2011), 1614-1640.
[32] Simon Foucart and Holger Rauhut, A mathematical introduction to compressive sensing, Applied and Numerical Harmonic Analysis, Springer New York, 2013.
[33] Donald Geman and George Reynolds, Constrained Restoration and the Recovery of Discontinuities, IEEE Trans. Pattern Anal. Mach. Intell. 14 (1992), no. 03, 367-383.
[34] Irina Gorodnitsky and Bhaskar Rao. Sparse signal reconstruction from limited data using focuss: A re-weighted minimum norm algorithm, IEEE Trans. Signal Process. 45 (1997), no. 3, 600-616.
[35] Peter J. Green, Iteratively reweighted least squares for maximum likelihood estimation, and some robust and resistant alternatives, Journal of the Royal Statistical Society: Series B (Methodological) 46 (1984),
no. 2, 149-170.
[36] Remi Gribonval and Morten Nielsen, Sparse representation in the union of basis, IEEE Trans. Inform. Theory 49 (2003),
[37] Trevor Hastie, Robert Tibshirani, and Martin Wainwright, Statistical learning with sparsity: The lasso and generalizations, Chapman and Hall/CRC, 2019.
[38] Magnus Rudolph Hestenes Eduard Stiefel, Methods of conjugate gradients for solving linear systems. Journal of research the National Bureau of Standards 49 (1952), no.
[39] Paul W. Holland and Roy Welsch, Robust regression using iteratively reweighted least-squares, Commu- nications in Statistics Theory and Methods (1977), 813- 827.
[40] Peter J. Huber, Robust estimation of a location parameter, Ann. Math. Statist. 35 (1964), no. 1, 73-1011.
[41] Jérôme Idier, Convex calf-quadratic criteria and interacting auxiliary variables for image restoration, IEEE Trans. Image Process. 10 (2001), no. 7, 1-100-10009
[42] Christian Kümmerle and Claudio Mayrink Verdun, scalable second order method for ill-oonitiooned matrix completion from samples, Proceedings of 2021 International Conference on Machine Learning (ICML'21), 2021.
[43] Christian Kümmerle and Juliane Sigl, Harmonic mean iteratively reweighted least squares for low-rank matrix recovery, J. Mach. Learn. Res. 19 (2018), 1815-1863.
[44] Ming-Jun Lai, Xu Yangyang, and Yin Wotao, Improved iteratively reweighted least squares for uncon- strained smoothed E, minimization, SIAM J. Numer. Anal. 2 (2013), no. 51, 927-957.
[45] Gilad Lerman and Tyler Maunu, Fast, robust and non-convex subspace recovery, Information and Inference: A Journal of the IMA 7 (2018), 2, 277-336.
12

---

[46] Xudong. Li, Defeng, Sun, and Kim-Chuan Toh, A highly efficient semismooth newton augmented lagrangian method for solving lasso problems, SIAM J. Optim. 28 (2018), no. 1, 1,433-458.
[47] Jingwei Liang, Jalal Fadili, and Gabriel Peyré, Activity identification and local linear convergence of hactaundd-bwwwwr-yyyp methods, SIAM Journal on Optimization 27 (2017), no. 1, 4,408-437.
[48] Nicolai Meinshausen, Peter Bühlmann, et al., dimennooooo graphs and variable selection with the lasso, Annals of statistics 34 (2006), no. 3, 1436-1462)
[49] Gérard Meurant, The lanezos and conjugate gradient algorithmm: From theory to finite precision computa- tions, Society for Industrial and Applicd Mathematics, 2006.
[50] Gregory P Meyer, An alternative probabilistic interpretation of the huber loss, Proceedings of the icce/evf conference on computer vision and pattern recognition, 2021, pp. 5261-5269.
[51] Karthik Mohan and Maryam Fazel, Iterative reweighted algorithms for matrix rank minimization, J. Mach. Learn. Res. 13 (201)), 3441-3473.
[52] Cesare Molinari, Mathurin Massias, Lorenzo Rosasco, and Silvia Villa, Iterative regularization for convex regularizers, International conference artificial intelligence and statistics, 2021, pp. (684-1694
[53] Bhaskar Mukhoty, Govind Gopakumar, Prateek Jain, and Purushottam Kar, Globally-convergenl iteratively reweighted least squares for robust regression problems, Proceedings of Machine Learning Research, 2019, pp. 313-322.
[54] Balas K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput. 24 (1996), 227-234.
[55] Mila Nikolova and Michael Ng. Analysis of half- quadratic minimization methods for signal and image recovery, SIAM J. Sci. Comput. 27 (2005), no. 3, 933--66.
[56] Jorge Nocedal and Stephen Wright, Numerical optimization, Springer Science & Business Media, 2006.
[57] Peter Ochs, Alexey Dosovitskiy, Thomas Brox, and Thomas Pock, On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision, STAM J. Imaging Sci. 8 (2015), no. 1, 331-372.
[58] Clarice Poon and Gabriel Peyré, Smooth Bilevel Programming for Sparse Regularization, Proc. NeurlPS'21. 21, 2021.
[59] Bhaskar D. Rao and Kenneth Kreutz-Delgado, An affine scaling methodology for best basis selection, IEEE Trans. Signal Process. 47 (1999), no. 1, 187-280))
[60] Mark Rudelson and Roman Vershynin, On sparse reconstruction from fourier and gaussian meusurements, Comm. Pure Appl. Math. 61 (2008), no. 8, 1025-1045.
[61] Daniel A. Spielman and Shang-Hon Hua Teng, Smoothed analysis of termination of linear programming algorithms, Math. Program., Ser. 97 (2003), 375-404.
[62] Damian Straszak and Nisheeth K Vishnoi, Iteratively reweighted least squares and slime mold dynamics: connection and convergence, Mathematical Programming (2021). 1-33.
[63] Ying Sun, Prabhu Babu, and Daniel P. Palomar, Majorizatior-miiniizzaaae algorithms in signal processing. communications, and machine learning, IEEE Trans. Signal Process. 65 (2017), no. 3, 794-816.
[64] Howard L. Taylor, Stephen C. Banks, and John F. McCoy, Deconvolution with the f norm, Geophysics 44 (1979), no. 1, 39-5..
[65] Robert Tibshirani, Regression shrinkage and selection via lasso, Journal of the Royal Statistical Society: Series (Methodological) 58 (1996), no. 1, 267-288.
[66] Andreas M Tillmann, Equivalence of linear programming and basis pursuit, PAMM 15 (2015), no. 1, 735 -38.
[67] Sergey Voronin, Regularization of linear systems with sparsity construints with applications to large scale inverse problems, Ph.D. Thesis, Princeton University, 2012.
[68] Sergey Voronin and Ingrid Daubechies, An iteratively reweighted least squares algorithu for sparse regularization, Functional amalysis, harmonic analysis, and image processing: A collection of papers in honor of bjöm jawerth, 2017, pp. 391-441.
[69] Endre Weiszfeld, Sur le point pour lequel la somme des distances de n points donnés est minimum, Tohoku Mathematical Journal, First Series 43 (1937), 355-386
13

---

[70] Max A. Woodbury, Inverting modified matrices, Memorandum report 42 (1950), no. 106, 336.
[71] Wotao Yin, Stanley Osher, Donald Goldfarb, and Jerome Darbon, Bregman iterative algorithms for E E-minimmzation with applications to compressed sensing, SIAM J. Imaging Sci 1 (2008), no. 1, 143-168.
[72] Zaiwei Zhang. Xiangru Huang. Qixing Huang. Xiao Zhang, and Yuan Li, Joint learning of neural networks via iterative reweighted least squares., Cypr workshops, 2019, pp. 18 26.
14


Reviews:
[{"review_id": "mIoqkx53Ock", "reviewer": "Reviewer_74ZJ", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nAll 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "k_Jkhh3MXyT", "reviewer": "Reviewer_pfZ6", "summary": "The paper studies the Basis Pursuit (BP) optimization problem (minimal l1 norm solution to a linear system).\nIterative Reweighted Least Squares (IRLS) is a majorization minimization algorithm to solve this problem.\nThe paper shows that it converges *globally* and linearly, under a nullspace property assumption (with parameter <1/2).\nExisting results only prove local linear convergence rates, first showing that IRLS identifies the support of the solution, after which the rate becomes linear.\nThe key is a new update rule for the smoothing parameter used in the majorization of |.| by a scaled Huber function.\nExperiments 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.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nComments:\nL32 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) ?\nSame 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.\n\nL115 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 ?\n\nL127 it holds trivially with v=0, why is it needed to exclude this case ?\nThe formulation L132 is a bit strange to me, I would put with Ax=y *before* \"is the unique solution\".\n\nL265 could you point to a more precise location in the Foucart and Rauhut book ?\n\nFig 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)).\nHowever in Fig 2 the \"noisy\" aspect of last iterations eems to kick in before numerical errors, can you comment on this aspect?\n\nIn 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?\n\nL279 can you explicitely state m and s for reproducibility ?\n\nIn 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 ?\n\nL596 it's epsilon not epsilon_k ?\n\n\n\nL78 I would say the complement is with respect to \\mathbb{N} not R^N ?\nL116, 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.\nL115 use \\mapsto not \\to\nL171:  obtain an multiplicative\nL234 epsilon_k not ^k\nseveral time you put an Upper case after a \":\" (eg L272, other occurrences)\nL322 you have a broken ref\nL473 Darbon not Darbons\nL587 has the l_1 -NSP holds.\nL587 you use z than x in the proof, maybe you can harmonize ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": ".", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "RxNWZOlzOm5", "reviewer": "Reviewer_DQJN", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On the strengths:\n- This is indeed a new result. \n- 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$?).\n\nOn 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.\n\nEdit 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "9o8gyUdjtRS", "reviewer": "Reviewer_YDtV", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Review Summary\n---------------\n\nThe 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.\n\nMajor comments and questions\n----------------------------\n\n\n- **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.\n\n- **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.\n\nMinor comments, nitpicks and typos\n----------------------------------\n\n- **m1:** (*l.78*) I think that $\\mathbb R^N$ should be $[N]$ here?\n\n- **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$.\n\n- **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?\n\n- **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.\n\n- **m5:** In the 2nd equation of the block bellow *l.635*, the $=$ should be a $\\le$ I think.\n\nExtra references\n----------------\n\n[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).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

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)