More thoughts on OMP performance limits from SIC

I am not too satisfied with my interpretation yesterday of Jin and Rao’s condition (JRC). When I look at it again and refer to their text, i.e.,
$$\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\}$$
this is a condition for asymptotic success (as the number of measurements \(M\) goes to infinity) and not failure. Other aspects of the sparse signals can influence the recovery performance, such as which elements of the measurement matrix are active, and how much they are active in relation to each other.

I have checked my simulations, and re-ran them for 2000 different realizations of five distributions with no additive noise. (All signals are sensed by the same sensing matrix.) I am also looking at the recovery performance of BP. Below we see the probability of exact recovery (\(|| \vx – \hat \vx|| < || \vx || 1e-2) for OMP and BP and five different distributions: Normal, Laplacian, uniform, bimodal Gaussian, and bimodal uniform.


Below we see what percentage of sparse vector realizations from each distribution satisfy the JRC. I notice that the relative heights of the light bars follow the circles above. That is a good positive correlation from which we might say of a particular distribution that the fewer members it has satisfying the JRC, the worse OMP will do at recovering sensed members from that distribution.

Below we see among these sparse vector distributions, the percentages of exact recovery and else for OMP that satisfy the JRC or not. The top plots show of those signals recovered exactly by OMP, what percentage satisfies the JRC, or not. The bottom plot shows the same but for those signals not recovered exactly by OMP. Here we see that of those not recovered, a higher percentage of them do not satisfy the JRC.


The plot below shows the same, but for BP. It is intriguing to see here the very small differences between signals recovered or not. Thus, however many signals from a distribution satisfy the JRC apparently has no bearing on the general recoverability using \(\ell_1\) minimization.



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