Compressed sensing using sparse-graph codes for the continuous-alphabet setting
作者： Dong Yin , Ramtin Pedarsani , Xiao Li , Kannan Ramchandran
DOI: 10.1109/ALLERTON.2016.7852309
关键词: Time complexity 、 Decoding methods 、 Arbitrarily large 、 Fraction (mathematics) 、 Compressed sensing 、 Log-log plot 、 Constant (mathematics) 、 Dense graph 、 Combinatorics 、 Mathematics
摘要: In this paper, we consider the compressive sensing (CS) problem in presence of noise. The is to recover a K-sparse signal s ∈ ℝn from noisy linear measurements y = As + w. We propose fast recovery algorithm that can reconstruct any with time complexity grows linearly K and sublinearly n. Specifically, high probability, our able an arbitrarily large fraction support sparse using Θ(K log(n) log log(n)) samples log1+r(n)) computational cost, where r > 0 small constant. sample complexities are near order-optimal. Further, exact log(K) log1+r(n)). With mild technical assumption on existence code universal decoding complexity, achieve for recovery, furthermore, full recovery. design based graph codes. also justify theoretical results numerical experiments.
sci-hub.se 参考文章(17)
Sameer Pawar, Kannan Ramchandran, Xiao Li, Sub-linear Time Support Recovery for Compressed Sensing using Sparse-Graph Codes arXiv: Information Theory. ,(2014)
J. Justesen, Class of constructive asymptotically good algebraic codes IEEE Transactions on Information Theory. ,vol. 18, pp. 652- 656 ,(1972) , 10.1109/TIT.1972.1054893
Sameer Pawar, Kannan Ramchandran, A robust R-FFAST framework for computing a k-sparse n-length DFT in O(k log n) sample complexity using sparse-graph codes international symposium on information theory. pp. 1852- 1856 ,(2014) , 10.1109/ISIT.2014.6875154
Michael Lustig, David Donoho, John M Pauly, None, Sparse MRI: The application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine. ,vol. 58, pp. 1182- 1195 ,(2007) , 10.1002/MRM.21391
Wassily Hoeffding, Probability Inequalities for sums of Bounded Random Variables Journal of the American Statistical Association. ,vol. 58, pp. 13- 30 ,(1963) , 10.1007/978-1-4612-0865-5_26
S. Sarvotham, D. Baron, R.G. Baraniuk, Sudocodes ߝ Fast Measurement and Reconstruction of Sparse Signals international symposium on information theory. pp. 2804- 2808 ,(2006) , 10.1109/ISIT.2006.261573
J. Romberg, Imaging via Compressive Sampling IEEE Signal Processing Magazine. ,vol. 25, pp. 14- 20 ,(2008) , 10.1109/MSP.2007.914729
Joel A. Tropp, Anna C. Gilbert, Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit IEEE Transactions on Information Theory. ,vol. 53, pp. 4655- 4666 ,(2007) , 10.1109/TIT.2007.909108
Piotr Indyk, Milan Ruzic, Near-Optimal Sparse Recovery in the L1 Norm foundations of computer science. pp. 199- 207 ,(2008) , 10.1109/FOCS.2008.82