Recovery of Compressively Sensed Sparse Signals using Cyclic OLS

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).


5 thoughts on “Recovery of Compressively Sensed Sparse Signals using Cyclic OLS

  1. 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).


  2. 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 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).


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s