Input: Sampling matrix Φ , noisy sample vector u ,

sparsity level s

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

1) Initialization:

a 0 0 {Trivial initial approximation}

v u {Current samples = input samples}

k 0

2) repeat

a) k k + 1

b) y Φ T v {Form signal proxy}

c) Ω S u p p ( y 2 s ) {Identify large components}

d) T Ω S u p p ( a k 1 ) {Merge supports}

e) b | T Φ + T {Signal estimation by least-squares}

f) b | T C 0

g) r v

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

a k b f l o o r ( 0.8 s )

h) a k b s {Prune to obtain next approximation}

i) v u Φ a k {Update current samples}

until halting criterion true