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
http://link.springer.com/chapter/10.1007/978-3-319-46128-1_48
And here is the link to the free version hosted on my website:
https://dkpal.github.io/StoCoSaMP_cameraready.pdf


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.

Best
Dipan K. Pal

Thanks Dipal !

The work is : Stochastic CoSaMP: Randomizing GreedyPursuit for Sparse Signal Recovery by Dipan K. Pal and Ole J. Mengshoel. Supplementary material is here.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.