Global convergence of smoothed iteratively reweighted least squares for nonconvex $\ell_\tau$-minimization in sparse recovery

The iteratively reweighted least squares (IRLS) algorithm of Daubechies, DeVore, Fornasier and Güntürk approximates $\ell_1$- and $\ell_\tau$-minimization for sparse recovery by a sequence of weighted least-squares problems with an adaptively decreasing smoothing parameter $\varepsilon$. Its published theory guarantees convergence to the sparse solution only in a slightly smaller sparsity range than $\ell_1$-minimization, gives only a posteriori conditions (such as $\varepsilon\to 0$) for convergence in the nonconvex $0<\tau<1$ regime, and proves fast local rates only after the iterates enter an unspecified neighborhood of the solution. Later work resolved the $\ell_1$-sided questions: Aravkin, Burke and He constructed examples where the algorithm provably fails at the boundary of the sparsity range and gave a modified smoothing update that removes this gap, and Kümmerle, Mayrink Verdun and Stöger proved a global linear convergence rate for an IRLS variant. What remains open is the global convergence theory of the smoothed nonconvex $\ell_\tau$-IRLS ($0<\tau<1$): does it converge from its standard initialization to the sparsest or a global $\ell_\tau$-minimizer under null-space-type assumptions, or can this fail, and if so what is the precise basin of attraction; how many iterations are needed a priori to enter the locally superlinear regime; and how sharp are the local convergence constants.

Background

Compressed sensing seeks to recover a sparse vector $x\in\mathbb{R}^N$ (one with at most $k$ nonzero entries, called $k$-sparse) from far fewer linear measurements $y=\Phi x\in\mathbb{R}^m$, $m<N$. Since minimizing the number of nonzeros is combinatorially hard, one standard relaxation is basis pursuit, i.e. minimizing the $\ell_1$-norm $\|x\|_{\ell_1}=\sum_i |x_i|$ over the affine solution set $\mathcal{F}(y)=\{x:\Phi x=y\}$, which recovers the sparse solution exactly when $\Phi$ satisfies a suitable condition. Two standard such conditions are the restricted isometry property (RIP), which says that $\Phi$ approximately preserves the norm of all sparse vectors, and the null space property (NSP) of order $K$ with constant $\gamma\in(0,1)$, which says that every vector $\eta$ in the null space of $\Phi$ satisfies $\|\eta_T\|_{\ell_1}\le\gamma\|\eta_{T^c}\|_{\ell_1}$ for every coordinate set $T$ of size at most $K$; under NSP of order $K$, the $k$-sparse solution is unique and equal to the $\ell_1$-minimizer for all $k\le K$. Daubechies, DeVore, Fornasier and Güntürk proposed computing this minimizer by IRLS: starting from the minimizer of the plain $\ell_2$-norm on $\mathcal{F}(y)$ (obtained with uniform weights), each iteration computes the minimizer of a weighted $\ell_2$-norm $\|x\|_{\ell_2(w)}=(\sum_i w_i x_i^2)^{1/2}$ on $\mathcal{F}(y)$ and then updates the weights to $w_i=(|x_i|^2+\varepsilon^2)^{-1/2}$, where $\varepsilon$ is a smoothing parameter decreased adaptively by the rule $\varepsilon_{n+1}=\min(\varepsilon_n, r(x^{n+1})_{K+1}/N)$, with $r(z)$ the non-increasing rearrangement of $|z|$. The smoothing makes the reweighted functional $J(z,w,\varepsilon)=\sum_i (z_i^2 w_i + \varepsilon^2 w_i + w_i^{-1})$ a smooth surrogate for the $\ell_1$-norm, and the algorithm is equivalent to a block coordinate descent (minimizing over $x$ and over the weights alternately) on this surrogate. The same scheme with the heavier weights $w_i=(|x_i|^2+\varepsilon^2)^{-1+\tau/2}$, $0<\tau<1$, smooths the nonconvex $\ell_\tau$ quasi-norm $\|x\|_{\ell_\tau}^{\tau}=\sum_i |x_i|^\tau$, which penalizes small entries more aggressively and empirically recovers sparser solutions from fewer measurements; the analysis of this $\tau$-version is stated under the analogous $\tau$-null space property ($\tau$-NSP) of order $K$ with constant $\gamma$, in which the $\ell_1$-norms of the NSP are replaced by $\tau$-th powers of the $\ell_\tau$ quasi-norm, i.e. $\|\eta_T\|_{\ell_\tau}^{\tau}\le\gamma\|\eta_{T^c}\|_{\ell_\tau}^{\tau}$. The proved theory for the $\ell_1$ version guarantees convergence of the iterates for every $y$, recovery of the $k$-sparse solution only for $k<K-\frac{2\gamma}{1-\gamma}$ (a strict sub-range of the $\ell_1$ range $k\le K$; the authors state they cannot exclude failure inside this gap and had no examples), and a linear (exponential) local rate once the iterates are near the solution. For $0<\tau<1$ the analysis is weaker: the surrogate decreases monotonically, accumulation points are characterized, and if the a posteriori condition $\lim\varepsilon_n=0$ holds then the iterates converge to a $K$-sparse $\ell_\tau$-minimizer; but because the smoothed functional is nonconvex, convergence to the sparsest or global $\ell_\tau$-minimizer is not proved, the local superlinear rate — a law of the form $E_{n+1}\le\mu E_n^{2-\tau}$ in the error measure $E_n=\|x^{(n)}-x^*\|_{\ell_\tau}^{\tau}$, faster than any geometric rate for $\tau<1$ — holds only inside a neighborhood of radius $R^*$ whose entry time is not bounded a priori, and the authors report that for small $\tau$ the iteration sometimes never reaches that neighborhood. The open problem is the global half of this convergence theory for the nonconvex $\ell_\tau$ algorithm.

