Share Email Print

Proceedings Paper

The fast algorithm of spark in compressive sensing
Author(s): Meihua Xie; Fengxia Yan
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 23 January 2017
PDF: 4 pages
Proc. SPIE 10322, Seventh International Conference on Electronics and Information Engineering, 103224J (23 January 2017); doi: 10.1117/12.2265341
Show Author Affiliations
Meihua Xie, Hunan International Economics Univ. (China)
National Univ. of Defense Technology (China)
Fengxia Yan, National Univ. of Defense Technology (China)

Published in SPIE Proceedings Vol. 10322:
Seventh International Conference on Electronics and Information Engineering
Xiyuan Chen, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?