A fast iterative thresholding and support-and-scale shrinking algorithm (FITS 3 ) for non-Lipschitz group sparse optimization (I): the case of least-squares fidelity Thanks: Received date, and accepted date (The correct dates will be entered by the editor). Yanan Zhao, Qiaoli Dong, Yufei Zhao, Chunlin Wu Abstract We consider to design a new efficient and easy-to-implement algorithm to solve a general group sparse optimization model with a class of non-convex non-Lipschitz regularizations, named as fast iterative thresholding and support-and-scale shrinking algorithm (FITS 3 ). In this paper we focus on the case of a least-squares fidelity. FITS 3 is designed from a lower bound theory of such models and by integrating thresholding operation, linearization and extrapolation techniques. The FITS 3 has two advantages. Firstly, it is quite efficient and especially suitable for large-scale problems, because it adopts support-and-scale shrinking and does not need to solve any linear or nonlinear system. For two important special cases, the FITS 3 contains only simple calculations like matrix-vector multiplication and soft thresholding. Secondly, the FITS 3 algorithm has a sequence convergence guarantee under proper assumptions. The numerical experiments and comparisons to recent existing non-Lipschitz group recovery algorithms demonstrate that, the proposed FITS 3 achieves similar recovery accuracies, but costs only around a half of the CPU time by the second fastest compared algorithm for median- or large-scale problems. keywords Group sparse recovery; Non-convex non-Lipschitz optimization; Thresholding; Support-and-scale shrinking; Extrapolation; Least-squares {AMS} 49M05, 65K10, 90C26, 90C30 1 Introduction In this paper, we consider the following non-convex and non-Lipschitz group sparse optimization model with a least-squares fidelity \min_{x\in\mathbb{R}^{n}}\left\{\mathcal{E}(x):=\frac{1}{2}\|Ax-b\|_{2}^{2}+\alpha\sum_{g_{i}\in\mathcal{G}}\psi(\|x_{g_{i}}\|_{p})\right\}, (1.1) where A\in\mathbb{R}^{m\times n}(m0 is the regularization parameter, \psi(t):[0,+\infty)\rightarrow[0,+\infty) is a regularization function, p\in[1,+\infty) , \mathcal{G} is the group index set, x=(x_{g_{1}},x_{g_{2}},...,x_{g_{r}})^{\top}\in\mathbb{R}^{n} with x_{g_{i}}\ (g_{i}\in\mathcal{G}) as its i th group. If each g_{i} has only one element, the group sparse reconstruction model ( 1.1 ) degenerates to the conventional non-group reconstruction model. The regularization function \psi considered in this paper is assumed to be concave and non-Lipschitz around 0; see Assumption 2.1 for more details. One example of \psi is \psi(t)=t^{q} ( 00 . Secondly, the objective function \mathcal{E} in ( 1.1 ) is coercive, and thus has always a minimizer. Thirdly, 0 is the strict minimizer of \psi , and thus ( 1.1 ) has a trivial solution 0 if b=0 . Therefore, we consider the case of b\neq 0 in this paper. Assumption 2.1 (ii) implies that \psi is non-Lipschitz. Herein, we list some functions that satisfy Assumption 2.1 : \psi_{1}(t)=t^{q},00 , \psi^{\prime}(t) is L_{c} -Lipschitz continuous on [c,+\infty) , i.e., there exists constant L_{c}>0 determined by c , such that \left|\psi^{\prime}(t)-\psi^{\prime}(s)\right|\leq L_{c}\left|t-s\right|, for any t,s\in[c,+\infty) . (ii) For any w\in\mathbb{R}^{d} and p\geq 1 , the subdifferential of \psi(\|w\|_{p}) is \partial\psi(\|w\|_{p})=\left\{\begin{aligned} &\prod_{j=1}^{d}(-\infty,+\infty),\;\;\text{if}\;\;\|w\|_{p}=0;\\ &\prod_{j=1}^{d}\mu_{j},\qquad\quad\;\;\;\;\text{if}\;\;\|w\|_{p}\neq 0,\end{aligned}\right. (2.4) where \prod means the Cartesian product of sets, and \mu_{j}=\left\{\begin{aligned} &\left\{\psi^{\prime}(\|w\|_{p})\|w\|_{p}^{1-p}|w_{j}|^{p-1}\sgn(w_{j})\right\},\quad p>1;\\ &\left\{\psi^{\prime}(\|w\|_{1})\sgn(w_{j})\right\},\qquad\quad\qquad\;\qquad p=1,w_{j}\neq 0;\\ &[-\psi^{\prime}(\|w\|_{1}),\;\psi^{\prime}(\|w\|_{1})],\;\,\;\qquad\quad\;\;\qquad p=1,w_{j}=0;\end{aligned}\right. with the sign function \sgn(\cdot) . Clearly, the subdifferential of \mathcal{E} in ( 1.1 ) is \partial\mathcal{E}(x)=A^{\top}(Ax-b)+\alpha\prod_{g_{i}\in\mathcal{G}}\partial\psi(\|x_{g_{i}}\|_{p}), where \partial\psi(\|x_{g_{i}}\|_{2}) is calculated by ( 2.4 ). Next, we give two inequalities that will be frequently used in the convergence analysis. Lemma 2.1 . ( [ 25 ] ) For any w\in\mathbb{R}^{d} , 0<\gamma_{1}\leq\gamma_{2} , we have the following inequality \|w\|_{\gamma_{2}}\leq\|w\|_{\gamma_{1}}. (2.5) Lemma 2.2 . ( [ 55 ] ) For any w\in\mathbb{R}^{d} , \gamma>0 , then there exists \widetilde{C}_{\gamma}>0 such that \|w\|_{\gamma}\leq\widetilde{C}_{\gamma}\|w\|_{\gamma+1}, (2.6) particularly, for \gamma=1 it holds that \|w\|_{1}\leq\sqrt{d}\|w\|_{2} . 3 Algorithm In this section, we start from a theorem on lower bound theory, and combine thresholding, linearization method and the extrapolation technique, to develop a new efficient and easy-to-implement algorithm, i.e., the fast iterative thresholding with support-and-scale shrinking algorithm (FITS 3 ) for the non-convex non-Lipschitz minimization problem in ( 1.1 ). Theorem 3.1 . (Lower bound theory) If \mathcal{E} in ( 1.1 ) has a local minimum at x^{*} , then for any g_{i}\in\mathcal{G} , x^{*}_{g_{i}}\neq 0\;\Longrightarrow\;\|x^{*}_{g_{i}}\|_{p}\geq\kappa\text{ with }\kappa=\left\{\begin{aligned} &(\psi^{\prime\prime})^{-1}\left(\frac{-\|A\|_{2}^{2}}{\alpha}\right),\;\quad\;\;\;1\leq p\leq 2,\\ &(\psi^{\prime\prime})^{-1}\left(\frac{-\|A\|_{2}^{2}}{\alpha(\#g_{i})^{1-2/p}}\right),\;p>2.\end{aligned}\right. Proof 3.2 . This proof is a straightforward generalization of [ 23 , Theorem 3.1] . Theorem 3.1 implies a group support inclusion relationship. Suppose that a local minimizer x^{\ast} is very near to some iteration point x^{k} such that \|x^{\ast}-x^{k}\|_{p}<\kappa . Then for g_{i}\in\mathcal{G} with x^{k}_{g_{i}}=0 , \|x^{\ast}_{g_{i}}\|_{p}\leq\|x^{\ast}_{g_{i}}-x^{k}_{g_{i}}\|_{p}+\|x^{k}_{g_{i}}\|_{p}<\kappa , which implies x^{\ast}_{g_{i}}=0 by Theorem 3.1 . Therefore, \mathcal{S}(x^{\ast})\subseteq\mathcal{S}(x^{k}):=\mathcal{S}^{k} . Such support inclusion relationship naturally motivates a group support shrinking strategy at each iteration, like [ 60 , 55 , 23 , 52 ] and references therein. In addition, considering the finite word length of real computers and to avoid extremely large linearization weights described later, we relax the computation of the group support set \mathcal{S}^{k} by using a thresholding operation like [ 23 , 52 , 50 ] . In particular, let \tilde{x}^{k} be as follows \tilde{x}^{k}_{g_{i}}=\left\{\begin{aligned} &x^{k}_{g_{i}},\;\;\;\text{if}\;\,\|x^{k}_{g_{i}}\|_{p}\geq\tau;\\ &0,\quad\;\;\text{if}\;\,\|x^{k}_{g_{i}}\|_{p}<\tau,\end{aligned}\right. for some thresholding parameter \tau , and denote \tilde{\mathcal{S}}^{k}=\mathcal{S}(\tilde{x}^{k}) . Obviously, it holds that \tilde{\mathcal{S}}^{k}\subseteq\mathcal{S}^{k} ( [ 52 ] ). Consequently, given x^{k} , we can compute x^{k+1} by \displaystyle\min_{x\in\mathbb{R}^{n}}\left\{\frac{1}{2}\|Ax-b\|_{2}^{2}+\alpha\sum_{g_{i}\in\tilde{\mathcal{S}}^{k}}\psi(\|x_{g_{i}}\|_{p})\right\} (3.7) \displaystyle\text{s.t.}\;x_{g_{i}}=0,\;\forall g_{i}\in\mathcal{G}\setminus\tilde{\mathcal{S}}^{k}. Note that the problem ( 3.7 ) is still non-convex and cannot be solved directly. Here, we linearize both the fidelity term and the regularization term [ 24 , 60 ] at \tilde{x}^{k} , and x^{k+1} can be computed by \displaystyle\min_{x\in\mathbb{R}^{n}}\left\{\begin{aligned} \frac{1}{2}\|A\tilde{x}^{k}-b\|_{2}^{2}+&(x-\tilde{x}^{k})^{\top}A^{\top}(A\tilde{x}^{k}-b)+\frac{\beta}{2}\|x-\tilde{x}^{k}\|^{2}_{2}+\\ &\alpha\sum_{g_{i}\in\tilde{\mathcal{S}}^{k}}\left[\psi(\|\tilde{x}_{g_{i}}^{k}\|_{p})+\psi^{\prime}(\|\tilde{x}_{g_{i}}^{k}\|_{p})(\|x_{g_{i}}\|_{p}-\|\tilde{x}^{k}_{g_{i}}\|_{p})\right]\end{aligned}\right\} (3.8) \displaystyle\text{s.t.}\;x_{g_{i}}=0,\;\forall g_{i}\in\mathcal{G}\setminus\tilde{\mathcal{S}}^{k}, where \beta>\|A^{\top}A\|_{2} . For ( 3.8 ), we can simply substitute the constraint into the objective function, which not only eliminates constraints but also reduces the scale of the problem. Let B^{k}=A_{\tilde{\mathcal{S}}^{k}} . Clearly, one has A\tilde{x}^{k}=B^{k}\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}} . When the group support set \mathcal{S}(x)\subseteq\tilde{\mathcal{S}}^{k} , we derive that \begin{split}&\frac{1}{2}\|A\tilde{x}^{k}-b\|_{2}^{2}+(x-\tilde{x}^{k})^{\top}A^{\top}(A\tilde{x}^{k}-b)+\frac{\beta}{2}\|x-\tilde{x}^{k}\|^{2}_{2}\\ =&\frac{1}{2}\|B^{k}\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}-b\|_{2}^{2}+(x_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}})^{\top}(B^{k})^{\top}(B^{k}\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}-b)+\frac{\beta}{2}\|x_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}\|^{2}_{2}.\end{split} Therefore, the problem in ( 3.8 ) is equivalent to the following unconstrained minimization problem \left\{\begin{aligned} &x^{k+1}_{\tilde{\mathcal{S}}^{k}}=\arg\min_{x_{\tilde{\mathcal{S}}^{k}}}\left\{\begin{aligned} \frac{1}{2}\|B^{k}\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}-b\|_{2}^{2}+&(x_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}})^{\top}(B^{k})^{\top}(B^{k}\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}-b)+\frac{\beta}{2}\|x_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}\|^{2}_{2}+\\ &\alpha\sum_{g_{i}\in\tilde{\mathcal{S}}^{k}}\left[\psi(\|\tilde{x}_{g_{i}}^{k}\|_{p})+\psi^{\prime}(\|\tilde{x}_{g_{i}}^{k}\|_{p})(\|x_{g_{i}}\|_{p}-\|\tilde{x}^{k}_{g_{i}}\|_{p})\right]\end{aligned}\right\}\\ &x^{k+1}_{\mathcal{G}\setminus\tilde{\mathcal{S}}^{k}}=0.\end{aligned}\right. (3.9) The problem ( 3.9 ) can be solved efficiently. To further speed up the computation, we borrow the idea of the extrapolation technique ( [ 36 , 6 , 60 , 38 ] ), and introduce a new variable z^{k} defined as: \left\{\begin{aligned} &z^{k}_{\tilde{\mathcal{S}}^{k}}=\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}+t_{k}(\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k-1}_{\tilde{\mathcal{S}}^{k}});\\ &z^{k}_{\mathcal{G}\setminus\tilde{\mathcal{S}}^{k}}=0,\end{aligned}\right. (3.10) where t_{k} is the parameter of extrapolation. Note that \mathcal{S}(z^{k})\subseteq\tilde{\mathcal{S}}^{k} . We then propose to update x^{k+1} as follows \left\{\begin{aligned} &x^{k+1}_{\tilde{\mathcal{S}}^{k}}=\arg\min_{x_{\tilde{\mathcal{S}}^{k}}}\left\{\begin{aligned} \frac{1}{2}\|B^{k}z^{k}_{\tilde{\mathcal{S}}^{k}}-b\|_{2}^{2}+&(x_{\tilde{\mathcal{S}}^{k}}-z^{k}_{\tilde{\mathcal{S}}^{k}})^{\top}(B^{k})^{\top}(B^{k}z^{k}_{\tilde{\mathcal{S}}^{k}}-b)+\frac{\beta}{2}\|x_{\tilde{\mathcal{S}}^{k}}-z^{k}_{\tilde{\mathcal{S}}^{k}}\|^{2}_{2}+\\ &\alpha\sum_{g_{i}\in\tilde{\mathcal{S}}^{k}}\left[\psi(\|\tilde{x}_{g_{i}}^{k}\|_{p})+\psi^{\prime}(\|\tilde{x}_{g_{i}}^{k}\|_{p})(\|x_{g_{i}}\|_{p}-\|\tilde{x}^{k}_{g_{i}}\|_{p})\right]\end{aligned}\right\}\\ &x^{k+1}_{\mathcal{G}\setminus\tilde{\mathcal{S}}^{k}}=0.\end{aligned}\right. (3.11) We now define y^{k}=z^{k}_{\tilde{\mathcal{S}}^{k}}-\frac{1}{\beta}(B^{k})^{\top}(B^{k}z^{k}_{\tilde{\mathcal{S}}^{k}}-b), and reformulate ( 3.11 ) as follows x^{k+1}_{g_{i}}=\left\{\begin{aligned} &\text{arg}\min_{x_{g_{i}}}\left\{\frac{\beta}{2}\|x_{g_{i}}-y^{k}_{g_{i}}\|_{2}^{2}+\alpha\psi^{\prime}(\|\tilde{x}_{g_{i}}^{k}\|_{p})\|x_{g_{i}}\|_{p}\right\},\;\;\forall g_{i}\in\tilde{\mathcal{S}}^{k}\\ &0,\;\;\forall g_{i}\in\mathcal{G}\setminus\tilde{\mathcal{S}}^{k},\end{aligned}\right. (3.12) where y^{k}_{g_{i}} is the component of y^{k} . The problem in ( 3.12 ) is a strongly convex problem and there are many efficient methods to solve it, such as the Newton method. For two most interesting cases with p=1 and p=2 , this problem has analytic solutions. When p=1 , its analytic solution is as follows ( [ 20 ] ) x^{k+1}_{j}=\max\left\{|y_{j}^{k}|-\alpha\psi^{\prime}(\|\tilde{x}_{g_{i}}^{k}\|_{1})/\beta,0\right\}\sgn(y_{j}^{k}),\;\forall j\in g_{i},\,g_{i}\in\tilde{\mathcal{S}}^{k}. When p=2 , the analytic solution is the multi-dimensional shrinkage ( [ 48 ] ) x^{k+1}_{g_{i}}=\max\left\{\|y_{g_{i}}^{k}\|_{2}-\alpha\psi^{\prime}(\|\tilde{x}_{g_{i}}^{k}\|_{2})/\beta,0\right\}\frac{y_{g_{i}}^{k}}{\|y_{g_{i}}^{k}\|_{2}},\;\forall g_{i}\in\tilde{\mathcal{S}}^{k}. We mention that with p=1 , the minimization problem ( 1.1 ) is suitable for intra-group sparse recovery ( [ 55 , 25 ] ). When p>1 , p=2 is the most typical choice in ( 1.1 ) ( [ 25 , 23 ] ). In summary, we give the details of the fast iterative thresholding with support and scale shrinking algorithm (FITS 3 ) in Algorithm 1 . Therein \bar{t}\in(0,1] is chosen so that Algorithm 1 is convergent; see Section 4 for details. Algorithm 1 FITS 3 : fast iterative thresholding with support-and-scale shrinking Input \alpha,\beta,\mathrm{Tol},\tau,x^{0},x^{-1}=\tilde{x}^{-1}=x^{0},k=0,\text{MAXit} and \left\{t_{k}\right\}\subset[0,{\bar{t}}) satisfying \sup_{k}t_{k}<{\bar{t}} . while k\leq\text{MAXit} do 1. Thresholding: \tilde{x}^{k}_{g_{i}}=\left\{\begin{aligned} &x^{k}_{g_{i}},\;\;\;\text{if}\;\,\|x^{k}_{g_{i}}\|_{p}\geq\tau;\\ &0,\quad\;\;\text{if}\;\,\|x^{k}_{g_{i}}\|_{p}<\tau.\end{aligned}\right. 2. Find \tilde{\mathcal{S}}^{k}=\left\{g_{i}\in\mathcal{G}:\|\tilde{x}^{k}_{g_{i}}\|_{p}\neq 0\right\} . 3. Update B^{k} and z^{k} : B^{k}=A_{\tilde{\mathcal{S}}^{k}},\qquad\left\{\begin{aligned} &z^{k}_{\tilde{\mathcal{S}}^{k}}=\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}+t_{k}(\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k-1}_{\tilde{\mathcal{S}}^{k}});\\ &z^{k}_{\mathcal{G}\setminus\tilde{\mathcal{S}}^{k}}=0.\end{aligned}\right. 4. Compute y^{k} : y^{k}=z^{k}_{\tilde{\mathcal{S}}^{k}}-\frac{1}{\beta}(B^{k})^{\top}(B^{k}z^{k}_{\tilde{\mathcal{S}}^{k}}-b) . 5. Compute x^{k+1} by solving ( 3.12 ). 6. If \|x^{k+1}-x^{k}\|_{2}/\|x^{k}\|_{2}<\mathrm{Tol} , break. end while return x^{k+1} Remark 3.3 . Here we wish to point out some differences between our FITS 3 algorithm and several typical existing non-convex non-Lipschitz group sparse recovery methods [ 25 , 55 , 23 ] . Our FITS 3 algorithm integrates thresholding, support-and-scale shrinking, linearization and extrapolation techniques, and is applicable to more general non-Lipschitz regularization than \ell_{p,q} regularization. The PGM-GSO in [ 25 ] and the InISSAPL-GSO in [ 55 ] consider the \ell_{p,q} regularization, and the IRLS-th in [ 23 ] is applicable only to \ell_{2,q} regularization. All of these three algorithms do not use extrapolation acceleration. The PGM-GSO in [ 25 ] depends on the proximal operator of regularization term, which is not always explicit. The InISSAPL-GSO in [ 55 ] is with a two-loop algorithmic structure for any p,q . Our FITS 3 algorithm and PGM-GSO do not need to solve any linear system, while both InISSAPL-GSO and IRLS-th solve a linear system at each iteration. Remark 3.4 . We mention that, we got aware very recently of a closely related efficient and sophisticated two-phase method with a shrinkage phase and a subspace optimization phase proposed in [ 50 ] . There are some differences between our FITS 3 and the algorithm in [ 50 ] . First, the algorithm in [ 50 ] was designed for \ell_{1} minimization in non-group sparse reconstruction, while our FITS 3 is for group sparse recovery with a general non-Lipschitz regularization. Second, their algorithm uses continuation and efficient quadratic solvers at each subspace optimization step, while our FITS 3 integrates extrapolation acceleration and linearization technique. 4 Convergence analysis In this section, we give the convergence analysis of the proposed FITS 3 algorithm. Our proof relies on KŁ property [ 29 , 32 ] of a function (or KŁ function) which has extensive applications in analyzing non-convex optimization algorithms [ 2 , 3 , 4 , 8 , 60 , 38 , 23 ] . For convenience of description, we introduce the following auxiliary functions \begin{split}\mathcal{F}^{k}(x)&=\frac{1}{2}\|Az^{k}-b\|_{2}^{2}+(x-z^{k})^{\top}A^{\top}(Az^{k}-b)+\frac{\beta}{2}\|x-z^{k}\|_{2}^{2}\\ &\phantom{=;}+\alpha\sum_{g_{i}\in\tilde{\mathcal{S}}^{k}}\left[\psi(\|\tilde{x}_{g_{i}}^{k}\|_{p})+\psi^{\prime}(\|\tilde{x}_{g_{i}}^{k}\|_{p})(\|x_{g_{i}}\|_{p}-\|\tilde{x}_{g_{i}}^{k}\|_{p})\right],\quad k=0,1,2,\cdots,\end{split} which can be decomposed into \mathcal{F}^{k}(x)=\mathcal{J}_{0}^{k}(x)+\sum_{g_{i}\in\tilde{\mathcal{S}}^{k}}\mathcal{J}_{g_{i}}^{k}(x_{g_{i}}) with \begin{split}\mathcal{J}_{0}^{k}(x)&=\frac{1}{2}\|Az^{k}-b\|_{2}^{2}+\sum_{g_{i}\in\mathcal{G}\setminus\tilde{\mathcal{S}}^{k}}(x_{g_{i}}-z^{k}_{g_{i}})^{\top}(A^{\top}(Az^{k}-b))_{g_{i}}+\frac{\beta}{2}\sum_{g_{i}\in\mathcal{G}\setminus\tilde{\mathcal{S}}^{k}}\|x_{g_{i}}-z^{k}_{g_{i}}\|_{2}^{2},\\ \mathcal{J}_{g_{i}}^{k}(x_{g_{i}})&=(x_{g_{i}}-z^{k}_{g_{i}})^{\top}(A^{\top}(Az^{k}-b))_{g_{i}}+\frac{\beta}{2}\|x_{g_{i}}-z^{k}_{g_{i}}\|_{2}^{2}\\ &\quad+\alpha\left[\psi(\|\tilde{x}_{g_{i}}^{k}\|_{p})+\psi^{\prime}(\|\tilde{x}_{g_{i}}^{k}\|_{p})(\|x_{g_{i}}\|_{p}-\|\tilde{x}_{g_{i}}^{k}\|_{p})\right].\end{split} Note that x_{g_{i}}^{k+1} , g_{i}\in\tilde{\mathcal{S}}^{k} in ( 3.12 ) is essentially updated by solving \displaystyle\min_{x_{g_{i}}}\,\mathcal{J}_{g_{i}}^{k}(x_{g_{i}}). (4.13) We will establish our convergence result under the following (inexact) condition that \lambda^{k+1}_{g_{i}}\in\partial\mathcal{J}_{g_{i}}^{k}(x^{k+1}_{g_{i}})\,\,\mbox{with}\,\,\|\lambda^{k+1}_{g_{i}}\|_{2}\leq\frac{\beta\varepsilon}{2}\|x^{k+1}_{g_{i}}-\tilde{x}^{k}_{g_{i}}\|_{2},\quad g_{i}\in\tilde{\mathcal{S}}^{k} (4.14) exists for a given \varepsilon\in[0,1) , since the subproblem ( 4.13 ) needs an iterative solver for p rather than 1 and 2. It is worthy to notice that ( 4.14 ) implies \|\lambda^{k+1}_{\tilde{\mathcal{S}}^{k}}\|_{2}\leq\frac{\beta\varepsilon}{2}\|x^{k+1}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}\|_{2}, (4.15) no matter how \lambda^{k+1}_{g_{i}}, g_{i}\in\mathcal{G}\setminus\tilde{\mathcal{S}}^{k} are chosen. Because of the (inexact) condition, we let in Algorithm 1 {\bar{t}}\overset{\triangle}{=}{\bar{t}}(\varepsilon)=\frac{\sqrt{(\beta+\|A^{\top}A\|_{2})^{2}-4\beta\varepsilon\|A^{\top}A\|_{2}}-(\beta-\|A^{\top}A\|_{2})}{2\|A^{\top}A\|_{2}}\in(0,1] for the latter convergence analysis. Remark 4.1 . If p=1 or p=2 in our FITS 3 algorithm, we can let \varepsilon=0 in ( 4.14 ) and ( 4.15 ), and thus have {\bar{t}}=1 , due to the closed form solutions given in Section 3 . We first observe a finite convergence property of the group support sets. According to Algorithm 1 , \tilde{\mathcal{S}}^{k+1}\subseteq\mathcal{S}^{k+1}\subseteq\tilde{\mathcal{S}}^{k}\subseteq\mathcal{S}^{k} holds, like [ 52 ] and references therein. Since \mathcal{G} is a finite set and \tilde{\mathcal{S}}^{k}\subseteq\mathcal{S}^{k}\subseteq\mathcal{G} , there exists an integer K>0 such that \tilde{\mathcal{S}}^{k}\equiv\mathcal{S}^{k}\equiv\mathcal{S}^{K},\;\forall k\geq K. (4.16) Subsequently, one has \tilde{x}^{k}\equiv x^{k},\;\forall k\geq K . We now present some lemmas where the following value function \mathcal{H}(x,u)=\mathcal{E}(x)+\frac{\beta(1-\varepsilon)}{2}\|x-u\|_{2}^{2}, (4.17) plays a key role. Lemma 4.2 . For any \beta>\|A^{\top}A\|_{2} and the extrapolation parameters \left\{t_{k}\right\}\subset[0,{\bar{t}}) satisfying \hat{t}=\sup_{k}t_{k}<{\bar{t}} , let \left\{x^{k}\right\} be a sequence generated by FITS 3 . Then, the following properties hold: (i) For any k\geq K+1 , the sequence \left\{\mathcal{H}(x^{k},x^{k-1})\right\} is monotonically nonincreasing. In particular, it holds that \mathcal{H}(x^{k},x^{k-1})-\mathcal{H}(x^{k+1},x^{k})\geq\left(-\frac{\|A^{\top}A\|_{2}}{2}\hat{t}^{2}-\frac{\beta-\|A^{\top}A\|_{2}}{2}\hat{t}+\frac{\beta(1-\varepsilon)}{2}\right)\|x^{k}-x^{k-1}\|_{2}^{2}. (ii) \lim_{k\to\infty}\|x^{k}-x^{k-1}\|_{2}=0 and the sequence \left\{x^{k}\right\} is bounded. (iii) \zeta:=\lim_{k\to\infty}\mathcal{E}(x^{k}) exists. Moreover, \mathcal{E}\equiv\zeta on \Omega , where \Omega is the set of accumulation points of \left\{x^{k}\right\} . (iv) \lim_{k\to\infty}\mathcal{H}(x^{k},x^{k-1})=\zeta . Moreover, \mathcal{H}\equiv\zeta on \Upsilon , where \Upsilon:=\left\{(x,x):x\in\Omega\right\} is the set of accumulation points of \left\{(x^{k},x^{k-1})\right\} . Proof 4.3 . (i) Letting x=\tilde{x}^{k} in \mathcal{F}^{k}(x) , we get \mathcal{F}^{k}(\tilde{x}^{k})=\frac{1}{2}\|Az^{k}-b\|_{2}^{2}+(\tilde{x}^{k}-z^{k})^{\top}A^{\top}(Az^{k}-b)+\frac{\beta}{2}\|\tilde{x}^{k}-z^{k}\|_{2}^{2}+\alpha\sum_{g_{i}\in\tilde{\mathcal{S}}^{k}}\psi(\|\tilde{x}_{g_{i}}^{k}\|_{p}). By the second-order Taylor expansion of \frac{1}{2}\|Ax-b\|_{2}^{2} at z^{k} , we can derive that \begin{split}\mathcal{F}^{k}(\tilde{x}^{k})=\mathcal{E}(\tilde{x}^{k})-\frac{1}{2}(\tilde{x}^{k}-z^{k})^{\top}A^{\top}A(\tilde{x}^{k}-z^{k})+\frac{\beta}{2}\|\tilde{x}^{k}-z^{k}\|_{2}^{2}.\end{split} Clearly, the following holds \mathcal{F}^{k}(\tilde{x}^{k})\leq\mathcal{E}(\tilde{x}^{k})+\frac{\beta}{2}\|\tilde{x}^{k}-z^{k}\|_{2}^{2}. (4.18) Recalling z^{k} in ( 3.10 ), one has \begin{split}\|\tilde{x}^{k}-z^{k}\|_{2}^{2}=t_{k}^{2}\|\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k-1}_{\tilde{\mathcal{S}}^{k}}\|_{2}^{2}\leq t_{k}^{2}\|\tilde{x}^{k}-\tilde{x}^{k-1}\|_{2}^{2}.\end{split} (4.19) Combining ( 4.18 ) and ( 4.19 ), we get \mathcal{F}^{k}(\tilde{x}^{k})\leq\mathcal{E}(\tilde{x}^{k})+\frac{\beta}{2}t_{k}^{2}\|\tilde{x}^{k}-\tilde{x}^{k-1}\|_{2}^{2}. (4.20) Now, we consider those x ’s satisfying \mathcal{S}(x)\subseteq\tilde{\mathcal{S}}^{k} . By the concavity of \psi and the fact \psi(\|x_{g_{i}}\|_{p})=0,\;\forall g_{i}\in\mathcal{G}\setminus\tilde{\mathcal{S}}^{k} when \mathcal{S}(x)\subseteq\tilde{\mathcal{S}}^{k} , we have \begin{split}\mathcal{F}^{k}(x)&\geq\frac{1}{2}\|Az^{k}-b\|_{2}^{2}+(x-z^{k})^{\top}A^{\top}(Az^{k}-b)+\frac{\beta}{2}\|x-z^{k}\|_{2}^{2}+\alpha\sum_{g_{i}\in\tilde{\mathcal{S}}^{k}}\psi(\|x_{g_{i}}\|_{p})\\ &=\frac{1}{2}\|Az^{k}-b\|_{2}^{2}+(x-z^{k})^{\top}A^{\top}(Az^{k}-b)+\frac{\beta}{2}\|x-z^{k}\|_{2}^{2}+\alpha\sum_{g_{i}\in\mathcal{G}}\psi(\|x_{g_{i}}\|_{p}).\end{split} Therefore, it holds that for x satisfying \mathcal{S}(x)\subseteq\tilde{\mathcal{S}}^{k} , \mathcal{F}^{k}(x)\geq\mathcal{E}(x)+\frac{\beta-\|A^{\top}A\|_{2}}{2}\|x-z^{k}\|_{2}^{2}. (4.21) Letting x=x^{k+1} in ( 4.21 ), we get \mathcal{F}^{k}(x^{k+1})\geq\mathcal{E}(x^{k+1})+\frac{\beta-\|A^{\top}A\|_{2}}{2}\|x^{k+1}-z^{k}\|_{2}^{2}. (4.22) By the definition of z^{k} , we have \|x^{k+1}-z^{k}\|_{2}^{2}=\|x^{k+1}_{\tilde{\mathcal{S}}^{k}}-z^{k}_{\tilde{\mathcal{S}}^{k}}\|_{2}^{2}=\|(x^{k+1}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}})-t_{k}(\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k-1}_{\tilde{\mathcal{S}}^{k}})\|_{2}^{2}. (4.23) Applying the inequality \|a-tb\|_{2}^{2}\geq(1-t)\|a\|_{2}^{2}+t(t-1)\|b\|_{2}^{2}~(t\geq 0) to ( 4.23 ) yields \|(x^{k+1}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}})-t_{k}(\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k-1}_{\tilde{\mathcal{S}}^{k}})\|_{2}^{2}\geq(1-t_{k})\|x^{k+1}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}\|_{2}^{2}+t_{k}(t_{k}-1)\|\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k-1}_{\tilde{\mathcal{S}}^{k}}\|_{2}^{2}. (4.24) Obviously, the following relationships hold \|x^{k+1}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}\|_{2}^{2}=\|x^{k+1}-\tilde{x}^{k}\|_{2}^{2},\;\|\tilde{x}^{k}_{\tilde{\mathcal{S}}^{k}}-\tilde{x}^{k-1}_{\tilde{\mathcal{S}}^{k}}\|_{2}^{2}\leq\|\tilde{x}^{k}-\tilde{x}^{k-1}\|_{2}^{2}. (4.25) Combining ( 4.22 )-( 4.25 ) and using t_{k}\in[0,\bar{t}),\beta>\|A^{\top}A\|_{2} , we get \begin{split}\mathcal{F}^{k}(x^{k+1})&\geq\mathcal{E}(x^{k+1})+\frac{\beta-\|A^{\top}A\|_{2}}{2}(1-t_{k})\|x^{k+1}-\tilde{x}^{k}\|_{2}^{2}\\ &\quad+\frac{\beta-\|A^{\top}A\|_{2}}{2}t_{k}(t_{k}-1)\|\tilde{x}^{k}-\tilde{x}^{k-1}\|_{2}^{2}.\end{split} (4.26) Since \mathcal{J}_{g_{i}}^{k}(x_{g_{i}}) is a \beta -strongly convex function and x^{k+1}_{g_{i}} solves ( 4.13 ) satisfying ( 4.14 ), one has \begin{split}\mathcal{J}_{g_{i}}^{k}(\tilde{x}^{k}_{g_{i}})\geq&\mathcal{J}_{g_{i}}^{k}(x^{k+1}_{g_{i}})+\langle\lambda^{k+1}_{g_{i}},\tilde{x}^{k}_{g_{i}}-x^{k+1}_{g_{i}}\rangle+\frac{\beta}{2}\|\tilde{x}^{k}_{g_{i}}-x^{k+1}_{g_{i}}\|_{2}^{2}\\ \geq&\mathcal{J}_{g_{i}}^{k}(x^{k+1}_{g_{i}})-\|\lambda^{k+1}_{g_{i}}\|\|\tilde{x}^{k}_{g_{i}}-x^{k+1}_{g_{i}}\|+\frac{\beta}{2}\|\tilde{x}^{k}_{g_{i}}-x^{k+1}_{g_{i}}\|_{2}^{2}\\ \geq&\mathcal{J}_{g_{i}}^{k}(x^{k+1}_{g_{i}})+\frac{\beta(1-\varepsilon)}{2}\|\tilde{x}^{k}_{g_{i}}-x^{k+1}_{g_{i}}\|_{2}^{2}.\\ \end{split} Furthermore, \mathcal{J}_{0}^{k}(\tilde{x}^{k})=\mathcal{J}_{0}^{k}(x^{k+1})=\frac{1}{2}\|Az^{k}-b\|_{2}^{2} . Therefore, we have \begin{split}\mathcal{F}^{k}(\tilde{x}^{k})\geq&\mathcal{F}^{k}(x^{k+1})+\frac{\beta(1-\varepsilon)}{2}\|\tilde{x}^{k}-x^{k+1}\|_{2}^{2}.\\ \end{split} (4.27) Combining ( 4.20 ) ( 4.26 ) ( 4.27 ), we get \begin{split}\mathcal{E}(\tilde{x}^{k})+\frac{\beta}{2}t_{k}^{2}\|\tilde{x}^{k}-\tilde{x}^{k-1}\|_{2}^{2}\geq&\mathcal{E}(x^{k+1})+\frac{\beta-\|A^{\top}A\|_{2}}{2}(1-t_{k})\|x^{k+1}-\tilde{x}^{k}\|_{2}^{2}\\ &+\frac{\beta-\|A^{\top}A\|_{2}}{2}t_{k}(t_{k}-1)\|\tilde{x}^{k}-\tilde{x}^{k-1}\|_{2}^{2}+\frac{\beta(1-\varepsilon)}{2}\|\tilde{x}^{k}-x^{k+1}\|_{2}^{2}\\ \geq&\mathcal{E}(x^{k+1})+\frac{\beta-\|A^{\top}A\|_{2}}{2}t_{k}(t_{k}-1)\|\tilde{x}^{k}-\tilde{x}^{k-1}\|_{2}^{2}\\ &+\frac{\beta(1-\varepsilon)}{2}\|\tilde{x}^{k}-x^{k+1}\|_{2}^{2}.\end{split} By the definition of \mathcal{H} in ( 4.17 ), the above inequality can be written as \mathcal{H}(\tilde{x}^{k},\tilde{x}^{k-1})-\mathcal{H}(x^{k+1},\tilde{x}^{k})\geq\left(-\frac{\|A^{\top}A\|_{2}}{2}t_{k}^{2}-\frac{\beta-\|A^{\top}A\|_{2}}{2}t_{k}+\frac{\beta(1-\varepsilon)}{2}\right)\|\tilde{x}^{k}-\tilde{x}^{k-1}\|_{2}^{2}. Since \tilde{x}^{k}=x^{k} and \tilde{x}^{k-1}=x^{k-1} hold when k\geq K+1 , we have, for \forall k\geq K+1 , \mathcal{H}(x^{k},x^{k-1})-\mathcal{H}(x^{k+1},x^{k})\geq\left(-\frac{\|A^{\top}A\|_{2}}{2}t_{k}^{2}-\frac{\beta-\|A^{\top}A\|_{2}}{2}t_{k}+\frac{\beta(1-\varepsilon)}{2}\right)\|x^{k}-x^{k-1}\|_{2}^{2}. (4.28) Due to our assumption that \left\{t_{k}\right\}\subset[0,{\bar{t}}) and \hat{t}=\sup_{k}t_{k}<{\bar{t}} , the following holds \begin{split}-\frac{\|A^{\top}A\|_{2}}{2}t_{k}^{2}-\frac{\beta-\|A^{\top}A\|_{2}}{2}t_{k}+\frac{\beta(1-\varepsilon)}{2}&\geq\left(-\frac{\|A^{\top}A\|_{2}}{2}\hat{t}^{2}-\frac{\beta-\|A^{\top}A\|_{2}}{2}\hat{t}+\frac{\beta(1-\varepsilon)}{2}\right)\\ &>0.\end{split} (4.29) Therefore, for any k\geq K+1 , the sequence \left\{\mathcal{H}(x^{k},x^{k-1})\right\} is monotonically nonincreasing. (ii) Summing up both sides of ( 4.28 ) from k=K+1 to N and using ( 4.29 ), we get \begin{split}&\left(-\frac{\|A^{\top}A\|_{2}}{2}\hat{t}^{2}-\frac{\beta-\|A^{\top}A\|_{2}}{2}\hat{t}+\frac{\beta(1-\varepsilon)}{2}\right)\sum_{k=K+1}^{N}\|x^{k}-x^{k-1}\|_{2}^{2}\\ &\leq\mathcal{H}(x^{K+1},x^{K})-\mathcal{H}(x^{N+1},x^{N}).\end{split} Let N\to\infty yields \left(-\frac{\|A^{\top}A\|_{2}}{2}\hat{t}^{2}-\frac{\beta-\|A^{\top}A\|_{2}}{2}\hat{t}+\frac{\beta(1-\varepsilon)}{2}\right)\sum_{k=K+1}^{\infty}\|x^{k}-x^{k-1}\|_{2}^{2}\leq\mathcal{H}(x^{K+1},x^{K}). It follows that \sum_{k=0}^{\infty}\|x^{k+1}-x^{k}\|_{2}^{2}<+\infty . Thus \lim_{k\to\infty}\|x^{k+1}-x^{k}\|_{2}=0 . For any k\geq K+1 , the sequence \left\{\mathcal{H}(x^{k},x^{k-1})\right\} is monotonically nonincreasing, so we have \mathcal{E}(x^{k})\leq\mathcal{H}(x^{k},x^{k-1})\leq\mathcal{H}(x^{K+1},x^{K}),\;\forall k\geq K+1. Therefore, the sequence \left\{x^{k}\right\}_{k\geq K+1} is bounded due to the coercivity of \mathcal{E}(x) . Furthermore, the whole sequence \left\{x^{k}\right\} is also bounded, because K is a finite integer. (iii) The nonnegative sequence \left\{\mathcal{H}(x^{k},x^{k-1})\right\}_{k\geq K+1} is monotonically nonincreasing, so \left\{\mathcal{H}(x^{k},x^{k-1})\right\} is convergent. Then, the sequence \left\{\mathcal{E}(x^{k})\right\} is also convergent due to \lim_{k\to\infty}\|x^{k+1} -x^{k}\|_{2}=0 . Thus \zeta:=\lim_{k\to\infty}\mathcal{E}(x^{k}) exists. Since \mathcal{E} is a continuous funciton, one has \mathcal{E}\equiv\zeta on \Omega . (iv) Since \lim_{k\to\infty}\mathcal{E}(x^{k})=\zeta and \lim_{k\to\infty}\|x^{k+1}-x^{k}\|_{2}=0 , thus \lim_{k\to\infty}\mathcal{H}(x^{k},x^{k-1})=\zeta . Since \mathcal{H} is a continuous function, then \mathcal{H}\equiv\zeta on \Upsilon . This completes the proof. Before proceeding, we calculate the subdifferential of \mathcal{J}_{g_{i}}^{k}(x_{g_{i}}) , g_{i}\in\tilde{\mathcal{S}}^{k} to consider ( 4.14 ). In particular, we have \lambda^{k+1}_{g_{i}}\in(A^{\top}(Az^{k}-b))_{g_{i}}+\beta(x^{k+1}_{g_{i}}-z^{k}_{g_{i}})+\alpha\psi^{\prime}(\|\tilde{x}_{g_{i}}^{k}\|_{p})\partial\|\cdot\|_{p}(x^{k+1}_{g_{i}}),\;\forall g_{i}\in\tilde{\mathcal{S}}^{k}. (4.30) Since for any k\geq K , \tilde{\mathcal{S}}^{k}=\mathcal{S}^{k} and \tilde{x}^{k}=x^{k} hold, by ( 2.4 ), ( 4.30 ) indicates • For p>1,\forall j\in g_{i} with g_{i}\in\mathcal{S}^{k},k\geq K , we have \begin{split}\lambda^{k+1}_{j}=&(A^{\top}(Az^{k}-b))_{j}+\beta(x^{k+1}-z^{k})_{j}\\ &+\alpha\psi^{\prime}(\|x_{g_{i}}^{k}\|_{p})\|x_{g_{i}}^{k+1}\|_{p}^{1-p}|x_{j}^{k+1}|^{p-1}\sgn(x_{j}^{k+1});\end{split} (4.31) • For p=1,\forall j\in s(x^{k+1}_{g_{i}}) with g_{i}\in\mathcal{S}^{k},k\geq K , we have \begin{split}\lambda^{k+1}_{j}=(A^{\top}(Az^{k}-b))_{j}+\beta(x^{k+1}-z^{k})_{j}+\alpha\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1})\sgn(x_{j}^{k+1});\end{split} (4.32) • For p=1,\forall j\in g_{i}\backslash s(x^{k+1}_{g_{i}}) with g_{i}\in\mathcal{S}^{k},k\geq K , we have \begin{split}\lambda^{k+1}_{j}\in(A^{\top}(Az^{k}-b))_{j}+\beta(x^{k+1}-z^{k})_{j}+\alpha[-\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1}),\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1})].\end{split} (4.33) The next lemma provides a lower bound and upper bound theory for the iterative sequence \left\{x^{k}\right\} . Lemma 4.4 . For any \beta>\|A^{\top}A\|_{2} and the extrapolation parameters \left\{t_{k}\right\}\subset[0,{\bar{t}}) satisfying \sup_{k}t_{k}<{\bar{t}} , let \left\{x^{k}\right\} be a sequence generated by FITS 3 . Then for any k\geq K+1 , (i) \|x_{g_{i}}^{k}\|_{p}\leq\overline{c}:=\psi^{-1}\left(\frac{\mathcal{H}(x^{K+1},x^{K})}{\alpha}\right) , for any g_{i}\in\mathcal{G} . (ii) \|x_{g_{i}}^{k}\|_{p}\geq\underline{c}:=\max\left\{(\psi^{\prime})^{-1}\left(\frac{(2\|A^{\top}A\|_{2}+\beta(4+\varepsilon)+2\|A\|_{2}\sqrt{\beta(1-\varepsilon)})\sqrt{n\mathcal{H}(x^{K+1},x^{K})}}{\alpha\sqrt{2\beta(1-\varepsilon)}}\right),\tau\right\} , for any g_{i}\in\mathcal{S}^{k} . Proof 4.5 . Since in Lemma 4.2 , the sequence \left\{\mathcal{H}(x^{k},x^{k-1})\right\} is nonincreasing for any k\geq K+1 , one has \begin{split}\mathcal{H}(x^{k},x^{k-1})\leq\mathcal{H}(x^{K+1},x^{K}),\;\forall k\geq K+1,\end{split} (4.34) which indicates \alpha\psi(\|x_{g_{i}}^{k}\|_{p})\leq\mathcal{H}(x^{K+1},x^{K}) . Then, one has \begin{split}\|x_{g_{i}}^{k}\|_{p}\leq\psi^{-1}\left(\frac{\mathcal{H}(x^{K+1},x^{K})}{\alpha}\right):=\overline{c},\;\forall k\geq K+1.\end{split} We next prove that any \|x_{g_{i}}^{k}\|_{p}\neq 0 with g_{i}\in\mathcal{S}^{k},k\geq K has a uniform lower bound. Obviously, \|x_{g_{i}}^{k}\|_{p} with g_{i}\in\mathcal{S}^{k},k\geq K has a lower bound \tau . In the following, we show that \|x_{g_{i}}^{k}\|_{p} with g_{i}\in\mathcal{S}^{k},k\geq K has also a positive lower bound independent of \tau . We discuss two cases with p>1 and p=1 separately. Firstly, we consider that p>1 . It follows from ( 4.31 ) that for any j\in g_{i} with g_{i}\in\mathcal{S}^{k},k\geq K , \alpha\psi^{\prime}(\|x_{g_{i}}^{k}\|_{p})\|x_{g_{i}}^{k+1}\|_{p}^{1-p}|x_{j}^{k+1}|^{p-1}=\left|\left(A^{\top}(Az^{k}-b)+\beta(x^{k+1}-z^{k})-\lambda^{k+1}\right)_{j}\right|. Adding up the above equations for all j\in g_{i} with g_{i}\in\mathcal{S}^{k},k\geq K , we get \alpha\psi^{\prime}(\|x_{g_{i}}^{k}\|_{p})\|x_{g_{i}}^{k+1}\|_{p}^{1-p}\|x_{g_{i}}^{k+1}\|_{p-1}^{p-1}=\left\|\left(A^{\top}(Az^{k}-b)+\beta(x^{k+1}-z^{k})-\lambda^{k+1}\right)_{g_{i}}\right\|_{1}. Due to Lemma 2.1 , we see \|x_{g_{i}}^{k+1}\|_{p}^{1-p}\|x_{g_{i}}^{k+1}\|_{p-1}^{p-1}\geq 1 . Therefore, by Lemma 2.2 , we have for g_{i}\in\mathcal{S}^{k},k\geq K+1 that \begin{split}\alpha\psi^{\prime}(\|x_{g_{i}}^{k}\|_{p})\leq&\left\|\left(A^{\top}(Az^{k}-b)+\beta(x^{k+1}-z^{k})-\lambda^{k+1}\right)_{g_{i}}\right\|_{1}\\ \leq&\|A^{\top}(Az^{k}-b)\|_{1}+\beta\|x^{k+1}-z^{k})\|_{1}+\|\lambda^{k+1}_{{\mathcal{S}}^{k}}\|_{1}\\ [~\text{by~\eqref{eq_inexact_condition2}}~]~\leq&\sqrt{n}\|A^{\top}(Az^{k}-Ax^{k}+Ax^{k}-b)\|_{2}+\sqrt{n}\beta\|(x^{k+1}_{\mathcal{S}^{k}}-x^{k}_{\mathcal{S}^{k}})-t_{k}(x^{k}_{\mathcal{S}^{k}}-x^{k-1}_{\mathcal{S}^{k}})\|_{2}\\ &+\frac{\beta\varepsilon}{2}\sqrt{n}\|x^{k+1}-\tilde{x}^{k}\|_{2}\\ \leq&\sqrt{n}(\|A^{\top}A\|_{2}\|x^{k}-x^{k-1}\|_{2}+\|A\|_{2}\|Ax^{k}-b\|_{2})+\sqrt{n}\beta(\|x^{k+1}-x^{k}\|_{2}\\ &+\|x^{k}-x^{k-1}\|_{2})+\frac{\beta\varepsilon}{2}\sqrt{n}\|x^{k+1}-x^{k}\|_{2}.\\ \end{split} (4.35) By ( 4.34 ), one has \|x^{k+1}-x^{k}\|_{2}\leq\sqrt{2\mathcal{H}(x^{K+1},x^{K})/\beta(1-\varepsilon)} , \|x^{k}-x^{k-1}\|_{2}\leq\sqrt{2\mathcal{H}(x^{K+1},x^{K})/\beta(1-\varepsilon)} and \|Ax^{k}-b\|_{2}\leq\sqrt{2\mathcal{H}(x^{K+1},x^{K})} for k\geq K+1 . Therefore, we get for k\geq K+1 , \psi^{\prime}(\|x_{g_{i}}^{k}\|_{p})\leq\frac{\sqrt{n}(2\|A^{\top}A\|_{2}+\beta(4+\varepsilon)+2\|A\|_{2}\sqrt{\beta(1-\varepsilon)})\sqrt{\mathcal{H}(x^{K+1},x^{K})}}{\alpha\sqrt{2\beta(1-\varepsilon)}}. Since \psi is a concave function, one has for k\geq K+1 , \|x_{g_{i}}^{k}\|_{p}\geq(\psi^{\prime})^{-1}\left(\frac{\sqrt{n}(2\|A^{\top}A\|_{2}+\beta(4+\varepsilon)+2\|A\|_{2}\sqrt{\beta(1-\varepsilon)})\sqrt{\mathcal{H}(x^{K+1},x^{K})}}{\alpha\sqrt{2\beta(1-\varepsilon)}}\right). Next, we consider the case that p=1 . ( 4.32 ) implies for any j\in s(x^{k+1}_{g_{i}}) with g_{i}\in\mathcal{S}^{k},k\geq K+1 , \begin{split}\alpha\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1})\leq&\|A^{\top}(Az^{k}-b)\|_{1}+\beta\|x^{k+1}-z^{k})\|_{1}+\|\lambda^{k+1}_{{\mathcal{S}}^{k}}\|_{1},\\ \end{split} which is exactly a similar inequality as the second inequality in ( 4.35 ). We can therefore derive for k\geq K+1 , \|x_{g_{i}}^{k}\|_{1}\geq(\psi^{\prime})^{-1}\left(\frac{\sqrt{n}(2\|A^{\top}A\|_{2}+\beta(4+\varepsilon)+2\|A\|_{2}\sqrt{\beta(1-\varepsilon)})\sqrt{\mathcal{H}(x^{K+1},x^{K})}}{\alpha\sqrt{2\beta(1-\varepsilon)}}\right). This completes the proof. Lemma 4.4 and Remark 2.1 (i) indicate that there exists L_{\underline{c}}>0 such that for any g_{i}\in\mathcal{S}^{k},\;k\geq K+1 , \left|\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{p})-\psi^{\prime}(\|x_{g_{i}}^{k}\|_{p})\right|\leq L_{\underline{c}}\left|\|x_{g_{i}}^{k+1}\|_{p}-\|x_{g_{i}}^{k}\|_{p}\right|\leq L_{\underline{c}}\|x_{g_{i}}^{k+1}-x_{g_{i}}^{k}\|_{p}. (4.36) Lemma 4.6 . For the extrapolation parameters \left\{t_{k}\right\}\subset[0,{\bar{t}}) , let \left\{x^{k}\right\} be a sequence generated by FITS 3 . Then for each k\geq K+1 , there exist \nu^{k+1}\in\partial\mathcal{E}(x^{k+1}) such that \|\nu^{k+1}\|_{2}\leq\Gamma_{1}\|x^{k+1}-x^{k}\|_{2}+\Gamma_{2}\|x^{k}-x^{k-1}\|_{2}, (4.37) and \gamma^{k+1}\in\partial\mathcal{H}(x^{k+1},x^{k}) such that \|\gamma^{k+1}\|_{2}\leq\Gamma_{3}\|x^{k+1}-x^{k}\|_{2}+\Gamma_{2}\|x^{k}-x^{k-1}\|_{2}, (4.38) with \Gamma_{1}=\max\left\{(\|A^{\top}A\|_{2}+\beta+\alpha(\widetilde{C}_{p-1})^{p-1}L_{\underline{c}}+\frac{\beta\varepsilon}{2})\sqrt{n},(\|A^{\top}A\|_{2}+\beta+\frac{\beta\varepsilon}{2}+n\alpha L_{\underline{c}})\sqrt{n}\right\} , \Gamma_{2}=(\|A^{\top}A\|_{2}+\beta)\sqrt{n},\ \Gamma_{3}=\Gamma_{1}+\sqrt{2}\beta(1-\varepsilon), and a constant \widetilde{C}_{p-1} defined in ( 2.6 ). Proof 4.7 . We will discuss p>1 and p=1 separately. (1) The case of p>1 . Let k\geq K+1 and define \nu^{k+1} by \small\left\{\begin{aligned} \nu_{j}^{k+1}&=(A^{\top}(Ax^{k+1}-b))_{j}+\alpha\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{p})\|x_{g_{i}}^{k+1}\|_{p}^{1-p}|x_{j}^{k+1}|^{p-1}\sgn(x_{j}^{k+1}),\;\forall j\in g_{i}\,,\,g_{i}\in\mathcal{S}^{k};\\ \nu_{j}^{k+1}&=0,\hskip 9.24994pt\forall j\in g_{i}\,,\,g_{i}\in\mathcal{G}\setminus\mathcal{S}^{k}.\end{aligned}\right. (4.39) According to the subdifferential in ( 2.4 ), one has \nu^{k+1}\in\partial\mathcal{E}(x^{k+1}) . Recall ( 4.31 ) that for any j\in g_{i} with g_{i}\in\mathcal{S}^{k},k\geq K \begin{split}\lambda^{k+1}_{j}=(A^{\top}(Az^{k}-b))_{j}+\beta(x^{k+1}-z^{k})_{j}+\alpha\psi^{\prime}(\|x_{g_{i}}^{k}\|_{p})\|x_{g_{i}}^{k+1}\|_{p}^{1-p}|x_{j}^{k+1}|^{p-1}\sgn(x_{j}^{k+1}).\end{split} (4.40) Combining ( 4.39 ) and ( 4.40 ), we obtain that for any j\in g_{i} with g_{i}\in\mathcal{S}^{k},k\geq K+1 \small\begin{split}\nu_{j}^{k+1}=&(A^{\top}A(x^{k+1}-z^{k}))_{j}-\beta(x^{k+1}-z^{k})_{j}+\lambda^{k+1}_{j}\\ &+\alpha\|x_{g_{i}}^{k+1}\|_{p}^{1-p}|x_{j}^{k+1}|^{p-1}\sgn(x_{j}^{k+1})\left(\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{p})-\psi^{\prime}(\|x_{g_{i}}^{k}\|_{p})\right).\end{split} (4.41) From ( 4.41 ) and using ( 4.36 ), we get \small\begin{split}|\nu_{j}^{k+1}|\leq|(A^{\top}A(x^{k+1}-z^{k}))_{j}|+\beta|(x^{k+1}-z^{k})_{j}|+|\lambda^{k+1}_{j}|+\alpha L_{\underline{c}}\|x_{g_{i}}^{k+1}\|_{p}^{1-p}|x_{j}^{k+1}|^{p-1}\|x_{g_{i}}^{k+1}-x_{g_{i}}^{k}\|_{p}.\end{split} (4.42) Adding up all j\in g_{i} for g_{i}\in\mathcal{S}^{k},k\geq K+1 in ( 4.42 ) yields \begin{split}\|\nu_{g_{i}}^{k+1}\|_{1}\leq&\|(A^{\top}A(x^{k+1}-z^{k}))_{g_{i}}\|_{1}+\beta\|(x^{k+1}-z^{k})_{g_{i}}\|_{1}+\|\lambda^{k+1}_{g_{i}}\|_{1}\\ &+\alpha L_{\underline{c}}\|x_{g_{i}}^{k+1}\|_{p}^{1-p}\|x_{g_{i}}^{k+1}\|_{p-1}^{p-1}\|x_{g_{i}}^{k+1}-x_{g_{i}}^{k}\|_{p}.\end{split} (4.43) By Lemma 2.1 and Lemma 2.2 , one has \begin{split}\alpha L_{\underline{c}}\|x_{g_{i}}^{k+1}\|_{p}^{1-p}\|x_{g_{i}}^{k+1}\|_{p-1}^{p-1}\|x_{g_{i}}^{k+1}-x_{g_{i}}^{k}\|_{p}&\leq\alpha(\widetilde{C}_{p-1})^{p-1}L_{\underline{c}}\|x_{g_{i}}^{k+1}-x_{g_{i}}^{k}\|_{p}\\ &\leq\alpha(\widetilde{C}_{p-1})^{p-1}L_{\underline{c}}\|x_{g_{i}}^{k+1}-x_{g_{i}}^{k}\|_{1},\end{split} (4.44) where \widetilde{C}_{p-1} is a constant. Combining ( 4.43 ) and ( 4.44 ) and using Lemma 2.2 , we get \begin{split}&\|\nu^{k+1}\|_{1}\\ &\leq\sqrt{n}\left(\|A^{\top}A(x^{k+1}-z^{k})\|_{2}+\beta\|x^{k+1}-z^{k}\|_{2}+\|\lambda^{k+1}_{{\mathcal{S}}^{k}}\|_{2}+\alpha(\widetilde{C}_{p-1})^{p-1}L_{\underline{c}}\|x^{k+1}-x^{k}\|_{2}\right).\end{split} Recalling ( 4.15 ) and the definition of z^{k} in ( 3.10 ), one has for k\geq K+1 that \begin{split}\|\nu^{k+1}\|_{1}\leq&\left(\|A^{\top}A\|_{2}+\beta+\alpha(\widetilde{C}_{p-1})^{p-1}L_{\underline{c}}+\frac{\beta\varepsilon}{2}\right)\sqrt{n}\|x^{k+1}-x^{k}\|_{2}\\ &+(\|A^{\top}A\|_{2}+\beta)\sqrt{n}\|x^{k}-x^{k-1}\|_{2}.\end{split} Using the inequality in Lemma 2.1 , we get \begin{split}\|\nu^{k+1}\|_{2}\leq&\left(\|A^{\top}A\|_{2}+\beta+\alpha(\widetilde{C}_{p-1})^{p-1}L_{\underline{c}}+\frac{\beta\varepsilon}{2}\right)\sqrt{n}\|x^{k+1}-x^{k}\|_{2}\\ &+(\|A^{\top}A\|_{2}+\beta)\sqrt{n}\|x^{k}-x^{k-1}\|_{2}.\end{split} (4.45) Again for k\geq K+1 , we define \gamma^{k+1}:=(\gamma^{k+1}_{x},\gamma^{k+1}_{u}) by \left\{\begin{aligned} \gamma^{k+1}_{x}&=\nu^{k+1}+\beta(1-\varepsilon)(x^{k+1}-x^{k});\\ \gamma^{k+1}_{u}&=-\beta(1-\varepsilon)(x^{k+1}-x^{k}).\end{aligned}\right. (4.46) By the definition of \mathcal{H}(x,u) in ( 4.17 ), we have \gamma^{k+1}\in\partial\mathcal{H}(x^{k+1},x^{k}) . Meanwhile, it holds that \|\gamma^{k+1}\|_{2}\leq\|\nu^{k+1}\|_{2}+\sqrt{2}\beta(1-\varepsilon)\|x^{k+1}-x^{k}\|_{2}. Therefore, using ( 4.45 ), one has \displaystyle\|\gamma^{k+1}\|_{2}\leq \displaystyle\left(\left(\|A^{\top}A\|_{2}+\beta+\alpha(\widetilde{C}_{p-1})^{p-1}L_{\underline{c}}+\frac{\beta\epsilon}{2}\right)\sqrt{n}+\sqrt{2}\beta(1-\varepsilon)\right)\|x^{k+1}-x^{k}\|_{2} (4.47) \displaystyle+(\|A^{\top}A\|_{2}+\beta)\sqrt{n}\|x^{k}-x^{k-1}\|_{2}. (2) The case of p=1 . Let k\geq K+1 and define \nu^{k+1} as \nu_{j}^{k+1}=\left\{\begin{aligned} &(A^{\top}(Ax^{k+1}-b))_{j}+\alpha\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1})\sgn(x_{j}^{k+1}),\quad\forall j\in s(x^{k+1}_{g_{i}}),\;g_{i}\in\mathcal{S}^{k};\\ &(A^{\top}(Ax^{k+1}-b))_{j}+\alpha\xi_{j},\;\;\,\;\qquad\quad\quad\qquad\qquad\quad\forall j\notin s(x^{k+1}_{g_{i}}),\;g_{i}\in\mathcal{S}^{k};\\ &0,\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\;\;\;\;\forall j\in g_{i},\;g_{i}\in\mathcal{G}\setminus\mathcal{S}^{k}.\end{aligned}\right. (4.48) where \xi_{j}\in[-\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1}),\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1})] will be selected later. By the subdifferential in ( 2.4 ), one has \nu^{k+1}\in\partial\mathcal{E}(x^{k+1}) . Recall ( 4.32 ) and ( 4.33 ) that for any j\in s(x^{k+1}_{g_{i}}) with g_{i}\in\mathcal{S}^{k},k\geq K , \begin{split}\lambda^{k+1}_{j}=(A^{\top}(Az^{k}-b))_{j}+\beta(x^{k+1}-z^{k})_{j}+\alpha\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1})\sgn(x_{j}^{k+1}),\end{split} (4.49) and that for any j\not\in s(x^{k+1}_{g_{i}}) with g_{i}\in\mathcal{S}^{k},k\geq K , \begin{split}\lambda^{k+1}_{j}\in(A^{\top}(Az^{k}-b))_{j}+\beta(x^{k+1}-z^{k})_{j}+\alpha[-\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1}),\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1})].\end{split} (4.50) On one hand, combining ( 4.48 ) and ( 4.49 ), we get for any j\in s(x^{k+1}_{g_{i}}) with g_{i}\in\mathcal{S}^{k},k\geq K+1 , \begin{split}\nu_{j}^{k+1}=&(A^{\top}A(x^{k+1}-z^{k}))_{j}-\beta(x^{k+1}-z^{k})_{j}+\lambda^{k+1}_{j}\\ &+\alpha\sgn(x_{j}^{k+1})\left(\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1})-\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1})\right).\end{split} Using ( 4.36 ), it then follows that for any j\in s(x^{k+1}_{g_{i}}) with g_{i}\in\mathcal{S}^{k},k\geq K+1 , \begin{split}|\nu_{j}^{k+1}|&\leq|(A^{\top}A(x^{k+1}-z^{k}))_{j}|+\beta|(x^{k+1}-z^{k})_{j}|+|\lambda^{k+1}_{j}|+\alpha L_{\underline{c}}\|x_{g_{i}}^{k+1}-x_{g_{i}}^{k}\|_{1}.\end{split} (4.51) On the other hand, by ( 4.50 ), there exists an \eta_{j}\in[-\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1}),\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1})] such that \begin{split}\lambda^{k+1}_{j}=(A^{\top}(Az^{k}-b))_{j}+\beta(x^{k+1}-z^{k})_{j}+\alpha\eta_{j},\;j\not\in s(x^{k+1}_{g_{i}}).\end{split} Then, for any j\notin s(x^{k+1}_{g_{i}}) with g_{i}\in\mathcal{S}^{k},k\geq K+1 , \nu_{j}^{k+1} in ( 4.48 ) could be written as \begin{split}\nu_{j}^{k+1}=(A^{\top}A(x^{k+1}-z^{k}))_{j}-\beta(x^{k+1}-z^{k})_{j}+\lambda^{k+1}_{j}+\alpha(\xi_{j}-\eta_{j}).\end{split} (4.52) In order to estimate the value of |\nu_{j}^{k+1}| for any j\notin s(x^{k+1}_{g_{i}}) with g_{i}\in\mathcal{S}^{k},k\geq K , we use the method in [ 55 ] to choose \xi_{j} in ( 4.48 ). If \psi^{\prime}(\|x_{g_{i}}^{k}\|_{1})\leq\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1}) , we set \xi_{j}=\eta_{j} . If \psi^{\prime}(\|x_{g_{i}}^{k}\|_{1})>\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1}) , we set \xi_{j}=\left\{\begin{aligned} \eta_{j},&\quad\eta_{j}\in\left[-\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1}),\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1})\right];\\ \psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1}),&\quad\eta_{j}\in\left(\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1}),\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1})\right];\\ -\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1}),&\quad\eta_{j}\in\left[-\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1}),-\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1})\right).\end{aligned}\right. By the choice of \xi_{j} and ( 4.52 ), the following holds for j\notin s(x^{k+1}_{g_{i}}) with g_{i}\in\mathcal{S}^{k},k\geq K+1 , \begin{split}|\nu_{j}^{k+1}|&\leq|(A^{\top}A(x^{k+1}-z^{k}))_{j}|+\beta|(x^{k+1}-z^{k})_{j}|+|\lambda^{k+1}_{j}|+\alpha\left|\psi^{\prime}(\|x_{g_{i}}^{k+1}\|_{1})-\psi^{\prime}(\|x_{g_{i}}^{k}\|_{1})\right|\\ &\leq|(A^{\top}A(x^{k+1}-z^{k}))_{j}|+\beta|(x^{k+1}-z^{k})_{j}|+|\lambda^{k+1}_{j}|+\alpha L_{\underline{c}}\|x_{g_{i}}^{k+1}-x_{g_{i}}^{k}\|_{1}.\end{split} (4.53) Adding up all j\in g_{i} , for g_{i}\in\mathcal{S}^{k},k\geq K+1 in ( 4.51 ) and ( 4.53 ), we obtain \begin{split}\|\nu_{g_{i}}^{k+1}\|_{1}\leq\|(A^{\top}A(x^{k+1}-z^{k}))_{g_{i}}\|_{1}+\beta\|(x^{k+1}-z^{k})_{g_{i}}\|_{1}+\|\lambda^{k+1}_{g_{i}}\|_{1}+n\alpha L_{\underline{c}}\|x_{g_{i}}^{k+1}-x_{g_{i}}^{k}\|_{1}.\end{split} Recalling the construction of \nu^{k+1} in ( 4.48 ), one has \nu^{k+1}_{j}=0 , for any j\in g_{i} with g_{i}\in\mathcal{G}\setminus\mathcal{S}^{k},k\geq K+1 . Therefore, by Lemma 2.2 and ( 4.15 ), we can derive that \begin{split}\|\nu^{k+1}\|_{1}&\leq(\|A^{\top}A\|_{2}+\beta)\sqrt{n}\|x^{k+1}-z^{k}\|_{2}+(\frac{\beta\varepsilon}{2}+n\alpha L_{\underline{c}})\sqrt{n}\|x^{k+1}-x^{k}\|_{2}.\end{split} Applying \|\nu^{k+1}\|_{2}\leq\|\nu^{k+1}\|_{1} , we get \begin{split}\|\nu^{k+1}\|_{2}&\leq(\|A^{\top}A\|_{2}+\beta+\frac{\beta\varepsilon}{2}+n\alpha L_{\underline{c}})\sqrt{n}\|x^{k+1}-x^{k}\|_{2}+(\|A^{\top}A\|_{2}+\beta)\sqrt{n}\|x^{k}-x^{k-1}\|_{2}.\end{split} (4.54) Define \gamma^{k+1}\in\partial\mathcal{H}(x^{k+1},x^{k}) as in ( 4.46 ). By some simple calculations as in ( 4.47 ), we get \begin{split}\|\gamma^{k+1}\|_{2}\leq&\left((\|A^{\top}A\|_{2}+\beta+\frac{\beta\varepsilon}{2}+n\alpha L_{\underline{c}})\sqrt{n}+\sqrt{2}\beta(1-\varepsilon)\right)\|x^{k+1}-x^{k}\|_{2}\\ &+(\|A^{\top}A\|_{2}+\beta)\sqrt{n}\|x^{k}-x^{k-1}\|_{2}.\end{split} (4.55) Summarizing ( 4.45 ), ( 4.47 ) ( 4.54 ) and ( 4.55 ) completes the proof. Lemma 4.8 . For any \beta>\|A^{\top}A\|_{2} and the extrapolation parameters \left\{t_{k}\right\}\subset[0,{\bar{t}}) satisfying \sup_{k}t_{k}<{\bar{t}} , let \left\{x^{k}\right\} be a sequence generated by FITS 3 . Then, any cluster point of \left\{x^{k}\right\} is a stationary point of \mathcal{E} . Proof 4.9 . By Lemma 4.2 (ii), the sequence \left\{x^{k}\right\} is bounded and thus has a cluster point. Take an arbitrary cluster point of \left\{x^{k}\right\} denoted as \hat{x}=\lim_{l\rightarrow\infty}x^{k_{l}} . Then, we have \lim_{l\rightarrow\infty}\mathcal{E}(x^{k_{l}})=\mathcal{E}(\hat{x}) due to the continuity of \mathcal{E} . By Lemma 4.6 , one chooses a \nu^{k_{l}}\in\partial\mathcal{E}(x^{k_{l}}) . It holds that \nu^{k_{l}}\rightarrow 0 as l\rightarrow\infty by the inequality ( 4.37 ) and the fact that \lim_{k\to\infty}\|x^{k}-x^{k-1}\|_{2}=0 . The closedness of the graph of the limiting subdifferential operator guarantees that 0\in\partial\mathcal{E}(\hat{x}) . Finally, we give our main convergence result of the FITS 3 algorithm. Theorem 4.10 . Assume that \mathcal{H}(x,u) is a KŁ function, \beta>\|A^{\top}A\|_{2} and the extrapolation parameters \left\{t_{k}\right\}\subset[0,{\bar{t}}) satisfy \sup_{k}t_{k}<{\bar{t}} . Let \left\{x^{k}\right\} be a sequence generated by FITS 3 . Then, the sequence \left\{x^{k}\right\} converges globally to a stationary point of \mathcal{E} . Moreover, \sum_{k=0}^{\infty}\|x^{k}-x^{k-1}\|_{2}<\infty holds. Proof 4.11 . We use the abstract convergence theorem in [ 38 ] to show the results. Lemma 4.2 (i) (ii), Lemma 4.6 and the continuity of the function \mathcal{E} give (H1), (H2) and (H3) required by the abstract convergence theorem [ 38 , Theorem 3.7] . Therefore, the sequence \left\{x^{k}\right\} converges to an \overline{x} which is a stationary point of \mathcal{E} by Lemma 4.8 . Moreover, \sum_{k=0}^{\infty}\|x^{k}-x^{k-1}\|_{2}<\infty holds. Remark 4.12 . At least a broad class of objective functions \mathcal{E} satisfy KŁ property assumption on \mathcal{H} in Theorem 4.10 . If \mathcal{E} is a semialgebraic function, then \mathcal{H} is also semialgebraic and thus has KŁ property. Remark 4.13 . If we further assume that the function \varphi\in\Xi_{\sigma} of \mathcal{H}(x,u) in KŁ property has the form \varphi(s)=cs^{1-\theta},\theta\in[0,1) , we can get the convergence rate of our FITS 3 algorithm by a similar analysis with [ 2 , 49 ] . To save the space, we omit the details. 5 Numerical experiments In this section, we show the performance of the FITS 3 algorithm on the group sparse optimization model with a least-squares fidelity. We use the potential functions: \psi(t)=t^{q},0300\end{cases},\quad a_{-1}=a_{0}=1. The initial point x^{0} is chosen as the approximate solution of the \ell_{1} regularization, which is solved by ADMM ( [ 53 ] ) in very few iterations with random initialization. The algorithm is stopped, when the following condition is satisfied \frac{\|x^{k}-x^{k-1}\|_{2}}{\|x^{k-1}\|_{2}}\leq\text{Tol}, with \text{Tol}=5*10^{-5} . We take MAXit=300. To evaluate the recovery quality, define the following relative error \epsilon_{\text{rel}}=\frac{\|x^{\star}-\underline{x}\|_{2}}{\|\underline{x}\|_{2}}. The recovered signal x^{\star} is regarded as successful if the relative error less than 0.01 . The success rate is the ratio of success over 50 trials in this paper. We mainly test Algorithm 1 with p=2 for model ( 1.1 ), and record the experiment results in various aspects in Subsection 5.1 . The test on Algorithm 1 with p=1 is simply reported in Subsection 5.2 . 5.1 Test on Algorithm 1 with p=2 5.1.1 The convergence and extrapolation effect of FITS 3 We first test the convergence and extrapolation effect of FITS 3 with p=2 . For this, we set q=0.5 , the number of nonzero groups \underline{\mathcal{S}}=12 , i.e., the sparsity level is 18.75\% . The recovery result is shown in Fig. 1 (a) and the recovery error \left(\frac{\|x^{k}-\underline{x}\|_{2}}{\|\underline{x}\|_{2}}\right) is shown in Fig. 1 (b). It can be seen that FITS 3 performs well on the sparse signal recovery problem. (a) (b) (c) (d) (e) (f) Figure 1: Test on FITS 3 with p=2 . (a) The recovery by FITS 3 . (b)(c)(d)(e) The convergence justification of FITS 3 . (f) The speed up effect of extrapolation. Next, we show the convergence behavior of the FITS 3 algorithm. Experimental results are reported in Fig. 1 (b)-(e). The iteration points become closer and closer to the ground truth as shown in Fig 1 (b). The group support set shown in Fig. 1 (c) decreases monotonically and converges, which is consistent with the conclusion in ( 4.16 ). The sequences of \mathcal{E}(x^{k}) and the relative error \left(\frac{\|x^{k-1}-x^{k}\|_{2}}{\|x^{k-1}\|_{2}}\right) shown in Fig. 1 (d)(e) converge, although oscilate slightly, which are consistent with our theoretical results. We show the speed up effect of extrapolation. When the extrapolation parameter t=0 , the FITS 3 algorithm degenerates to the algorithm without extrapolation (ITS 3 ). We run ITS 3 and FITS 3 under the same settings. The sequence of objective function value \mathcal{E}(x^{k}) of FITS 3 and ITS 3 are shown in Fig. 1 (f). It can be seen that the value of \mathcal{E}(x^{k}) of FITS 3 decreases and converges faster and FITS 3 requires fewer iteration steps to reach the stopping condition. 5.1.2 Choice of q In this subsection, we discuss the choice of q . We test the FITS 3 algorithm with different q\in\left\{0.1,0.3,0.5,0.7,0.9\right\} . The success rates of FITS 3 with different q are reported in Fig. 2 (a). It shows that under the general setting, the success rates of FITS 3 with q=0.3 and q=0.5 are higher than others. In the following experiments, we take q=0.5 . (a) (b) (c) (d) Figure 2: Success rate tests and comparisons on FITS 3 with p=2 . (a)(b)(c) The success rates of FITS 3 for group sparse minimization models with different q , different group sizes and different types of measurement matrix A , respectively. (d) Comparison on success rates between non-Lipschitz group sparse recovery algorithms and ADMM-GL algorithm. 5.1.3 Adaptability to different group sizes and different types of A In this subsection, we test the sensitivity of FITS 3 with q=0.5 on group sizes and types of A in terms of success rate. We first show the adaptability of FITS 3 on group sizes. We test FITS 3 for four problems with different group sizes l\in\left\{4,8,16,32\right\} . The success rates are shown in Fig. 2 (b). It can be seen that the larger the group size, the higher the success rate. We next test the sensitivity of FITS 3 on different measurement matrices A . We use matrix A generated from A=(orth(B^{\prime}))^{\prime} in Matlab, where B is a random Gaussian matrix, random Bernoulli matrix, random PartHadamard matrix or random PartFourier matrix. Success rates of recoveries by FITS 3 are presented in Fig. 2 (c). It can be seen that FITS 3 performs consistently well in problems with different measurement matrices. 5.1.4 Comparisons In this subsection, we compare the performance of FITS 3 with some existing algorithms solving non-Lipschitz \ell_{p,q} regularization models, including PGM-GSO ( [ 25 ] ), InISSAPL-GSO ( [ 55 ] ) and IRLS-th ( [ 23 ] ). We also compare it to the ADMM-GL ( [ 9 ] ) solving the convex group lasso model ( \ell_{2} - \ell_{2,1} model) ( [ 58 ] ), which is a baseline algorithm for group sparse recovery. The PGM-GSO, InISSAPL-GSO, IRLS-th and our FITS 3 are used to solve the non-Lipschitz \ell_{2} - \ell_{2,q} minimization model. The parameters and stopping conditions of the compared algorithms follow their default settings. We set q=0.5 in the PGM-GSO, InISSAPL-GSO and IRLS-th since these algorithms give their best results at q=0.5 . We compare these algorithms in terms of the success rate, recovery accuracy and CPU cost. Fig. 2 (d) shows the comparison on the success rates of these algorithms under the general setting for recovery problems with different sparsity levels. It can be observed that the recovery success rates of FITS 3 , PGM-GSO, InISSAPL-GSO, IRLS-th are very close and all higher than ADMM-GL. In Table 1 , we compare the CPU costs of these algorithms for recovery problems with different scales and sparsity levels. In particular, we set n\in\left\{1024,4096,8192,12288,16384\right\} , m=n/2 , the group size l=16 and the sparsity levels 5\% , 10\% , 15\% and 20\% . It can be seen that non-Lipschitz methods PGM-GSO, InISSAPL-GSO, IRLS-th and FITS 3 reach similar recovery accuracies (better than the convex ADMM-GL method), while the proposed FITS 3 usually takes the least CPU cost. This efficiency advantage becomes more and more greater as the problem scale n increases. 5.2 Test on Algorithm 1 with p=1 Here we test the performance of the FITS 3 algorithm for signal recovery problems with intra-group sparsity structures. We set n=1024 , m=512 , the group size l=32 , and the number of nonzero group \underline{\mathcal{S}}=16 . To simulate the intra-group sparsity structures, we denote the number of nonzero elements of each nonzero group as \underline{s} , and consider \underline{s}=6 and 9. Fig. 3 shows the recovery results of FITS 3 with p=1 , q=0.5 and p=2 , q=0.5 . We observe that for such signal recovery problems with intra-group sparsity structures, Algorithm 1 with p=1 works quite well and much better than Algorithm 1 with p=2 . (a) p=1,\underline{s}=6:\epsilon_{\text{rel}}=0.0025 (b) p=2,\underline{s}=6:\epsilon_{\text{rel}}=0.1212 (c) p=1,\underline{s}=9:\epsilon_{\text{rel}}=0.0030 (d) p=2,\underline{s}=9:\epsilon_{\text{rel}}=0.1525 Figure 3: Signal recovery by FITS 3 with p=1 and p=2 for the signal recovery problems with intra-group sparsity structures. (a)(b) The intra-group sparsity level \underline{s}/l=6/32 . (c)(d) The intra-group sparsity level \underline{s}/l=9/32 . 6 Conclusions In this paper, we proposed a new simple algorithm named as FITS 3 for a general non-convex non-Lipschitz group sparse regularization model with a least-squares fidelity, by integrating thresholding operation, group support-and-scale shrinkage, linearization and extrapolation techniques. This iterative algorithm does not need to solve any linear or nonlinear system, and in two most important cases p=1 and p=2 it contains only simple operations like matrix-vector multiplication and soft thresholding. It thus is especially suitable for solving median- or large-scale problems. We also established the sequence convergence property of the proposed FITS 3 under an inexact condition at each iteration, which is applicable to our FITS 3 with a general p\in[1,+\infty). Numerical experiments illustrated the advantages of the FITS 3 , showing great potentials in various group sparse recovery applications in the current era of big data.