Problem Statement

For the noiseless sparse-recovery setting $y=\Phi x$ with $\Phi\in\mathbb{R}^{m\times N}$, $m<N$, and affine solution set $\mathcal{F}(y)=\{x:\Phi x=y\}$, consider the iteratively reweighted least squares algorithm of Daubechies–DeVore–Fornasier–Güntürk with the smoothed nonconvex $\ell_\tau$ weights $w_i^{(n)}=(|x_i^{(n)}|^2+\varepsilon_n^2)^{-1+\tau/2}$, $0<\tau<1$, initialized with uniform weights $w^{(0)}=(1,\dots,1)$ and $\varepsilon_0=1$ (so that the first iterate is the minimum $\ell_2$-norm solution of $\Phi x=y$), and with the adaptive smoothing rule $\varepsilon_{n+1}=\min(\varepsilon_n, r(x^{(n+1)})_{K+1}/N)$, where $r(z)$ denotes the non-increasing rearrangement of $|z|$ and $K$ is a fixed integer, as in the source. Assume that $\Phi$ satisfies the $\tau$-null space property ($\tau$-NSP) of order $K$ with constant $\gamma$, i.e. $\|\eta_T\|_{\ell_\tau}^{\tau}\le\gamma\|\eta_{T^c}\|_{\ell_\tau}^{\tau}$ for every coordinate set $T$ with $|T|\le K$ and every $\eta$ in the null space of $\Phi$, with $\gamma$ in the range assumed by the source's $\tau$-theory (in particular $\gamma<1-\frac{2}{K+2}$ for the global statements, and $0<\gamma<1$ for the local rate theory), and that $\mathcal{F}(y)$ contains a $k$-sparse vector $x^*$ with $k\le K$. Establish the global convergence theory of this algorithm. Specifically: (i) prove that the iterates converge to the sparsest solution of $\Phi x=y$ (which, under these assumptions, coincides with the unique global minimizer of the $\ell_\tau$ quasi-norm $\|x\|_{\ell_\tau}^{\tau}=\sum_i |x_i|^\tau$ on $\mathcal{F}(y)$), or disprove this by an explicit construction — a matrix and data for which the algorithm, run from its standard initialization $w^{(0)}=(1,\dots,1)$ with $\varepsilon_0=1$, provably converges to a limit that is not the sparsest/global $\ell_\tau$-minimizer; a single such explicit construction suffices to establish that global convergence can fail, and if it is given, (i) additionally requires characterizing precisely the basin of attraction of the sparse solution, i.e. verifiable a priori conditions on the problem instance $(\Phi,y,\tau,K,\gamma)$ under which the standard-initialization iterates converge to the sparse solution; (ii) provide an a priori bound, in terms of the problem parameters, on the number of iterations needed for the iterates to enter the neighborhood of radius $R^*=[\rho\, r(x^*)_k]^{\tau}$ (for a parameter $0<\rho<1$, where $r(x^*)_k$ is the $k$-th largest absolute entry of $x^*$) in which the local superlinear rate $E_{n+1}\le\mu E_n^{2-\tau}$ with $E_n=\|x^{(n)}-x^*\|_{\ell_\tau}^{\tau}$ and contraction constant $\mu$ is guaranteed, so that the total iteration complexity of the method is bounded; in the disproof branch of (i) this bound is required for the problem instances covered by the basin-of-attraction characterization obtained there, and need not hold for the failing counterexample; and (iii) determine sharp forms of the constants in the local convergence theory (the contraction factor $\mu$ and the neighborhood radius $R^*$, and the constants in the superlinear rate law), removing the pessimism that the source's own estimates acknowledge. These three requests jointly complete the convergence theory of the same algorithm under the same assumptions: they concern, respectively, whether the algorithm globally reaches the target, how quickly it enters the proven fast regime, and how sharp the proven fast regime is.

