Abstract
Recovery algorithms play a key role in compressive sampling (CS). Most of current CS recovery algorithms are originally designed for one-dimensional (1D) signal, while many practical signals are two-dimensional (2D). By utilizing 2D separable sampling, 2D signal recovery problem can be converted into 1D signal recovery problem so that ordinary 1D recovery algorithms, e.g. orthogonal matching pursuit (OMP), can be applied directly. However, even with 2D separable sampling, the memory usage and complexity at the decoder are still high. This paper develops a novel recovery algorithm called 2D-OMP, which is an extension of 1D-OMP. In the 2D-OMP, each atom in the dictionary is a matrix. At each iteration, the decoder projects the sample matrix onto 2D atoms to select the best matched atom, and then renews the weights for all the already selected atoms via the least squares. We show that 2D-OMP is in fact equivalent to 1D-OMP, but it reduces recovery complexity and memory usage significantly. What’s more important, by utilizing the same methodology used in this paper, one can even obtain higher dimensional OMP (say 3D-OMP, etc.) with ease.
Similar content being viewed by others
References
Candes E, Romberg J, Tao T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans Inform Theory, 2006, 52: 489–509
Candes E, Tao T. Near optimal signal recovery from random projections: universal encoding strategies. IEEE Trans Inform Theory, 2006, 52: 5406–5425
Donoho D. Compressed sensing. IEEE Trans Inform Theory, 2006, 52: 1289–1306
Candes E, Tao T. Decoding by linear programming. IEEE Trans Inform Theory, 2005, 51: 4203–4215
Tropp J, Gilbert A. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans Inform Theory, 2007, 53: 4655–4666
Pope G. Compressive sensing: a summary of reconstruction algorithms. Master thesis. Zürich: Eidgenössische Technische Hochschule. 2009
Rivenson Y, Stern A. Compressed imaging with a separable sensing operator. IEEE Signal Process Lett, 2009, 16: 449–452
Ghaffari A, Babaie-Zadeh M, Jutten C. Sparse decomposition of two dimensional signals. In: IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, Taipei, 2009. 3157–3160
Liu Y, Wu M Y, Wu S J. Fast OMP algorithm for 2D angle estimation in MIMO radar. IET Electronics Lett, 2010, 46: 444–445
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fang, Y., Wu, J. & Huang, B. 2D sparse signal recovery via 2D orthogonal matching pursuit. Sci. China Inf. Sci. 55, 889–897 (2012). https://doi.org/10.1007/s11432-012-4551-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11432-012-4551-5