The fast algorithm of spark in compressive sensing

Meihua Xie; Fengxia Yan

doi:10.1117/12.2265341

Translator Disclaimer

23 January 2017 The fast algorithm of spark in compressive sensing

Meihua Xie, Fengxia Yan

Author Affiliations +

Proceedings Volume 10322, Seventh International Conference on Electronics and Information Engineering; 103224J (2017) https://doi.org/10.1117/12.2265341
Event: Seventh International Conference on Electronics and Information Engineering, 2016, Nanjing, China

Abstract

Compressed Sensing (CS) is an advanced theory on signal sampling and reconstruction. In CS theory, the reconstruction condition of signal is an important theory problem, and spark is a good index to study this problem. But the computation of spark is NP hard. In this paper, we study the problem of computing spark. For some special matrixes, for example, the Gaussian random matrix and 0-1 random matrix, we obtain some conclusions. Furthermore, for Gaussian random matrix with fewer rows than columns, we prove that its spark equals to the number of its rows plus one with probability 1. For general matrix, two methods are given to compute its spark. One is the method of directly searching and the other is the method of dual-tree searching. By simulating 24 Gaussian random matrixes and 18 0-1 random matrixes, we tested the computation time of these two methods. Numerical results showed that the dual-tree searching method had higher efficiency than directly searching, especially for those matrixes which has as much as rows and columns.

Citation Download Citation

Meihua Xie and Fengxia Yan "The fast algorithm of spark in compressive sensing", Proc. SPIE 10322, Seventh International Conference on Electronics and Information Engineering, 103224J (23 January 2017); https://doi.org/10.1117/12.2265341

ACCESS THE FULL ARTICLE