23 January 2017 The fast algorithm of spark in compressive sensing
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.
© (2017) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Meihua Xie, 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); doi: 10.1117/12.2265341; https://doi.org/10.1117/12.2265341
PROCEEDINGS
4 PAGES


SHARE
Back to Top