Sparse Signals Reconstruction via Adaptive Iterative Greedy Algorithm

Abstract

Compressive sensing(CS) is an emerging research field that has applications in signal processing, error correction, medical imaging, seismology, and many more other areas. CS promises to efficiently reconstruct a sparse signal vector via a much smaller number of linear measurements than its dimension. In order to improve CS reconstruction performance, this paper present a novel reconstruction greedy algorithm called the Enhanced Orthogonal Matching Pursuit (E-OMP). E-OMP falls into the general category of Two Stage Thresholding(TST)-type algorithms where it consists of consecutive forward and backward stages. During the forward stage, E-OMP depends on solving the least square problem to select columns from the measurement matrix. Furthermore, E-OMP uses a simple backtracking step to detect the previous chosen columns accuracy and then remove the false columns at each time. From simulations it is observed that E-OMP improve the reconstruction performance better than Orthogonal Matching Pursuit (OMP) and Regularized OMP (ROMP).

References

• D. L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4):1289–1306, Apr. 2006.
• Walid Osamy, Ahmed Salim, and Ahmed Aziz. Efficient compressive sensing based technique for routing in wireless sensor networks. INFOCOMP Journal of Computer Science, 12(1):01–09, 2013.
• K. Choi and J. Wang. Compressed sensing based cone-beam computed tomography reconstruction with a first-order method. Med. Phys, 37:5113–5125, 2010.
• E. J. Candes and T. Tao. Decoding by linear programming. IEEE Trans. Inf. Theor. , 51(12):4203–4215, December 2005.
• J. Romberg and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory, 52(2):89509, 2006.
• Emmanuel J. Cand`es, Mark Rudelson, Terence Tao, and Roman Vershynin. Error correction via linear programming. In FOCS, pages 295–308. IEEE Computer Society, 2005.
• Joel A. Tropp and Stephen J. Wright. Computational methods for sparse solution of linear inverse problems. Proceedings of the IEEE, 98(6):948–958, 2010.
• S. G. Mallat and Z. Zhang. Matching pursuits with time-frequency dictionaries. IEEE Trans. Signal Process, 41(12):33973415, 1993.
• J. A. Tropp and A. C. Gilbert. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans. Inform. Theory, 53(12):4655–4666, Dec. 2007.
• Joel A. Tropp and Deanna Needell. Cosamp: Iterative signal recovery from incomplete and inaccurate samples. CoRR, abs/0803. 2392, 2008.
• Wei Dai and Olgica Milenkovic. Subspace pursuit for compressive sensing signal reconstruction. IEEE Trans. Inf. Theor. , 55(5):2230–2249, May 2009.
• Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for compressed sensing. CoRR, abs/0805. 0510, 2008.
• Deanna Needell and Roman Vershynin. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Found. Comput. Math. , 9(3):317–334, April 2009.
• D. L. Donoho, Y. Tsaig, I. Drori, and J. L. Starck. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit. IEEE Trans. Inf. Theor. , 58(2):1094–1121, February 2012.
• Arian Maleki and David L. Donoho. Optimally tuned iterative reconstruction algorithms for compressed sensing. CoRR, abs/0909. 0777, 2009.
• Honglin Huang and Anamitra Makur. An adaptive omp-based compressive sensing reconstruction method for unknown sparsity noisy signals. SampTA, 2011.
• V. Cevher and S. Jafarpour. Fast hard thresholding with nesterovs gradient method. in: Neuronal Information Processing Systems, Workshop on Practical Applications of Sparse Modeling, Whistler, Canada, 2010.
• Yu Nesterov. Smooth minimization of non-smooth functions. Math. Program. , 103(1):127–152, May 2005.
• Nazim Burak Karahanoglu and Hakan Erdogan. A* orthogonal matching pursuit: Best-first search for compressed sensing signal recovery. CoRR, abs/1009. 0396, 2010.

Index Terms

Keywords