A Fast Algorithm of Compressed Sensing for 2D Signals

ABSTRACT

Compressed sensing (CS) is a new signal acquisition method that can do sampling and compression of signals simultaneously. In order to reduce the signal reconstruction time of CS algorithms and lower the growth rate of the reconstruction time when increasing the size of signals, this paper proposes the algorithm of block whole orthogonal matching pursuit (BWOMP), which is a fast CS algorithm based on the method of orthogonal matching pursuit (OMP) for two-dimension (2D) signals. BWOMP defines a measurement parameter named whole-correlation. At each iteration, instead of computing the correlation between each atom and 1D residuals, the whole-correlation is computed as the correlation between the atom and the 2D residuals. After that, an approximation of the 2D signal is generated directly by BWOMP. By reducing the number of the iterations, this method can significantly lower the computational complexity. On the other hand, BWOMP introduces the concept of block compressed sensing (BCS), and redesigns the block size and the observation matrix. BCS reduces the consumption of computational resources (i.e. memory and CPU cycles) by reducing the size of variables (especially the matrixes). The experimental comparisons show that, in comparison with OMP, BWOMP can save at least 80% reconstruction time, which makes the increasing rate of reconstruction time linear. The results indicate that the proposed algorithm may have great performance advantage for complex cases.

KEYWORDS:

• Compressed sensing
• fast reconstruction
• whole-correlation
• block reconstruction
• linear growth

Acknowledgments

We would like to thank J. Tropp, Wei Sha and D. L. Donoho for their valuable research in OMP and StOMP that is the basis of our study. We also gratefully acknowledge two anonymous reviewers for their helpful comments, and editors, for their work and help to our paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the Natural Science Foundation of China [number 61170035], [number 61272420], [number 61202003], [number 61502411]; the major projects of Nature Science Foundation of Jiangsu [number BK2011022]; the Innovation Foundation of Science and Technology Enterprises of Jiangsu [number BC2015178], the Prospective Joint Research Project of Jiangsu [number BY2014108-20], and NUST project [number 2011YBXM18].

Notes on contributors

Yongping Zhang

Yongping Zhang (born 1979) received his PhD in Computer (2014) from Nanjing University of Science and Technology. Now, he is a teacher at Yancheng Institute of Technology. His main research interests include Internet of Things, compressed sensing, cloud computing and distributed computing.

E-mail: [email protected]

Gongxuan Zhang

Gongxuan Zhang (born 1961) received his PhD in Computer (2005) from Nanjing University of Science and Technology. Now, he is a full professor and PhD supervisor of computer at Nanjing University of Science and Technology. His current research interests include client/server computing, CORBA technology, web service, information security, and network and distributed computing.

E-mail: [email protected]

Zhaomeng Zhu

Zhaomeng Zhu (born 1989) is PhD candidate of Nanjing University of Science and Technology in Computer. His current research interests include network and distributed computing, and cloud computing.

E-mail: [email protected]