The fast algorithm of spark in compressive sensing

Meihua Xie; Fengxia Yan

doi:10.1117/12.2265341

23 January 2017 The fast algorithm of spark in compressive sensing

Meihua Xie, Fengxia Yan

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

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available