Research indexJournal article
Sub-linear time compressed sensing using sparse-graph codes
Xiao, Pawar, Ramchandran
International Symposium on Information Theory1 Jun 2015
NobleIDark:/48914/w1/20260525/1817517EDOI10.1109/isit.2015.7282735
Sub-linear time compressed sensing using sparse-graph codes
Xiao, Pawar, Ramchandran · International Symposium on Information Theory · 2015 · Subscription
NobleIDark:/48914/w1/20260525/1817517EDOI10.1109/isit.2015.7282735
The full text is at the publisher
You can read the abstract here, or open it at the publisher.
Abstract
We consider the problem of recovering the support of an arbitrary K-sparse N-length vector in the presence of noise, where the sparsity K = O(N δ ) is sub-linear in N for some 0 < δ < 1. A new family of sparse measurement matrices is introduced with a low-complexity recovery algorithm, which achieves a sub-linear measurement cost O(K log 1.3̇ N) and sub-linear computational complexity O(K log 1.3̇ N). Our measurement system is designed to capture observations of the signal through the parity constraints of sparse-graph codes, and to recover the signal by using a simple peeling decoder. We formally connect general sparse recovery problems with sparse-graph decoding, and showcase our design in terms of the measurement cost, computational complexity and recovery performance.