Input: Sampling matrix $\Phi$ , noisy sample vector $u$ ,

sparsity level s

Output: An s-sparse approximation $a$ of the target signal

1) Initialization:

$a^0\leftarrow 0$ {Trivial initial approximation}

$v\leftarrow u$ {Current samples = input samples}

$k\leftarrow 0$

2) repeat

a) $k\leftarrow k+1$

b) $y\leftarrow {\Phi }^{\text{T}}v$ {Form signal proxy}

c) $\Omega \leftarrow Supp\left(y_{2s}\right)$ {Identify large components}

d) $T\leftarrow \Omega \cup Supp\left(a^{k-1}\right)$ {Merge supports}

e) ${b|}_T\leftarrow {\Phi }^{+}T$ {Signal estimation by least-squares}

f) ${b|}_{T^C}\leftarrow 0$

g) $r\leftarrow v$

If 0.8 (norm(r)) < norm(v):

$a^k\leftarrow b_{floor\left(0.8s\right)}$

h) $a^k\leftarrow b_s$ {Prune to obtain next approximation}

i) $v\leftarrow u-\Phi a^k$ {Update current samples}

until halting criterion true