Thursday, November 10, 2016

Stochastic CoSaMP: Randomizing Greedy Pursuit for Sparse Signal Recovery

Dipan just sent me the following:

Hi Igor,

I had contacted you a while back regarding this. I m pleased to bring to your attention some of our recent work on randomizing a greedy pursuit for sparse signal recovery published at ECML-PKDD 2016. We specifically focus on CoSaMP and introduce a simple modification to the algorithm leading to Stochastic CoSaMP. The modification although looks simple, we believe, has far reaching consequences, leading to gains in both performance and computation time.

Here is the Springer link
And here is the link to the free version hosted on my website:

And here is the abstract:

In this paper, we formulate the K-sparse compressed signal recovery problem with the L0 norm within a Stochastic Local Search (SLS) framework. Using this randomized framework, we generalize the popular sparse recovery algorithm CoSaMP, creating Stochastic CoSaMP (StoCoSaMP). Interestingly, our deterministic worst case analysis shows that under the Restricted Isometric Property (RIP), even a purely random version of StoCoSaMP is guaranteed to recover a notion of strong components of a sparse signal, thereby leading to support convergence. Empirically, we find that StoCoSaMP outperforms CoSaMP, both in terms of signal recoverability and computational cost, on different problems with up to 1 million dimensions. Further, StoCoSaMP outperforms several other popular recovery algorithms, including StoGradMP and StoIHT, on large real-world gene-expression datasets.

We hope that your subscribers might find the work useful, and we look forward to your response.

Dipan K. Pal
Thanks Dipal !

No comments: