I have discussed Cyclic Matching Pursuit here (original paper) and here (extension to time-frequency dictionaries, and an orthogonal least squares flavor) before. With reference to the recovery of compressively sampled sparse signals, I have presented some results here and here and here. I have shown that MP, the “pure greedy algorithm” itself, performs horribly for recovery. Spending some time orthogonalizing the residual, as in OMP, really helps things along.

We clearly see the phase transition move to the right as the number of measurements increase. What about the average computation time for CMP to produce a solution, as a function of sparsity for these indeterminacies? This is shown in the plot below.

As expected, more time is needed when we take more measurements of signals that are less sparse. I wonder now: this is time spent for all solutions, regardless if they are correct ones. Is there any difference in computation time when the solution is not “exact”?