Algorithm 1. The CS-MWRKO method

1. Input $A\in {ℝ}^{m\times n}\mathrm{,}b\in {ℝ}^m$ , parameter d, $x^0$ .

2. Output Approximate x solving $Ax=b$ .

3. Create a count sketch $S\in {ℝ}^{d\times m}$ , with $d<m$ and $\tilde{A}=SA,\tilde{b}=Sb$ , and $\tilde{M}\left(i\right)={\Vert {\tilde{a}}_i\Vert }_2^2$ , $i\in \left[d\right]$ .

4. Compute $i_1=\arg {\max }_{i\in \left[d\right]}\frac{\left|{\tilde{b}}_i-\langle {\tilde{a}}_i\mathrm{,}{x}^0\rangle \right|}{{\Vert {\tilde{a}}_i\Vert }_2}$ and $x^1=x^0+\frac{{\tilde{b}}_{i_1}-\langle {\tilde{a}}_{i_1}\mathrm{,}{x}^0\rangle }{\tilde{M}\left(i_1\right)}{\tilde{a}}_{i_1}$ .

5. For $k=\mathrm{1,2,3},\cdots$ do until satisfy the stopping criteria.

6. Compute $i_{k+1}=\arg {\max }_{i\in \left[d\right]}\frac{\left|{\tilde{b}}_i-\langle {\tilde{a}}_i\mathrm{,}{x}^k\rangle \right|}{{\Vert {\tilde{a}}_i\Vert }_2}$ .

7. Compute ${\tilde{D}}_{i_k}=\langle {\tilde{a}}_{i_k}\mathrm{,}{\tilde{a}}_{i_{k+1}}\rangle$ , and ${\tilde{r}}_{i_{k+1}}^k={\tilde{b}}_{i_{k+1}}-\langle {\tilde{a}}_{i_{k+1}},x^k\rangle$ .

8. Compute ${\tilde{w}}^{i_k}={\tilde{a}}_{i_{k+1}}-\frac{{\tilde{D}}_{i_k}}{\tilde{M}\left(i_k\right)}{\tilde{a}}_{i_k}$ , $h_{i_k}={\Vert {\tilde{a}}_{i_{k+1}}\Vert }_2^2{\sin }^2\langle {\tilde{a}}_{i_k}\mathrm{,}{\tilde{a}}_{i_{k+1}}\rangle$ and ${\tilde{\alpha }}_{i_k}^k=\frac{{\tilde{r}}_{i_{k+1}}^k}{h_{i_k}}$ .

9. Set $x^{k+1}=x^k+{\tilde{\alpha }}_{i_k}^k{\tilde{w}}^{i_k}$ .

10. End.