My simulations for normally distributed sparse signals have finally finished (after three weeks, jeesh!). This builds on the work here. The question is, what is the performance of cyclic OLS (COLS) in recovering compressively sensed sparse vectors?

Below we see the probability of exact recovery as a function of problem sparsity for cyclic MP (CMP, solid) and for COLS (dashed) at five problem indeterminacies \(m/N\), where the sensing matrix is \(m \times N\). Here \(N=400\). The \(s\)-sparse vector is distributed Normal. Clearly COLS is able to recover the original vectors better than CMP. (In my paper, we see CMP and OMP perform nearly the same.)

The figure below shows for these same sparse vectors, the phase transitions for six recovery methods, and the union of them all (Ensemble). Here we see COLS is on top for most of the indeterminacies, except for a brief tangle with PrOMP. Choosing the best from all six vectors recovered by these algorithms produces the phase transition on top.

So, COLS may do the best of them all for this type of sparse signal. (I should try SL0.) However, it brings with it such an enormous computational cost that I don’t think it is worth it. I make some mention of reducing its cost with the matrix inversion lemma, but I don’t think that will make any sort of dent. I will explore this in greater detail during my scientific mission in Rennes (details to come).

### Like this:

Like Loading...

*Related*

Thanks for the phase diagram. Can you tell me why the ensemble results is always better than the best solution from any of the techniques from which it is supposed to get its answer from ?

You are talking about the times it took to get these results. One wonders if this is ripe for asking a grant from the google exacycle program ( http://nuit-blanche.blogspot.com/2011/05/google-exacycletwo-more-days.html )

Cheers,

Igor.

LikeLike

Hi Igor,

With an ensemble of 9 recovery algorithms, we get 9 possible solutions {x_i}. We choose the one that produces the smallest l_2 error given the measurements (|| y – A x_i ||_2) to be the sensed vector. I do not expect that OMP, BP, IHT, CMP, etc. fail for the same vectors. So using an ensemble, I am guaranteed to have at least the recovery performance of the best performing algorithm. When the recovery algorithms fail for different vectors, then I will have better performance.

It is premature to ask for more computational resources to run COLS. I need to develop its theoretical results, and hone my application, to see if it is worthwhile. This work is a part of my scientific mission to INRIA (details to come).

Cheers.

-Bob.

LikeLike

oh I see, this is an implementation of the DUMBEST algorithm ( http://nuit-blanche.blogspot.com/2008/11/cs-dumbest-algorithm-mindmaps-counter.html ) :-) You’re right the “ensemble” sound much better.

Igor.

LikeLike

Bob,

I added some more thoughts:

http://nuit-blanche.blogspot.com/2011/05/ensemble-we-can-be-dumbest.html

Cheers,

Igor.

LikeLike

Bob,

By the way, I’d be very curious on how the Ensemble results fares compared to the DT transition computed by Tanner et al . I did a check on one value at http://ecos.maths.ed.ac.uk/polytopes.shtml and your graph seems to be above theirs. Either this is because of a difference in definition of what constitutes the phase transition, or your ensemble approach essentially beats their lone solver (which would make sense).

Cheers,

Igor.

LikeLike