Stochastic CoSaMP: Randomizing Greedy Pursuit for Sparse Signal Recovery
Abstract
In this paper, we formulate the K -sparse compressed signal recovery problem with the $L_0$ 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.
Cite
Text
Pal and Mengshoel. "Stochastic CoSaMP: Randomizing Greedy Pursuit for Sparse Signal Recovery." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2016. doi:10.1007/978-3-319-46128-1_48Markdown
[Pal and Mengshoel. "Stochastic CoSaMP: Randomizing Greedy Pursuit for Sparse Signal Recovery." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2016.](https://mlanthology.org/ecmlpkdd/2016/pal2016ecmlpkdd-stochastic/) doi:10.1007/978-3-319-46128-1_48BibTeX
@inproceedings{pal2016ecmlpkdd-stochastic,
title = {{Stochastic CoSaMP: Randomizing Greedy Pursuit for Sparse Signal Recovery}},
author = {Pal, Dipan K. and Mengshoel, Ole J.},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2016},
pages = {761-776},
doi = {10.1007/978-3-319-46128-1_48},
url = {https://mlanthology.org/ecmlpkdd/2016/pal2016ecmlpkdd-stochastic/}
}