In my continuing analysis of the recovery performance of CMP, I have compared the computational cost of the algorithm to both OMP and MP with debiasing (MP+).
The nice figure below shows as a function of the phase plane, the average cost of attempting to recover a signal using one of three algorithms. Sandwiched between MP+ and OMP (using a very lightweight QR implementation) is CMP, which has a cost that rises quickly once the sparsity exceeds a particular level.
Most intriguing though is that CMP (with no more than two refinement cycles each model augmentation) and OMP show the same empirical phase transition (50% recovery, black line) — at least at this problem dimension of 400 — but the boundary separating where CMP becomes more expensive than OMP is higher (red dashed).
So there it is, proof that CMP is less computationally complex than OMP for the same recovery performance w.r.t. the majority exact recovery (full support recovery, nothing more and nothing less). Now, what about 90% recovery?