Abstract. In this article detection algorithms
of discrete sparse signal with discrete Gaussian white noise with
reconstruction and without reconstruction of nonzero signal components from the
observed compressed data vector were proposed. Various conditions under which
the positions and values of nonzero components in a discrete signal could be
known and unknown were considered. Computer modeling of the proposed algorithms was performed
and analysis of effectiveness of these algorithms based on investigation of
behavior of total error probability depending on signal to noise ratio,
compression level and sparsity of original signal was implemented. It was
found, that the total probability of error for all synthesized algorithms
decreases with increasing signal to noise ratio and decreases with increasing
ratio of the number of elements in the observed data vector to the number of
elements in the original discrete signal. Besides, for most algorithms, total
probability of error decreases with decreasing the number of nonzero components
in the signal. In this article approximate theoretical formulas for the total probability
of error were represented. These formulas are applicable, when the positions of
the nonzero signal components are known and relatively well describe the
behavior of the total probability of error from the indicated parameters. Obtained
data can be used for a reasonable choice of the parameters of the random
demodulator depending on the observation conditions.
Key words: detection algorithm, discrete
signal, Nyquist frequency, sparse signal, Compressive Sensing, Orthogonal Matching
Pursuit (OMP), likelihood ratio, ideal observer criterion, total probability of
error, signal to noise ratio.
1. Proakis J.G. Cifrovaya svjaz'.
[Digital communications]. Moscow, Radio i svjaz' Publ. 1978. 296 p. (In
2. Hayashi K., Nagahara M.,
Tanaka T. A User’s guide to compressed sensing for communications systems. IEICE
Transaction on communications, 2013, Vol. E96-B, No. 3, pp. 685 – 712. DOI:
3. Ifeachor E.C., Jervis
B.W. Cifrovaja obrabotka signalov. Prakticheskij podhod. [Digital Signal
Processing. A practical approach]. Moscow, Williams Publ. 2004. 992 p. (In
4. Eldar C., Kutyniok G.
Compressed sensing: theory and applications. Cambridge University Press. 2012.
5. Foucart S., Rauhut H. A
mathematical introduction to compressive sensing. Springer. 2013. 625 p.
6. Parfenov V.I.,
Golovanov D.Y. Detection of unoccupied frequency subbands on the compressed measurements.
Infokommunikacionnye tehnologii – Infocommunication technologies, 2015,
Vol.13, No.3, pp. 305 – 312. (In Russian)
7. Parfenov V.I.,
Golovanov D.Y. Principles of construction and effectiveness analysis of
operation of wireless sensor networks based on compressive sensing theory. Cifrovaja
obrabotka signalov – Digital signal processing, 2016, No.2, pp. 14 – 19.
8. Tropp J., Laska J., Duarte M., Romberg J., Baraniuk R. Beyond Nyquist: efficient sampling of sparse bandlimited
signals. IEEE Transaction on Information Theory, 2010, Vol.56, No.1, pp.
520 – 544. DOI: 10.1109/TIT.2009.2034811
9. Baraniuk R., Davenport M., Duarte M., Hegde C. An introduction to compressive sensing. Houston, Rice University Press. 2011. 112 p.
10. Akimov P.S., Bakut
P.A., Bogdanovich V.A. Teorija obnaruzhenija signalov. [Theory of signal detection].
Moscow, Radio i svjaz' Publ. 1984. 440 p. (In Russian)
11. Coluccia G., Roumy A.,
Magli E. Exact performance analysis of the oracle receiver for compressed
sensing reconstruction. IEEE International Conference on Acoustics, Speech and
Signal Processing ICASSP 2014. Florence, Italy, 4 – 9 May 2014, pp. 1005 – 1009.
12. Tropp J., Gilbert A.
Signal recovery from random measurements via orthogonal matching pursuit. IEEE
Transaction on Information Theory, 2007, Vol. 53, No.12, pp. 4655 – 4666. DOI:
13. Wang Y., Yin W. Sparse
signal reconstruction via iterative support detection. SIAM Journal on Imaging Sciences, 2010, Vol.3, No.3, pp. 462 – 491. DOI: 10.1137/090772447