Article
Stochastic CoSaMP: Randomizing Greedy Pursuit for Sparse Signal Recovery
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery
(2016)
Abstract
In this paper, we formulate the K-sparse compressed signal recovery problem with the L0 norm within a Stochastic Local Search (SLS) framework. Within this randomized framework, we generalize the popular recovery algorithm CoSaMP, creating Stochastic CoSaMP (StoCoSaMP). Interestingly, our deterministic worst case analysis shows that under 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 randomness helps StoCoSaMP to outperform CoSaMP both in terms of signal recoverability and computational cost, even in high dimensions (upto 1 million dimensions), on a variety of problems. Further, StoCoSaMP outperforms many other popular recovery algorithms (including StoGradMP and StoIHT) on large scale real-world gene-expression datasets.
Keywords
- compressed sensing,
- stochastic local search,
- CoSaMP,
- StoCoSaMP,
- sparse signal recovery,
- machine learning
Disciplines
Publication Date
September 20, 2016
Publisher Statement
@inproceedings{pal16Stochastic,
author = "Pal, D. K. and Mengshoel, O. J.",
title = "Stochastic CoSaMP: Randomizing Greedy Pursuit for Sparse Signal Recovery",
booktitle = "European Conference on Machine Learning and Knowledge Discovery in Databases (ECML-PKDD-16)",
month = "September",
year = "2016",
publisher = "Springer",
address = "Riva del Garda, Italy",
pages = "761--776"
}
Citation Information
Dipan K Pal and Ole J Mengshoel. "Stochastic CoSaMP: Randomizing Greedy Pursuit for Sparse Signal Recovery" European Conference on Machine Learning and Principles and Practice of Knowledge Discovery (2016) p. 761 - 776 Available at: http://works.bepress.com/ole_mengshoel/57/