Exploring the Failings of OMP and \(\ell_1\) Minimization

Continuing from my experiments over the past few weeks, today I simulate sparse signal recovery from compressive measurements using both OMP and \(\ell_1\) minimization (the principal known as BP). I run 1000 independent trials (using the same sensing matrix, with elements iid normal random, and columns made unit norm) using a signal of length 250 samples with sparsity 11 compressed into 50 measurements. The magnitudes of the non-zero elements of the sparse vector are iid uniform on [1,2].
I now look at some of the cases where OMP and BP succeeds and fails.


First, OMP and BP failed together 154 times in the 1000 simulations.
Below we see some of these cases in the time-domain. The red circles show the original sparse signal in time and amplitude; the gray dots show the reconstruction by OMP; and the black dots show the reconstruction by BP.
We see a variety of spacings and amplitudes. Many of the signals lack a wide dynamic range, with values near plus minus 1.5. But there is nothing here strongly suggesting that both OMP and BP will fail to recover the sensed signal.

OMPFailBPFailexample_2.jpg

Second, OMP succeeded and BP failed together 33 times in the 1000 simulations.
Below we see some of these cases in the time-domain (which reminds me of dragon fruit).
We again see a variety of spacings and amplitudes, some very extreme, such as the top left example with four non-zero samples spaced close together.
But I see nothing awry in these examples to say BP will fail and OMP will succeed.

OMPSuccessBPFailexample_1.jpg
Third, OMP failed and BP succeeded together 413 times in the 1000 simulations.
Below we see some of these cases in the time-domain.
Again, I don’t see evidence that OMP should fail here.

OMPFailBPSuccessexample_1.jpg

Finally, OMP succeeds and BP succeeds together 400 times in the 1000 simulations.
Below we see some of these cases in the time-domain.
Again, some samples are closely spaced in time and amplitude.

OMPSuccessBPSuccessexample_8.jpg
Now that I think about it, close spacing of active samples should not have that large of an influence.
Even if two samples are adjacent, they weight different atoms \(\mathbf{\Phi}\vx\). When \(\mathbf{\Phi}\) is random, then adjacent columns will probably be approximately orthogonal. In the experiments above, 86% of the adjacent column pairs have a magnitude inner product of less than 0.2, and 54% have less than 0.1. Perhaps what I have to be worry about then are those active elements that scale the columns of \(\mathbf{\Phi}\) that are more coherent than that.
Looking at the coherence between the atoms that are active in these cases, I am finding no relationship between the coherence of atoms in the successful and failed cases. I have looked at the mean magnitude coherences, their variance, the sorted coherence values, and so on. I see no pattern. But perhaps it is both a large coherence, and a lack of dynamic range. Now to look at the influence of dynamic range… of which I am still not sure how to measure…

Advertisements

2 thoughts on “Exploring the Failings of OMP and \(\ell_1\) Minimization

  1. Nice research topics! OMP and L1 are classical algorithms based on compressive sensing. Recently, I have considered how to design a measurement matrix to mitigate the conherence, the recovery performance has been improved, however, the computational complexity are very high due to convex optimization problem. Thanks for your poster about these. Good job!

    Like

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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