NobleBlocks

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

Paywalled

The full text is at the publisher

You can read the abstract here, or open it at the publisher.

Read 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.

Discussion

Citations

Topics

More

Suggest a correction or report