Subspace Pursuit for Compressive Sensing Signal Reconstruction

Subspace Pursuit for Compressive Sensing Signal Reconstruction (SP) is an iterative backtracking greedy algorithm introduced by Dai and Milenkovic (2009) for reconstructing K-sparse and compressible signals x in R^N from linear measurements y = Phi x + e in R^m. Unlike CoSaMP (which merges 2K proxy coordinates and prunes without re-projecting), SP initializes the K-element support T^0 = {K indices of largest magnitude of Phi^* y} with orthogonal-projection residue y_r^0 = resid(y, Phi_{T^0}) and at each iteration l >= 1 forms the 2K-element candidate union T_tilde^l = T^{l-1} union {K indices of largest magnitude of Phi^* y_r^{l-1}}, computes the intermediate projection coefficients x_p = Phi_{T_tilde^l}^dagger y, prunes T^l to the K indices of largest magnitude in x_p, and performs a second orthogonal projection y_r^l = y - Phi_{T^l} Phi_{T^l}^dagger y onto the pruned K-dimensional column subspace before checking termination ||y_r^l||_2 >= ||y_r^{l-1}||_2.