Sub-linear time compressed sensing using sparse-graph codes
Li Xiao, Sameer Pawar, Kannan Ramchandran · 2015
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 01.3̇N) and sub-linear computational complexity O(K log1.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.