Successive Interference Cancellation

I am meeting this Thursday with a professor more specialized than I in digital communications, which will catalyze my understanding of the application and limits of successive interference cancellation (SIC) to picking the bits off a received signal ripe with messages for other receivers. To prepare for this meeting, I am reviewing over the next few days SIC in D. Tse and P. Viswanath, “Fundamentals of Wireless Communication,” Cambridge University Press, 2005 — which I see will require some skimming of several of the other chapters to get a feel for what is going on. I am most interested in learning more about the theoretical underpinnings used by Jin and Rao in analyzing the performance limits of OMP.

I have returned to my simulations of recovering sparse signals with different coefficient distributions from compressive sampling in the no noise case. Previously, I looked at the distribution of success and failure with respect to coherence and dynamic range, and did not find anything settling about it. Now, I am looking at the same data, but with the criteria by Jin and Rao:

OMP can recover a compressively sampled sparse signal as long as its ordered coefficients obey
$$\frac{\log N}{M} \le 0.5 \log \left [1 + \frac{s_i^2}{\sigma_n^2 + \sum_{j=i+1}^K s_j^2} \right ] \; \forall i \in \{1, 2, \ldots, K\}.$$

Below I plot the distributions of OMP recovery success and failures with respect to the “JR Criteria” above for 2000 realizations of sparse signals with coefficients distributed standard Normal. Most of the time OMP recovers these signals, but of those OMP fails to recover more than half of them satisfy the JR condition.

Let’s look at another distribution. Below I plot the recovery statistics for sparse signals distributed uniform and zero mean. It appears to me from this that the JR condition is not the determining factor for when recovery is not possible. (Perhaps I should pay more importance to their claim of “asymptotic recovery”, because I don’t know what this means other than running the algorithm until we have surely passed the sparsity of the signal.)

And finally, below I plot the recovery statistics for sparse signals distributed in two unit-variance Gaussian humps centered on plus and minus 3. Now, a much larger percentage of all the signals tested do not satisfy the JR condition, and most of those OMP fails to recover.

What am I expecting? If the JR condition is really indicative of the recoverability of a compressively sampled sparse signal, then I expect the dark bar (OMP fails) in “Fails JR Condition” to be much greater than the light bar (OMP succeeds) across all distributions.
When I look at the percentages among only failures, and only successes, I get something more reasonable. For the sparse vectors distributed standard normal I see the below:

And for the uniform and zero mean sparse signals I see the following:

And finally for the two Gaussian hump distributed signal, I see the following:

In that last plot we see that when OMP fails, the sparse signal does not satisfy the JR condition as often as for when OMP succeeds. Further work is necessary, and perhaps rerunning all of my simulations to make sure my data are correct!