Input: $X\in {ℝ}^{m\times n}\mathrm{,}y\in {ℝ}^m\mathrm{,}{\beta }_0\in {ℝ}^n$ and $l$ .

Output: Approximate ${\beta }_l$ solving (1).

1. Randomly select $j_1\in \left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ with probability $\frac{{\Vert X_{j_1}\Vert }_2^2}{{\Vert X\Vert }_F^2}$ and compute ${\beta }_1={\beta }_0+\frac{s_0^{\left(j_1\right)}}{{\Vert X_{j_1}\Vert }_2^2}{e}_{j_1}$ .

2. For $k=1$ to $l-1$ do

3. Compute ${\delta }_k=\frac{1}{2}\left(\frac{1}{{\Vert s_k\Vert }_2^2}\underset{1\le j\le n}{\max }\left\{\frac{{\left|s_k^{\left(j\right)}\right|}^2}{{\Vert X_j\Vert }_2^2}\right\}+\frac{1}{{\Vert X\Vert }_F^2}\right)$ .

4. Construct set $V_k=\left\{j\mathrm{<mo>\; :\; </mo>}{\left|s_k^{\left(j\right)}\right|}^2\ge {\delta }_k{\Vert s_k\Vert }_2^2{\Vert X_j\Vert }_2^2\right\}$ .

5. Compute ${\tilde{s}}_k^{\left(j\right)}=\{\begin{array}{ll}{s}_k^{\left(j\right)},\hfill & \text{if}j\in V_k\mathrm{,}\hfill \\ \mathrm{0,}\hfill & \text{otherwise}\mathrm{.}\hfill \end{array}$

6. Select $j_{k+1}\in V_k$ with probability $\frac{{\left|{\tilde{s}}_k^{\left(j_{k+1}\right)}\right|}^2}{{\Vert {\tilde{s}}_k\Vert }_2^2}$ .

7. Compute $w_{j_k}=e_{j_{k+1}}-\frac{X_{j_k}^{\text{T}}{X}_{j_{k+1}}}{{\Vert X_{j_k}\Vert }_2^2}{e}_{j_k}$ and $h_{j_k}=X_{j_{k+1}}^{\text{T}}X{w}_{j_k}$ .

8. Set ${\beta }_{k+1}={\beta }_k+{\eta }_k^{\left(j_k\right)}{w}_{j_k}$ , where ${\eta }_k^{\left(j_k\right)}=\frac{{\tilde{s}}_k^{\left(j_{k+1}\right)}}{h_{j_k}}$ .

9. End for