References

1. Ingrid Daubechies, Ronald DeVore, Massimo Fornasier, and C. Sinan Güntürk, 'Iteratively reweighted least squares minimization for sparse recovery', Communications on Pure and Applied Mathematics 63(1) (2010) 1–38. DOI: 10.1002/cpa.20303, https://doi.org/10.1002/cpa.20303 (preprint arXiv:0807.0575, https://arxiv.org/abs/0807.0575, titled 'Iteratively re-weighted least squares minimization for sparse recovery')
2. Aleksandr Y. Aravkin, James V. Burke, and Daiwei He, 'IRLS for Sparse Recovery Revisited: Examples of Failure and a Remedy' (2019). arXiv:1910.07095, https://arxiv.org/abs/1910.07095
3. Christian Kümmerle, Claudio Mayrink Verdun, and Dominik Stöger, 'Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate', Advances in Neural Information Processing Systems 34 (NeurIPS 2021). arXiv:2012.12250, https://arxiv.org/abs/2012.12250
4. Damian Straszak and Nisheeth K. Vishnoi, 'IRLS and Slime Mold: Equivalence and Convergence' (2016). arXiv:1601.02712, https://arxiv.org/abs/1601.02712
5. Christian Kümmerle and Johannes Maly, 'Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares' (2023, revised 2024). arXiv:2306.04961, https://arxiv.org/abs/2306.04961
6. Liangzu Peng, Christian Kümmerle, and René Vidal, 'Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression' (2022). arXiv:2208.11846, https://arxiv.org/abs/2208.11846
7. Stamatios Lefkimmiatis and Iaroslav Koshelev, 'Learning Sparse and Low-Rank Priors for Image Recovery via Iterative Reweighted Least Squares Minimization', International Conference on Learning Representations (ICLR) 2023. arXiv:2304.10536, https://arxiv.org/abs/2304.10536
8. Kaihao Liang and Michael J. Clay, 'Iterative re-weighted least squares algorithm for $\ell_p$-minimization with tight frame and $0<p\le 1$', Linear Algebra and its Applications 581 (2019) 413–434. DOI: 10.1016/j.laa.2019.07.029, https://doi.org/10.1016/j.laa.2019.07.029
9. Yun Cai, Qian Zhang, and Ruifang Hu, 'Iteratively reweighted least squares for block sparse signal recovery with unconstrained $\ell_{2,p}$ minimization', Analysis and Applications 23(2) (2025) 193–212 (published online 2024). DOI: 10.1142/S0219530524500283, https://doi.org/10.1142/S0219530524500283
10. Sergey Voronin and Ingrid Daubechies, 'An iteratively reweighted least squares algorithm for sparse regularization', Contemporary Mathematics 693 (2017) 391–411. DOI: 10.1090/conm/693/13941, https://doi.org/10.1090/conm/693/13941
11. Jean Jacques Fuchs, 'Convergence of a Sparse Representations Algorithm Applicable to Real or Complex Data', IEEE Journal of Selected Topics in Signal Processing 1(4) (2007) 598–605. DOI: 10.1109/JSTSP.2007.909363, https://doi.org/10.1109/JSTSP.2007.909363