# Cyclic Matching Pursuit for Compressed Sensing Recovery

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.

However, what if we could maintain the simplicity of MP, and improve recoverability? That is essentially the tenor of the paper I am submitting to SPARS11. Last night, I left CMP running on my 24′ iMac for normally distributed sparse signals of dimension $$N=400$$, measured by sensing matrices sampled from the uniform spherical ensemble $$\mathcal{R}^{M\times N}$$. Averaging the results of 100 independent trials, I find the following exact recovery probabilities (as defined by Maleki and Donoho $$|| \vx – \hat \vx ||_2/||\vx||_2 0.99$$, where $$\vr’$$ is the new residual with refinement and $$\vr$$ is the old before refinement, or five refinement cycles have been completed.)

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”?