In this Po’D I noted that CoSaMP was acting rather odd. When I looked at the code made available by the authors, I saw the reason for it. (Hooray for reproducibility!) Przemyslaw Dymarski has sent me some graphs of the correction to CoSaMP I discuss here and here.
Below are the decomposition results using the old CoSaMP, compared with several algorithms. The dictionary is a set of atoms created from a 2nd order AR process, as described in this Po’D. Here the signal is 10-sparse. RMGS is a computationally efficient OOMP. “min L1” is basis pursuit. And proposed by Dymarski et al., are the cyclic OOMP (“CyRMGS”) and the cyclic optimized complementary MP (“CyOOCMP”). With performance like that, CyOOCMP appears to deserve a pronounceable name, like “CYLON” or “SoSayWeAll”. (Just a few suggestions :)