CoSaMP (Compressive Sampling Matching Pursuit)

CoSaMP (Compressive Sampling Matching Pursuit) is an iterative greedy-pursuit signal reconstruction algorithm introduced by Needell and Tropp (2009) that combines combinatorial support-identification ideas with the optimal restricted-isometry stability guarantees of convex optimization. Given noisy linear measurements u = Phi x + e in C^m of an N-dimensional signal x and target sparsity s, each iteration k >= 1 executes five steps: (1) Identification of the 2s largest coordinates Omega = supp((Phi^* v)_{2s}) of the proxy y = Phi^* v from the current residual v; (2) Support Merger T = Omega union supp(a^{k-1}) of size at most 3s; (3) Estimation via restricted least squares b|_T = Phi_T^dagger u and b|_{T^c} = 0; (4) Pruning to retain only the s largest entries a^k = b_s; and (5) Sample update v = u - Phi a^k. Under the Restricted Isometry Property delta_{4s} <= 0.1, CoSaMP satisfies ||x - a^k||_2 <= 2^{-k} ||x||_2 + 20*nu where nu = ||x - x_s||_2 + s^{-1/2} ||x - x_s||_1 + ||e||_2.