PAGE 1
LOCALIZATION OF SPARSE SIGNALS by SINDUJA SEETHAPATHY B.E., Anna University, 2012 A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfillment of the requirements for the degree of Master of Science Electrical Engineering 2015
PAGE 2
ii This thesis for the Master of Science Degree by Sinduja Seethapathy has been approved for the Electrical Engineering Program by Titsa Papantoni, Chair Jan Bialasiewicz Mark Golkowski 4/20/2015
PAGE 3
iii Sinduja Seethapathy (M.S in Electrical Engineering) Localization of Sparse Signals Thesis directed by Professor Titsa Papantoni ABSTRACT The recently popular term sparse signal refers to occasional or scattered occurrence. On the other hand, the effective transmission of such signals, previously denoted as bursty, has been addressed by treesearch as well as random access algorithms. The refreshed interest on sparse signals has focused on their extraction via linear transformations, while the term robustness has simultaneously been used loosely. This thesis addresses the detection or localization of sparse signals using a parametric optimal detector (in the absence of outliers), a robust detector (in the presence of outliers) and a treesearch detector and focusing on a specific signal model. As a special case, we assume that a constant sparse signal is embedded in additive white noise. For this special case, we first derive the optimal parametric detector; secondly, we develop a robust detector designed to counteract occasional occurrences of outliers; finally, we propose and analyze a treesearch detector. For each one of the three detectors, we assume that the signal occurrence is modeled by a Bernoulli process and we study their performance in terms of probability of correct detection, complexity and resistance to outliers. We also include and discuss numerical evaluations. The form and content of this abstract are approved. I recommend its publication. Approved: Titsa Papantoni
PAGE 4
iv I dedicate it to my loving parents.
PAGE 5
v ACKNOWLEDGEMENT I cannot express enough thanks to my committee for their continued support and encouragement: Dr. Titsa Papantoni, my committee chair, Dr. Mark Golkowski and Dr. Jan Bialasiewicz, I also wish to thank Ms. Ashanthi Maxworth. I offer my sincere appreciation for the learning opportunities provided by my committee. My completion of this thesis could not have been accomplished without my family: my parents Mr. M. Seethapathy and Mrs. S. Krishna Veni, my brother S. Lakshmi Narayanan and my special friend R. Sakthivishnu. I also thank my friends and family who stood by me and supported me. They have been a moral support in my hard times. My heartfelt thanks to all of them.
PAGE 6
vi TABLE OF CONTENTS CHAPTER I. INTRODUCTION 1 II. PROBLEM STATEMENT AND GENERAL SOLUTION 4 (a) Optimal ML Detector 5 III. CONSTANT SIGNAL AND WHITE GAUSSIAN ADDITIVE NOISE 9 (a) Optimal ML Detector 9 IV. THE OUTLIER RESISTANT DETECTOR .... 17 (a) Robustl ML Detector ..... 17 V. SUBOPTIMAL TREE SEARCH DETECTORS .. 30 VI. THE BERNOULLI SIGNALPRESENCE MODEL .. 38 VII. DISCUSSION AND CONCLUSION ... 47 REFERENCES .. 49 APPENDIX ... 50
PAGE 7
vii LIST OF FIGURES FIGURE 1 Shows the 'n' VS 'P d YDOXHVIRUGLIIHUHQW.YDOXHVIRU615 DQG1 ( 4 for parametric detector in the absence of outliers. (from equation (4)) 2 Shows the 'n' VS 'P d nYDOXHVIRUGLIIHUHQW.YDOXHVIRU615 DQG1 ( 4 for parametric detector in the absence of outliers. (from equation (4)) 3 Shows the 'n' VS 'P d nYDOXHVIRUGLIIHUHQW.YDOXHVIRU615 DQG1 ( 4 for parametric detector in the absence of outliers. (from equation (4)) 4 Shows the 'n' VS 'P d nYDOXHVIRUGLIIHUHQW.YDOXHVIRU615 DQG1 ( 4 for parametric detector in the absence of outliers. (from equation (4)) 5 Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for robust detector in the absence of outliers. (from equation (14)) 6 Shows the 'n' VS 'P d graph for diff HUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for robust detector in the absence of outliers. (from equation (14)) 7 Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for robust detector in the absence of outliers. (from equation (14)) 8 Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for robust detector in the absence of outliers. (from equation (14)) 9 Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for parametric detector in the presence of outliers. (from equation (16)) 10 Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for parametric detector in the presence of outliers. (from equation (16)) 11 Shows the 'n' VS 'P d graph IRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for parametric detector in the presence of outliers. (from equation (16)) 12 Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for parametric detector in the presence of outliers. (from equation (16)) 13 Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for robust detecto r in the presence of outliers. (from equation (17)) 14 Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for robust detector in the presence of outliers. (from equation (17)) 15 Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for robust detector in the presence of outliers. (from equation (17)) 16 Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG1 ( 5 for robust detector in the presence of outliers. (from equation (17)) 17 The probability of correct detection P d (n, q) in (26) for the treesearch detector, as function of n, for q = 0.01(from equation (26)) 18 The probability of correct detection P d (n, q) in (26) for the treesearch detector, as function of n, for q = 0.01 (from equation (26))
PAGE 8
viii 19 Shows the comparison between the parametric and the robust in the absence of outliers, p UREDELOLWLHVLQDQGIRUT DQG615 ZKHQ0 (from equation (28)&(29)) 20 Shows the comparison between the parametric and robust detector model in the absence of outliers, probabilities in (19) and (20), for q = 0.05 and SNR= 0.5, ZKHQ0 IURPHTXDWLRQ 20 Shows the comparison between parametric and robust detector in the presence of RXWOLHUVSUREDELOLWLHVLQDQGIRUT DQG615 ZKHQ DQG0= 0.05. (from equation (30)&(31)) 22 Shows the comparison between parametric and robust detector in the presence of RXWOLHUVSUREDELOLWLHVLQDQGIRUT DQG615 ZKHQ DQG0 IURPHTXDWLRQ 23 Shows the comparison between parametric and robust detector in the presence of RXWOLHUVSUREDELOLWLHVLQDQGIRUT DQG615 ZKHQ DQG0= 0.05. (from equation (30)&(31)) 24 Shows the comparison between parametric and robust detector in the presence of outliers, probabilities in (21) and (22), IRUT DQG615 ZKHQ DQG 0 IURPHTXDWLRQ
PAGE 9
1 CHAPTER I INTRODUCTION There are many applications in signal processing and communication systems where the discrete signals are sparse in some domain such as time, frequency, or space; i.e., most of the samples are zero, or alternatively, their transforms in another domain are sparse. There are trivial sparse transformations where the sparsity is SUHVHUYHGLQERWKWKHWLPHDQGIUHTXHQF\GRPDLQVWKHLGHQWLW\WUDQVIRUPPDWUL[ and its permutations are extreme examples. Wavelet transformations that preserve the local characteri VWLFVRIDVSDUVHVLJQDOFDQEHUHJDUGHGDVDOPRVWVSDUVHLQWKH IUHTXHQF\GRPDLQLQJHQHUDOIRUVSDUVHVLJQDOVWKHPRUHVLPLODUWKH transformation matrix is to an identity matrix, the sparser the signal is in the transform domain. In any of these scenarios, sampling and processing can be optimized using sparse signal processing. In other words, the sampling rate and the processing manipulations can be significantly reduced; hence, a combination of data compression and processing time reduction can be achieved. Each field has developed its own tools, algorithms, and reconstruction methods for sparse signal processing. The sparse signal recovery problem has been the subject of extensive research over the last few decades in several different research communities, including applied mathematics, statistics, and theoretical computer science. The goal of this research has been to obtain higher compression rates; stable recovery schemes; low encoding, update and decoding times; analytical recovery bounds; and resilience to noise. The momentum behind this research is welljustified: underdetermined linear regression problems in tandem with sparse representations underlie the paradigm of signal compression and denoising in signal processing, the tractability and generalization of learning algorithms in machine learning, the stable embedding and decoding properties of
PAGE 10
2 codes in information theory, the effectiveness of data streaming algorithms in theoretical computer science, and neuronal information processing and interactions in computational neuroscience. Sparse representations of signals have received a great deal of attentions in recent years. The problem solved by the sparse representation is to search for the most compact representation of a signal in terms of linear combination of atoms in an over complete dictionary. Recent developments in multiscale and multiorientation representation of signals, such as wavelet, ridgelet, curvelet and contourlet transforms are an important incentive for the research on the sparse representation. Compared to methods based on orthonormal transforms or direct time domain processing, sparse representation usually offers better performance with its capacity for efficient signal modelling. The refreshed interest on sparse signals has focused on their extraction via linear transformations, while the term robustness has been used loosely. This thesis addresses the detection of sparse signals using a parametric optimal detector (in the absence of outliers), a robust detector (in the presence of outliers) and a treesearch detection method. As a special case, we initially assume that a constant sparse signal is embedded in additive white noise. We then develop a parametrically optimal and a robust detector, where the latter is designed to resist the effect of occasional extreme outlier data; we also develop a tree search detector. We analyze the performance of all three detectors with regard to the probabilities of correct detection they induce, subject to the occurrence of the constant signal being generated by a Bernoulli model. We include and discuss numerical evaluations, as well. The organization of the thesis is as follows: In Section 2, we state the fundamental general problem of sparse signal processing, including general assumptions and notation, and we discuss existing published results in the area. In
PAGE 11
3 Section 3, we first present and analyze the general sparse signal detector, when data observations are stationary and memory less; we then analyze the special case where the sparse signal is a constant transmitted in additive Gaussian white noise. In Section 4, we consider the case where observation data are contaminated with occasional data outliers, while the sparse signal is a constant transmitted through additive white Gaussian noise; we then present and analyze a robust detector, which is designed to protect decisions from the presence of extreme outlier data. In Section 5, we present and analyze a treesearch sub optimal detector for sparse signals that are widely spread. In Section 6, we present a specific Bernoulli signal generating model; we use results developed in Sections 4 and 5 to analyze probability of correct detection performance In Section 7, we state conclusions, as well as directions for future work. Finally in section 8, we list some references.
PAGE 12
4 CHAPTER II PROBLEM STATEMENT AND GENERAL SOLUTION In this section we present the overall problem statement and derive the general detector for sparse signals in memory less and stationary environments. Consider observations generated by a sequence of mutually independent random variables. Since the signal is considered to be sparse, only a small percentage of the observations represent the signal, while the remaining major percentage represents just noise. Let the percentage representing the signal be bounded from DERYHE\DJLYHQYDOXH.:HDVVXPHWKDWWKHUDQGRPYDULDEOHVUHSUHVHQWLQJWKHsignal as well as those representing the noise are identically distributed. We denote by x 1 [ n a sequence of n such observations which consists of both noise and signal, while we denote by X 1 ; n the sequence of mutually independent random variables whose realization is the sequence x 1 [ n We also denote by f 1 (.) the probability distribution function (for discrete variables) or probability density function (for absolutely continuous variables) of signal including observationsnoted as pdfwhile we denote by f 0 (.) the pdf for noise only observations. Given the observations x 1 [ n and the pdf s f 1 (.), f 0 (.) the objective is to identify the locations of the signal presence; that is, which ones of the x 1 [ n observations originated from the pdf f 1 (.). Our approach to the problem will be Maximum Likelihood (ML), deciding in favor of the signal locations which maximize the probability of the observed data set. ML is equivalent to the Bayesian minimization of error probability approach, when all the signal locations and their number are equally probable.
PAGE 13
5 Given the sequence x 1 [ n the optimal detector decides in favor of i 1 L m ; 0<=m<= n signal locations if: r ÂŽÂ‘Â‰ B 5 : T ; rE 5 rHKCB 4 : T ; < = rLÂÂƒÂšFr ÂŽÂ‘Â‰ B 5 : T ; rE :; rHKCB 4 : T ; < = G (1) f 1 (x k )Probability density function of x k for signal presence f 0 (x k )Probability density function of x k for signal absence Let us define: C : T ; ÂŽÂ‘Â‰ @ :; :; A (2) The above expression is called the log likelihood ratio. Via some straight forward modifications of the expression in (1), we may then express the optimal ML detector as follows: (a) Optimal ML Detector 1) Given the sequence x 1, x n compute all g(x j Â” j Â” n 2) If g(x k Â” ; for all k Â” k Â” n then, decide that no observation contains signal. 3) If a set of integers ; {i 1 L m } and g(x k Â” ; for all k and g(x k Â” ; for all then decide that the observations containing the signal are all those with indices in the set {i 1 L m }. 4) If a set of integers {i 1 L m } ; m > .Q : g(x k ) > 0 ; for all k {i 1 L m } and g ( x k Â” 0; for all k Â^L 1 L m } then decide that the observations containing the signal are those whose indices k are contained in the set {i 1 L m } and whose g( xk ) values are the .Q highest in the set.
PAGE 14
6 Considering the log likelihood ratio in (2), let h i (w ) and H i (w); i = 0, 1, denote, respectively, the pdf and the cumulative distribution function of the random variable g(X) at the value point w, given that the pdf of X is f i i = 0, 1 Let P d (0) denote the probability of correct detection induced by the optimal ML detector, given that no observation contains signal. Let, instead, P d ({ i 1 L m }) denote the probability of correct detection given that the indices of the observations containing signal are given by the set {i 1 L m }. Then, assuming absolutely continuous {X i } random variables; without lack in generality, we obtain the following expressions; without much difficulty, where .Q is assumed an integer; for simplicity in notation: 2 : r ; rL > 4 :r; ? (3) P d (0)Probability of correct detection given that no observation contains signal H 0 (0)Cumulative distribution function of a no signal containing observation, at a point zero. 2 :< E 5 E =; rL > srF* 5 : r ;? > 4 : r ;? ? srQIrQJ2 :< E 5 E =; rLJr@SD 5 : S ;> srF* 5 : S ;? ?5 > 4 : S ;? : 5? ; IrLJ 4 (4) P d (i 1 ,...,i m )Probability of correct detection when the indices of signal containing observations are in (i 1 ,..,i m ) H 1 (0)Cumulative distribution function of a signal containing observation, at the point zero. h 1 (w) probability density function of a signal containing observation, at the point w. J is assumed to be an integer
PAGE 15
7 Remarks It is important to note that the optimal detector presented above assumes no knowledge as to any structure of the sparse signal and requires nsize memory, as well as ordering of the positive g(x k ) values, inducing complexity of order nlogn. If, on the other hand, a structure of the signal is known a priori and is such that it appears as a bursty batch, then, the sequential algorithm which is involved monitors changes in distribution should be deployed instead; it requires no memory and its complexity is of order n The authors in [8] considered the case where data sequences may be generated by either one of a number of nonparametrically defined processes and where the data generating process may change at any point in time. The aim was to effectively track the changes, where each acting process is essentially represe nted by a whole class of parametrically defined processes. The sequential robust algorithm they developed detects efficiently changes in data generating processes, while it simultaneously protects performance against extraneous data outliers. The algorithm was numerically evaluated when a shift from one Gaussian process to another is being monitored, while data outliers may be present; its performance was compared to that of the parametric monitoring algorithm. The robust algorithm generally offers high protection against extreme data outliers with simultaneous minimal loss of SHUIRUPDQFHDWWKHQRPLQDOPRGHO)RURQO\WZRSURFHVVHV 0 DQG 1, may be involved in generating the data and a change IURP 0 WR 1 is monitored, the algorithm in [8] operates as follows: A threshold S>0 is a priori selected and the algorithmic value at time zero is set as, T 0 =0 Let T n1 (x 1 n1 ) denote the value of the algorithm at time n1 given that the sequence x 1 n1 = [x x n1 ] has been observed and the threshold S has not been crossed yet. Upon observation of a new datum x n the algorithm updates then to the value T n (x 1 n ) as follows:
PAGE 16
8 T n (x 1 n )= max(0, T n1 (x 1 n1 )+log(f 1 (x n x 1 n1 )/f 0 (x n x 1 n1 )) Stop the first time n, such that T n (x 1 n Â•6 DQGGHFLGHWKDWWKHFKDQJH 0 WR 1 occurred. where, f i (x n x 1 n1 )density function of the data point x n conditioned on the sequence x 1 n1 ; i = 0,1. The false alarm and power probability curves (as functions of time n) have been derived for various data generating processes, such as Poisson, towards designing threshold parameter values which satisfy required false alarm versus power tradeoffs. The performance of the algorithm is strongly influenced by the KullbackLeibler number ( Nonsymmetric measure of the difference between two probability distribution P and Q. Dkl(PQ) is the measure of info lost when Q is used to approximate P) between the two involved data generating processes. As the KullbackLeibler number increases, the performance improves.
PAGE 17
9 CHAPTER III CONSTANT SIGNAL AND WHITE GAUSSIAN ADDITIVE NOISE In this section we consider the special case where the signal is a known constant T 0 and the noise is zero mean white Gaussian with standard deviation V per observation, *1 After some straight forward normalizations, the optimal ML detector described in Section 2 takes here the following form: (a) Optimal ML Detector 1) Given the sequence x 1 [ n compute all (x i T/2) ; 1 d j d n 2) If (x k T/2) d 0 ; for all k, 1 d k d n then, decide that no observation contains signal. 3) If a set of integers {i 1 L m }; 1 d m d Dn: (x k T/2) 0 ; for all k Â {i 1 L m } and (x k T/2) d 0 ; for all k Â {i 1 L m }, then decide that the observations containing the signal are all those with indices in the set {i 1 L m }. 4) If a set of integers {i 1 L m }; m Dn : (x k T/2) 0 ; for all k Â {i 1 L m } and (x k T/2) d 0 ; for all k Â {i 1 L m }, then decide that the observations containing the signal are those whose indices k are contained in the set {i 1 L m } and whose (x k T/2) values are the D n highest in the set. 2 : < E 5 E = ; rLrdÂ£rl t rprh rrQIrQJ 2 : < E 5 E = ; rLJr@S : S ; >Â£ : rFS ; ? ?5 ? 6 rdÂ£rlSrE rprh : 5? ; rLJr@S : S ; >Â£ : S ; ? ?5 ? 6 rdÂ£rlrFSrE rprh : 5? ; IrLJ (5) The complexity of the above detector is of order nlogn Denoting by M (x) and )(x) respectively, the pdf and the cumulative distribution function (cdf) of the zero me an and unit variance Gaussian random variable and assuming D n as an integer, we
PAGE 18
10 have from [3] that the conditional probabilities of correct detection, conditioned on the number of observations containing signal, are given in this case by the expressions below where. Remarks It is interesting to note here that if it is known that the signal may appear as a set of bursty batches of unknown sizes, then the reinitialization sequential algorithm in [8] will sequentially detect the beginning and the ending of each batch with minimal complexity, no memory requirements and with accuracy increasing with the signalto noise ratio and the size of the each batch. Let then T n denote the value of the algorithm which detects the beginning of such a batch, upon the processing of the n th datum x n from its beginning. Let W n denote the value of the algorithm which detects the ending of each batch, upon processing the n th datum y n from the beginning of its initialization. The whole algorithmic system then works as follows: 1) Process the observed sequence x 1 ,....,x n sequentially starting with the algorithm {T n } whose values are updated as follows: 6 4 "r 6 >5 rLI=Trlr6 rET >5 rF t rp Stop the first time n such that i and declare n as the time when the signal batch begins. Then, switch immediately to the algorithm { W n } whose values are updated as follows, where time zero denotes the time when the algorithm begins and where y n denotes the n th observed datum after the latter beginning. 2) 9 4 "r
PAGE 19
11 9 >5 rLI=TrlrS rEU >5 rE t rp Stop the first time n, such that Wn Â• 5 and declare that the signal batch has ended. We now express a Corollary which will be useful in the computation of bounds for the probability of correct detection in (4). The expressions in the Corollary are derived from recursive relationships produced via integration by parts and can be proven easily by induction. Corollary The following equations hold: r@S : S ; Â£ : S ; rL : GrEs ; ?5 ? Â£ >5 :; (6) r@S : S ; Â£ : S ; rL : GrEs ; ?5 4 rcÂ£ >5 : ; rFt ?:>5; rg (7) r@S : S ; Â£ : S ; ? Â£ ? : rFS ; rL : JrFG ; G : JrEs ; r@ JrEs I A >5 @>5 Â£ >5? :rF;Â£ :; r@S : S ; Â£ : S ; Â£ : rFS ; 4 rLr IG : GrEsrEE ; : IrFE ; @4 rkÂ£ >5> : ; Â£ ? : rF ; rFt ? : >>5 ; ro (8)
PAGE 20
12 Lemma 1 below utilizes the results in the Corollary, to express two lower bounds for the probability of correct detection in (4). The bound in (9) is relatively tight for low signalto QRLVHUDWLRYDOXHV17KHERXQGLQLVUHODWLYHO\WLJKWIRUKLJKVLJQDO to QRLVHUDWLR1LQVWHDG Lemma 1 The probability of correct detection in (4) increases monotonically with increasing value of the signalto QRLVHUDWLR1FRQYHUJLQJWRWKHYDOXHDV1 reaches asymptotically large values. This probability is bounded from below as IROORZVDVVXPLQJWKDW. n is an integer; for simplicity in notation: 2 : < E 5 E = ; rP >: srF ; J ? > JrFs ? J rHr@ JrEs I A >5 @ Â£ rl t rpÂ£ >5? rlrF t rpIrLJ (9) 2 : < E 5 E = ; rPr >: srF ; J ? > JrFs ? >: srF ; JrFE ? > JrEE ? : 5? ; @4 rHrlÂ£ > rl t rpÂ£ : 5? ; ? rlrF t rprFt ? : >5 ; rpIrLJ (10)
PAGE 21
13 Proof &RQVLGHULQJ1DV\PSWRWLFDOO\ODUJHZHILUVWDSSUR[LPDWH &! by 1, in Expression (4). We then, use expression (5) and consider again asymptotically large YDOXHVRI17KHUHVXOWSURYHVWKDWWKHSUREDELOLW\LQFRQYHUJHVWRDV1approaches infinity. To derive the bound in (9), we first bound &! from below by w) in the integrand of expression (4). Then, we use Equation (7) on the resulting integral expression. To derive the bound in (10), we bound &! from below by: 1) 1 for negative w values and 2) by w ); for positive w values. We then use Expressions (5) and (8) from the Corollary. Lemma 2 below states a probability of correct detection result for the case where the percentage of signalincluding observations and the signalto noise ratio are both very small. Lemma 2 /HW. !DQG1 > 0. Then, the probability of correct detection in (4) is of order n 1 Proof We brake the integral in (4) into two parts: the part from to 0 and the part from 0 to 1 For the first part, we expand >&!@ (1 .Q via Taylor series H[SDQVLRQWRILUVWRUGHU1DSSUR[LPDWLRQ)RUWKHVHF ond part, we approximate the integral by 1 times the value of the integrand at zero. Then, we approximate 1 rN 1 As a result, we then obtain: We note that, in general, the probability of correct detection induced by the ML optimal detector is of the order >1@ n increasing exponentially to 1; with
PAGE 22
14 increasing signalto noise ratio 1 while it is also decreasing exponentially to 0; with increasing sample size. 2 : < E 5 E = ; rNJÂ£ rl rpJ t : r ; t rEr@S : S ; 4 ? Â£ : S ; rEJrl rpr@S 6 : S ; Â£ : S ; 4 ? KIrLJ (11) The numerical results for equation (4) have been focused on the case when the QXPEHUPRIVLJQDOFRQWDLQLQJREVHUYDWLRQVLVFRQVLGHUHGDVP .Q,QWKHHTXDWLRQwe have considered different signal to noise ratio values, such as 0.5 and 1; for the low SNR range and 4.5 and 7; for the high SNR range. The SNR values have been H[WUDFWHGIURPWKHSUDFWLFDODSSOLFDWLRQLQ>@ZKHUH615 DQGWKHQRLVHSRZHU1 2 is given by 1 ( 5. In this paper we have used the same practical values, keeping the noise power constant and varying the SNR values. to see the significant changes in the Probability of correct detection for different values. The results are exhibited in Figures 1 to 4, representing the performance of the optimal parametric detector in the absence of outliers. In the figures, the probability of correct detection is plotted, as a function of the data size n, for various values of the SHUFHQWDJH.RIVLJQDOFRQWDLQLQJREVHUYDWLRQVDQGYDULRXVVLJQDO to noise ratios. From the plots, the decrease of this probability with increasing data size and GHFUHDVLQJSHUFHQWDJH. is observed.
PAGE 23
15 Figure 1: Shows the 'n' VS 'P d nYDOXHVIRUGLIIHUHQW.YDOXHVIRU615 DQG1 ( 4 for parametric detector in the absence of outliers. (from equation (4)) Figure 2: Shows the 'n' VS 'P d nYDOXHVIRUGLIIHUHQW.YDOXHVIRU615 DQG1 ( 4 for parametric detector in the absence of outliers. (from equation (4)) 20 30 40 50 60 70 80 90 100 110 120 0.4 0.5 0.6 0.7 0.8 0.9 1 D1 = 0.05 D2 = 0.1 D3 = 0.2 D4 = 0.3 20 40 60 80 100 120 140 0.988 0.99 0.992 0.994 0.996 0.998 1 1.002 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3
PAGE 24
16 Figure 3: Shows the 'n' VS 'P d nYDOXHVIRUGLIIHUHQW.YDOXHVIRU615 DQG1 ( 4 for parametric detector in the absence of outliers. (from equation (4)) Figure 4: Shows the 'n' VS 'P d nYDOXHVIRUGLIIHUHQW.YDOXHVIRU615 DQG1 ( 4 for parametric detector in the absence of outliers. (from equation (4)) 20 40 60 80 100 120 140 0 0.02 0.04 0.06 0.08 0.1 0.12 D1 = 0.05 D2 = 0.1 D3 = 0.2 D4 = 0.3 20 40 60 80 100 120 140 0 0.05 0.1 0.15 0.2 0.25 D1 = 0.05 D2 = 0.1 D3 = 0.2 D4 = 0.3
PAGE 25
17 CHAPTER IV THE OUTLIER RESISTANT DETECTOR In this section, we consider the case where extreme occasional outliers may be contaminating the Gaussian environment of Section 3. Then, instead of white and Gaussian, the noise environment is modeled as white with pdf belonging to a class F RIGHQVLW\IXQFWLRQVGHILQHGDVIROORZVIRUVRPHJLYHQYDOXH0LQZKHUH 0 represents the outlier contamination level: F= {f; f=(10I 0 0K f 0 is WKH*DXVVLDQ]HURPHDQDQGVWDQGDUGGHYLDWLRQ1SGI h is any pdf. The outlier resistant robust detector is then found based on the least favorable density f* in class F above, where the KullbackLeibler number between f* and its VKLIWHGE\ORFDWLRQSDUDPHWHUYHUVLRQDWWDLQVWKHLQILPXPDPRQJWKH.XOOEDFN Leibler numbers realized by all pdfs in F [6,7]. As found in [7], the log likelihood UDWLRLQLVDWUXQFDWHGYHUVLRQRIWKDWXVHGLQ6HFWLRQ$VDUHVXOWIRU!WKHML robust detector is operating as follows: (a) Robust ML Detector 1) Given the sequence x 1 ,....,x n compute all [z(x i )@d j d n, where < : T ; rLr] @TrR@ TrF@rErOTrO@ rF@rETrQrF@rE ra (12) @ : srF ; JÂ£rl rF@rE rprEATLJ @ 6 rF 6 t 6 KÂ£rl @ rpKrLs (13)
PAGE 26
18 2) If [z(x k )@d 0 ; for all k, 1d k d n, then, decide that no observation contains signal. 3) If a set of integers {i 1 L m }; 1 d m d Dn: [z(x k )@! ; for all k Â {i 1 L m } and [z(x k )@d 0 ; for all, then decide that the observations containing the signal are all those with indices in the set {i 1 L m }. 4) If a set of integers {i 1 L m }; m > Dn: [z(x k )@! ; for all k Â {i 1 L m } and [z(x k )@d 0 ; for all k Â {i 1 L m }, then decide that the observations containing the signal are all those with indices k are in the set {i 1 L m } and whose [ z(x k )@YDOXHVDUHWKH.QKLJKHVW in the set. We will denote by P r do ({i 1 L m }) the probability of correct detection induced by the robust ML detector, given that the noise is Gaussian containing no outliers and given that the signal occurs at the observation indices {i 1 ,....,i m } Then, we can derive the expressions below, with some extra caution, assuming again that .Q is an integer: 2 : < E 5 E = ; rLÂ£ rl t rprdIdJ 2 : < E 5 E = ; rLJr@S : S ;> Â£ : rFS ;? ?5 ? ? 6 rHrdÂ£rlSrE rprh : 5? ; rEÂ£ rl rF@rE rpÂ£ : 5? ; rl @ rpIrLJ (14) 2 4 Probability of correct detection induced by the robust detector in the absence of outliers. d data/ truncation level per datum. Comparing Expressions (4) and (14), we notice that the robust detector induces lower probability of correct detection at the nominal Gaussian model; for the case of m n where the difference of the two probabilities decreases monotonically
PAGE 27
19 with decreasing contamination level 0 As we will see in the sequel, this loss of performance of the robust detector at the nominal Gaussian model is at the gain of resistance to outliers. Let there exist a small positive value such that the noise per observation is ]HURPHDQ*DXVVLDQZLWKSUREDELOLW\ and is an infinite positive value y; with probability We express below the probabilities P G" ({i 1 L m }) and P r G" ({i 1 L m }) induced by this outlier model and the optimal ML detector in (ii) versus the robust detector, respectively, 2 r :< E 5 E =; rL2 r :< E 5 E =; rL : srF ; ? rHrd : srF ; Â£rl t rprErh Â£ ? rl t rp rrQIrOJ (15) level of contamination 2 r :< E 5 E =; rL : srF ; 5> : 5? ; J rHr@S:S; >: srF ; Â£ : rFS ; rE ? ?5 ? 6 rdÂ£rlSrE rprh : 5? ; rE :srF; : 5? ; IrLJ (16)
PAGE 28
20 2 r : < E 5 E = ; rL : s rF ; 5> : 5? ; Jr@S : S ;>: srF ; Â£ : rFS ; rE ? ?5 ? ? 6 rdÂ£rlS rE rprh : 5? ; rE : srF ; : 5? ; rd : srF ; Â£rl rF@rE rprErh Â£ : 5? ; rl @ rpIrLJ (17) Comparison between Expressions (16) and (17) reveals that the robust detector attains higher probability of correct detection than the detector in Section 3; in the presence of the extreme outliers, where the difference of this performance increases with increasing value. Remarks If it is known that the signal may appear as a set of bursty batches of unknown sizes and protection against data outliers is needed, then, the robust reinitialization sequential algorithm in [9] will sequentially detect the beginning and the ending of ea ch batch with minimal complexity, no memory requirements and with accuracy increasing with the signalto noise ratio and the size of each batch. Let then denote the value of the robust algorithm which detects the beginning of a signal batch, upon the processing of the n th datum xn from its beginning. Let denote the value of the robust algorithm which detects the ending of the batch, upon processing the n th datum n from the beginning of its initialization. The whole algorithmic system operates then as follows, where and 5 are two positive thresholds preselected to satisfy power and false alarm tradeoffs and where z ( x ) is as in (12):
PAGE 29
21 1) Process the observed sequence x 1 ,..,x n sequentially starting with the algorithm { 6 } whose values are updated as follows: 6 4 r 6 >5 I=Trlr6 rE<:T >5 ;rF t rp Stop the first time n such that 6 rR and declare n as the time when the signal batch begins. Then, switch immediately to the algorithm { 9 }whose values are updated as follows, where time zero denotes the time when the algorithm begins and where y n denotes the n th observed datum after the latter beginning: 9 4 r 9 >5 I=T : r9 rF<:U >5 ; rE t Stop the first time n such that 9 4 rR 5 and declare that the signal batch has ended. Numerical evaluations where performed for equations (14), (15), (16) and (17). Regarding expression (14), the performance of the parametric detector in the absence of outliers, four different SNR values, 4.5, 7, 0.5 and 1, were considered. In DGGLWLRQWKH.YDOXHVFRQVLGHUHGZHUHDQG7KHGWUXQFDWLRQYDOXHLQWKHHTXDWLRQKDVEHHQFDOFXODWHGIURPHTXDWLRQIRU0 7KHUHVXOWVDUHexhibited in Figures 5, 6, 7 and 8, where the effect of increasing data set size, SNR and decreasing percentage of signal containing observations on performance decrease is again observed.
PAGE 30
22 Figure 5: Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG 1 ( 5 for robust detector in the absence of outliers. (from equation (14)) Figure 6: Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG 1 ( 5 for robust detector in the absence of outliers. (from equation (14)) 20 30 40 50 60 70 80 90 100 110 120 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3 20 30 40 50 60 70 80 90 100 110 120 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3
PAGE 31
23 Figure 7: Shows the 'n' VS 'P d graph IRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG 1 ( 5 for robust detector in the absence of outliers. (from equation (14)) Figure 8: Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG 1 ( 5 for robust detector in the absence of outliers. (from equation (14)) 20 30 40 50 60 70 80 90 100 110 120 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3 20 30 40 50 60 70 80 90 100 110 120 0 0.05 0.1 0.15 0.2 0.25 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3
PAGE 32
24 Equation (16) provides the correct detection performance of the parametric detector in the presence of outliers and its quantitative behavior is exhibited in Figures 9, 10, 11 and 12. The graphs in the figures are again plotted for four different SNR YDOXHVDQGIRU1 ( DQGIRU. values 0.05, 0.1, 0.2 and 0.3. From the latter figures, we observe the faster performance decline with increasing sample size, as compared to the same performance in the absence of outliers. We also observe that the effect of FKDQJLQJSHUFHQWDJH. on performance is profoundly reduced. Equation (17) represents the performance of the robust detector, in the presence of outliers. Numerical results from expression (17) are exhibited in Figures 13 to 16. The graphs in the figures are again plotted for four different SNR values, 4.5, 7, 0 DQGZKHQ1 ( DQGIRU.YDOXHVDQG&RPSDULQJ Figures 9 to 12 (referring to the parametric detector) to Figures 13 to 16, we note that, as expected, in the presence of outliers the performance of the robust detector is superior and declines significantly slower than that of the parametric detector, when WKHVDPSOHVL]HLQFUHDVHV,QDGGLWLRQWKHHIIHFWRIFKDQJLQJSHUFHQWDJH.RQperformance is much more pronounced in the robust detector and so is the effect of signalto noise ratio.
PAGE 33
25 Figure 9: Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG 1 ( 5 for parametric detector in the presence of outliers. (from equation (16)) Figure 10: Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH61 R= 7 and 1 ( 5 for parametric detector in the presence of outliers. (from equation (16)) 0 20 40 60 80 100 120 140 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3 0 50 100 150 200 250 300 350 400 450 500 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3
PAGE 34
26 Figure 11: Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG 1 ( 5 for parametric detector in the presence of outliers. (from equation (16)) Figure 12: Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG 1 ( 5 for parametric detector in the presence of outliers. (from equation (16)) 0 20 40 60 80 100 120 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2 D1 = 0.05 D2 = 0.1 D3 = 0.2 D4 = 0.3 0 20 40 60 80 100 120 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3
PAGE 35
27 Figure 13: Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 and 1 ( 5 for robust detector in the presence of outliers. (from equation (17)) Figure 14: Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG 1 ( 5 for robust detector in the presence of outliers. (from equation (17)) 20 40 60 80 100 120 140 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3 0 20 40 60 80 100 120 140 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3
PAGE 36
28 Figure 15: Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG 1 ( 5 for robust detector in the presence of outliers. (from equation (17)) Figure 16: Shows the 'n' VS 'P d nJUDSKIRUGLIIHUHQW.YDOXHVZKHQWKH615 DQG 1 ( 5 for robust detector in the presence of outliers. (from equation (17)) 0 20 40 60 80 100 120 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3 0 20 40 60 80 100 120 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 D1 = 0.05 D2 = 0.1 D3 = 0.2 D4 = 0.3
PAGE 37
29 In this section, we evaluated the performance of the parametric and robust detectors, in both the presence and the absence of outliers. We observed the quantitative reduction in the performance of the parametric detector, when outliers are present. We also observed the quantitative performance superiority of the robust detector in the presence of outliers, at the expense of reduced performance in the absence of outliers. The latter performance tradeoff is controlled by the value of the design parameter 0
PAGE 38
30 CHAPTER V SUBOPTIMAL TREE SEARCH DETECTORS In this section, we consider the special case where the .Q components of the sparse signal are spread relatively evenly across the n members of the observation set. Then, we wish to devise a detector whose objective is to identify the presence of isolated signal including observations within clusters of signalabsent observations. In this case, we may draw from the information theoretic concepts of noiseless source coding to devise treesearchtype detectors for sparse signals, as was done for the transmission/probing of bursty signals [3,4]. In particular, referring to the notation and model in Section 2, where f 1 (.) and f 0 (.) are the pdfs of signalincluding versus signalabsent observations, respectively and where Â‰:Âš; HKC : Bs:Âš;BK:Âš; ; we define a treesearch detector as follows, considering for simplicity in notation that the size of the observation set is a power of 2: (a) Given the sequence x 1 [ N compute all g(x j ) ; 1 d j d N = 2 n (b) 8WLOL]HDVHTXHQFH^ k } of given algorithmic constants as: (i) If Â¦ d N 1k n k ) (x g then, decide that at most a single signal component is contained in the sequence x 1 [ N and stop (ii) If Â¦ N 1k n k ) (x g then, create the two partial sums Â¦ 2 N 1k k ) (x g and Â¦ 2 N 1k k ) (x g
PAGE 39
31 LLL7HVWHDFKRIWKHWZRVXPVLQLLDJDLQVWWKHFRQVWDQW n1 and go back to steps (i) and (ii). (c) In general, the observation set x 1 [ N is sequentially subdivided in powers of 2 number of portions, until the subdivision stops. If, during the algorithmic process, the observations with indices {i 1 L m }; m = 2 l are tested, then, (i) If Â¦ d m 1k i ) (x g k l then, decide that at most a single signal component is contained in the sequence x 1 [ N and stop (ii) If Â¦ m 1k i ) (x g k l then, create the two partial sums Â¦ 2 m 1k i ) (x g k and Â¦ m 1 2 m k i ) (x g k LLL7HVWHDFKRIWKHWZRVXPVLQLLDJDLQVWWKHFRQVWDQW l 1 and go back to steps (i) and (ii). For m signalcontaining observations within a total of N observations, the complexity of the treesearch detector is of order [logm]N. Focusing on the constant signal and additive, zero mean, white Gaussian noise model in (ii), where the function g(x) in the description of the tree search detector equals x WKH/HPPDEHORZ was proven in [3]. When the signal including observations are uniformly distributed across all observations, the operational complexity of the tree search detector is of order [log m ] N ; where m is the number of signalincluding components and N is the size of
PAGE 40
32 the observation set. The error performance of the treesearch detector may be studied for general pdfs, asymptotically: that is when the observation set is asymptotically large and each signalincluding observation component is isolated in the middle of an asymptotically large population of signalabsent observations. Then, the central limit theorem provides probability of correct detection expressions which are functions of the Kullback Leibler numbers between the pdfs f 1(.) and f 0(.). However, in this section, we will focus on the constant signal and additive Gaussian noise model of Section 3, where the function g ( x ) in the description of the treesearch detector equals x /2 In the latter case, we express the induced probabilities of correct detection in Lemma 3, below Lemma 3 Let a constant signal be additively embedded in white zero mean Gaussian QRLVHZLWKVWDQGDUGGHYLDWLRQ1/HW m =2 l be the number of signal components, given that they are spread uniformly across a total of N = 2 n observations, where n > l Let the constants { N } used by the tree search detector be such that: N < 2 N 1; for all 2 Â” k Â” n Then, the probability, Pd ( l n ), of correct detection induced by the treesearch detector is given by the following expression, where this probability is conditioned on the above uniform signal spreading assumption. 2 : HJ ; rLHÂ£ : ? ; rkÂ£ : ? ; rFÂ£ : @ ; rorFr@T : T ; Â£ :@ rE? rFT;I 6 7; nÂ•Q l Â• (18)
PAGE 41
33 2 : rJ ; rLÂ£ : ? 4 ; where, ? H ? rE:t ??5 rFs; 6 6 I t ? ? 6 (19) @ H ?>5 rF ? rE:t ??5 rFs; 6 6 I t ? ? 6 (20) Proof For the proof, we consider that a single signal component per 2 n l observations is present. Then, we express P d ( l n ) as the probability that two independent sums of such 2 n l observations are each smaller than n l while their sum is larger than n l +1 It is relatively easy to conclude that the probability of correct decision in (18) is increasing with increasing signalto noise ratio / 1 as well as with increasing difference n l It is also relatively simple to conclude that the n l and n l +1 values should be of 2 ( n l ) order; for asymptotically large values of the difference n l. We may select the specific values of the constants n l and n l +1 based on a maximization of correct detection criterion, as stated in Lemma 4 below. Lemma 4 Let a constant signal be additively embedded in white zero mean Gaussian noise with standard deviation 1 /HWWKHVLJQDORFFXUZLWKSUREDELOLW\ q per observation, independently across all N = 2 n observations. Let P d ( n l q ) denote then the probability of correctly deciding between at most one and at least two signal
PAGE 42
34 components in 2 n l observations, via the use of the treesearch constant n l The constant n l may be selected as that which maximizes the probability P d ( n l q ), where the latter is given by the following expression. 2 : JrFHM ; rL : srFM ; 6 7 Â£ : ? 4 ; rEt ? M : srFM ; 6 7 ?5 Â£ : ? 5 ; rErrl t ? G rpM : srFM ; 6 7 ? Â£:rF? ; 6 7 @6 (21) where, ? ? rE:t ??5 rFG; ? (22) ? ? t ? 6 (23) ? t ? 6 (24) For signalto QRLVHUDWLR1DV\PSWRWLFDOO\VPDOOIRU n l Â•DQGWKH q< 2 7 7constant n l is given by Equation (25) below, where it can be then shown that n l +1 < 2 n l ? rLresrE tM>srFt : srFM ; 6 7 ?5 ? rFsrEt:srFM; 6 7 rEt ?>5 M:srFM; 6 7 ?5 ri ?5 (25)
PAGE 43
35 Proof ([SUHVVLRQLVGHULYHGLQDVWUDLJKWIRUZDUGIDVKLRQ:KHQ1LV asymptotically small, we use first order Taylor expansion approximations with respect WRWKH n l GHILQHGLQRIWKHIXQFWLRQVLQ6XEVHTXHQWO\ZH find the PD[LPL]LQJ n l (defined in (23)) value of the resulting expression, as given by (25). :HQRWHWKDWZHPD\UREXVWLI\WKHWUHH search detector at the Gaussian nominal model, by using, instead, g ( x ) = z ( x ) /2; for z ( x ) as in (12). The error performance of the robust treesearch detector may be then studied asymptotically. Regarding the Treesearch method, equations (18) and (21) have been numerically evaluated, where equations (19), (20), (22), (23), (24) and (25) have been used in the process.. :HLQLWLDOO\FRPSXWHGWKHWKUHVKROGYDOXHV^ k } from equation (25), assuring that they satisfy the condition k k1 The quantities c nlk nl and nl calculated from expressions (22) to (24), were used to compute the probability of correct detection in (21). The signalto noise ratio values were selected using the condition that the square of the SNR value, 1 2 should be above nl [2 nl1 1] 1 ; the latter condition guarantees that the expression in (18) is monotonically increasing with increasing SNR. The specific SNR considered in that range were: 3, 5 and 7. The results are plotted in Figures 17 and 18 for q=0.01 and 0.05, respectively. The results from expression (18) are also used later for a specific signaloccurence model. We first evaluated the a posteriori probability of correct in equation (26). detection P d (n l ,q) in expression (10). We subsequently evaluated the probability of correct detection P d (n, q), when a signal per observation is present with probability q, the signal is a constant > 0 embedded in white Gaussian noise, the signalspreading of Lemma 2 holds and the tree search is performed. For P d ( l, n) as in (18), the
PAGE 44
36 probability P d (n, q) is given by the following expression, whose value decreases with decreasing Bernoulli parameter q: 2 : JM ; rLrert :?;6 M 6 : srFM ; 6 ?6 ?6 @4 ri ?5 r2 : HJ ; :BNKI : sz ; ; ?6 @4 t :?;6 M 6 : s rFM ; 6 ?6 (26) Figures 17 and 18 exhibit the behavior of the probability P d (n q) of correct detection in (26), as induced by the treesearch detector at various signalto noise ratios, for q = 0.01 and q = 0.05, respectively. In the figures, the horizontal axis depicts the changing n values; the signalto noise ratios (SNRs) selected are within the range (in Lemma 2) guaranteeing monotone increase of the probability in (18 ) with increasing SNR. From these figures, we observe the profound performance reduction, when the Bernoulli parameter q decreases from 0.05 to 0.01; we also observe the significant impact of the signalto noise ratio on the P d (n, q) performance. The results are calculated for different SNR values, when q=0.01 and 0.05. The results for the above expression (26) are exhibited in Figures 17 and 18 below.
PAGE 45
37 Figure 17: The probability of correct detection P d (n, q) in (26) for the treesearch detector, as function of n, for q = 0.01(from equation (26)) Figure 18: The probability of correct detection P d (n, q) in (26) for the treesearch detector, as function of n, for q = 0.01 (from equation (26)) 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 \SNR = 3 \SNR = 5 \SNR = 7 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 \SNR = 3 \SNR = 5 \SNR = 7
PAGE 46
38 CHAPTER VI THE BERNOULLI SIGNALPRESENCE MODEL In this section, we consider the model of constant signal > 0 embedded in additive zero mean white Gaussian noi VHZLWKVWDQGDUGGHYLDWLRQSHUVDPSOH1:H select values of the various parameters involved and crossevaluate probabilities of correct detection, as induced by the detectors summarized in Section 3 and 4. For the parametric optimal detector in Section 3 and the robust detector in Section 4, we VHOHFWLQDGGLWLRQD%HUQRXOOLPRGHOIRUVLJQDOJHQHUDWLRQDVIROORZV*LYHQQDQG.the signal > 0 occurs per observation with probability p, given by the expression below, where q is a constant in (0, 0.5) which is closer to 0 for sparse signals: LrL M @ J I AM : srFM ; ? @4 (27) We then denote by P d P r d 0 P G and P r G then a posteriori probabilities of correct detection relating to the conditional probabilities of correct detection in (4), (14), (16) and (17), respectively, where the signal occurrence model in (27) is adopted. We can H[SUHVVWKHVHDSRVWHULRULSUREDELOLWLHVDVIROORZVDVVXPLQJ.QLQWHJHU 2 rLÂ£rl t rp N @ J I AM : srFM ; ? ?5@4 @ J I AM : srFM ; ? @4 O rEN @ Â =Â AM : srFM ; ? @ J I AM : srFM ; ? @4 O2 : < E 5 E = ; :BNKI:v;; (28)
PAGE 47
39 2 4 rLÂ£rl t rp N @ J I AM : srFM ; ? ?5@4 @ J I AM : srFM ; ? @4 O rEN @ J J AM : srFM ; ? @ J I AM : srFM ; ? @4 O2 4 : < E 5 E = ; :BNKI: sv ;; (29) 2 rL2 : < E 5 E = ; :BNKI: sw ;;N @ J I AM : srFM ; ? ?5@4 @ J I AM : srFM ; ? @4 O rE2 : < E 5 E = ; :BNKI: sx ;;N @ J J AM : srFM ; ? @ J I AM : srFM ; ? ?5@4 O (30) 2 rL2 : < E 5 E = ; :BNKI: sw ;;N @ J I AM : srFM ; ? ?5@4 @ J I AM : srFM ; ? @4 O rE2 : < E 5 E = ; :BNKI: sy ;;N @ J J AM : srFM ; ? @ J I AM : srFM ; ? ?5@4 O (31) For the parametric and robust detectors, we numerically evaluated the a posteriori probabilities in (28), (29), (30) and (31). Equation (28) provides the performance of the parametric detector in the absence of outliers, for the Bernoulli signaloccurrence model. In its calculation, the results from equation (4) were used. Equation (29) provides the probability of correct detection for the robust detector in
PAGE 48
40 the absence of outliers for the Bernoulli signaloccurrence model. The results from equation (14) were used in this case. Equation (30) provides the performance of the parametric detector in the presence of outliers and the Bernoulli signaloccurrence model. The results from equation (15) and (16) were used in the latter case. Equation (31) provides the probability of correct detection for robust detector in the presence of outliers and the Bernoulli signaloccurrence model; the results from equation (15) were used here. The results from the parametric and the robust detectors, in the absence of outliers, have been compared, for the SNR values 4.5, 7, 0.5 and 1, and for the .YDOXHV 5, 0.1, 0.2 and 0.3 These values are plotted when q=0.05 and 0 Similarly, the parametric and the robust detectors were compared in the presence of outliers 1 ( 4 q = 0.05 for the parametric and robust detectors; 0.05, 0.1, 0.2 and 0.3 for tree search detector 0 1 IRUWKHSDUDPHWULFDQGUREXVWGHWHFWRUVDQGIRU treesearch detector Results from our numerical comparisons between the parametric and the robust detectors are exhibited in Figures 19 to 24. From Figures 19 to 24, we observe the quantitative performance superiority of the robust detector in the presence of outliers, as compared to that of the parametric detector. The later performance superiority occurs at the expense of reduced performance, when outliers are absent. A satisfactory performance tradeoff, in the absence versus the presence of outliers, may be attained by the robust detector whose
PAGE 49
41 GHVLJQSDUDPHWHU0WDNHVDVPDOOYDOXH$VYLHZHGIURP)LJXUHVDQGIRUH[DPSOHWKHUREXVWGHWHFWRUGHVLJQHGIRURXWOLHUSUREDELOLW\0 RXWSHUIRUPVsignificantly the parametric detector when the actual RXWOLHUSUREDELOLW\LV From Figures 19 to 24, we also observe the quantitative performance increase, for both the parametric and the robust detectors, as the signalto noise ratio and the DVVXPHGLQWKHGHWHFWRUGHVLJQSHUFHQWDJH.RIVLJQDO containing observations increase (in contrast to the actual percentage represented by the Bernoulli parameter q). In all cases, performance decreases exponentially with the number of observations, for sufficiently large sample sizes. The results are exhibited in Figures 19 to 24 below: Parametric Detector xaxis: Number of observations Robust Detector yaxis: P d value Figure 19: Shows the comparison between the parametric and the robust in the absence of outliers, probabilities in DQGIRUT DQG615 ZKHQ0 0.05. (from equation (28)&(29)) 20 30 40 50 60 70 80 90 100 110 120 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 1.05 D1 = 0.05 D2 = 0.1 D3 = 0.2 D4 = 0.3
PAGE 50
42 Parametric Detector xaxis: Number of observations Robust Detector yaxis: P d value Figure 20: Shows the comparison between the parametric and robust detector model in the absence of outliers, probabilities in (19) and (20), for q = 0.05 and SNR= 0.5, ZKHQ0 (from equation (28)&(29)) 20 30 40 50 60 70 80 90 100 110 120 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 x 103 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3
PAGE 51
43 Parametric Detector xaxis: Number of observations Robust Detector yaxis: P d value Figure 21: Shows the comparison between parametric and robust detector in the presence of outliers, probabilities in (21) and (22), for q = 0.05 and SNR=7, when DQG0 (from equation (30)&(31)) 20 40 60 80 100 120 140 0 0.1 0.2 0.3 0.4 0.5 D1 = 0.05 D2 = 0.1 D3 = 0.2 D4 = 0.3
PAGE 52
44 Parametric Detector xaxis: Number of observations Robust Detector yaxis: P d value Figure 22: Shows the comparison between parametric and robust detector in the presence of outliers, probabilities in (21) and (22), for q = 0.05 and SNR= 0.5,when DQG0 (from equation (30)&(31)) 20 30 40 50 60 70 80 90 100 110 120 0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045 0.05 D1 = 0.05 D2 = 0.1 D3 = 0.2 D4 = 0.3
PAGE 53
45 Parametric Detector xaxis: Number of observations Robust Detector yaxis: P d value Figure 23: Shows the comparison between parametric and robust detector in the presence of outliers, probabilities in (21) and (22), for q = 0.05 and SNR=7, when and 0 (from equation (30)&(31)) 20 30 40 50 60 70 80 90 100 110 120 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3
PAGE 54
46 Parametric Detector xaxis: Number of observations Robust Detector yaxis: P d value Figure 24: Shows the comparison between parametric and robust detector in the presence of outliers, probabilities in (21) and (22), for q = 0.05 and SNR=0.5, when DQG0 (from equation (30)&(31)) 20 40 60 80 100 120 140 0 0.001 0.002 0.003 0.004 0.005 0.006 0.007 0.008 0.009 D 1 = 0.05 D 2 = 0.1 D 3 = 0.2 D 4 = 0.3
PAGE 55
47 CHAPTER VII DISCUSSION AND CONCLUSION In this, we investigate the problem of detecting sparse signals that are embedded in noise. The effective solution of the problem requires clear modeling of any a priori knowledge available to the designer. We first present and analyze the problem solution when only the highest percentage of signalincluding observations is a priori known. In the latter case, we consider the special case of a constant signal embedded in additive white Gaussian noise and presented both parametric and outlier resistant solutions. Secondly, we present an efficient solution to the problem when it is a priori known that the signal occurs in bursty batches. Finally, we present a treesearch solution approach for the case when the sparse signal is known to be uniformly distributed within the observations set. We analyze all our approaches in terms of probability of correct detection performance and complexity. We considered the case where a constant signal is sparsely generated by a Bernoulli variable and is subsequently embedded in additive Gaussian white noise. We then evaluated the performance of three sparse signal detectors parametrically optimal, robust and treesearch in terms of the probability of correct detection they induce. The parametrically optimal and robust detectors were designed based on an assumed known maximum percentage of signal containing observations, while the treesearch detector has been addressing an assumed uniform signal spreading across all observations without any a priori knowledge of percentages regarding signal containing observations. The parametrically optimal detector has been designed around the assumption that no data outliers may ever occur, while the robust detector VGHVLJQLQFRUSRUDWHVDQDVVXPHGPD[LPXPSHUFHQWDJHRIGDWDRXWOLHUV$OO three detectors have been evaluated for the same value 0.05 of the signalgenerating
PAGE 56
48 Bernoulli parameter, while the treesearch detector has also been evaluated for the Bernoulli parameter value 0.01. The performed evaluations have led to the following general qualitative conclusions: (a) As the spreading of the sparse signals increases, so does the difficulty of their localization, where such difficulty decreases with increasing signalto noise ratio; (b) The highest the assumed percentage of signal containing observations in the design of the parametrically optimal and the robust detectors, the better their performance, in both the presence and the absence of outliers; (c) In the presence of outlier data, the robust detector may significantly outperform the parametrically optimal detector at the expense of relative insignificant performance reduction in the absence of outlier data.
PAGE 57
49 REFERENCES >@(&DQGHV5RPEHUJDQG77DR5REXVW8QFHUWDLQW\3ULQFLSOHV([DFW6LJQDO5HFRQVWUXFWLRQIURP+LJKO\,QFRPSOHWH)UHTXHQF\,QIRUPDWLRQ IEEE Trans. Inform. Theory, Vol. 52, No.2, pp. 489509, Feb.2006. >@$7URSSDQG$&*LOEHUW6LJQDO5HFRYHU\IURP5DQGRP0HDVXUHPHQWVYLD2UWKRJRQDO0DWFKLQJ3XUVXLW IEEE Trans. Inf. Theory, Vol.53, No.2, pp. 46554666, Dec. 2007. [3] J. F. Hayes, $Q$GDSWLYH7HFKQLTXHIRU/RFDO'LVWULEXWLRQ IEEE Trans. Commun ., vol. COM26, pp. 11781 186, Aug. 1978. [3] A.T. Burrell and P. Papantoni.D]DNRV3DUDPHWULFDOO\2SWLPDO5REXVWDQG Tree6HDUFK'HWHFWLRQRI6SDUVH6LJQDOV Journal of Signal and Information Processing (JSIP), 2013, 4, 336342 doi:10.4236/jsip.2013.43042 Published Online August 2013 (http://www.scirp.org/journal/jsip) [4] D. Kazakos and P. Papantoni Kazakos, Detection and Estimation, Computer Science Press, 1990, ISBN 0716781816. >@3+XEHU$5REXVW9HUVLRQRIWKH3UREDELOLW\5DWLR7HVW Ann. Math. Statist., Vol. 36, pp. 17531758., 1965. [6] A. T. Burrell and P. Papantoni.D]DNRV5DQGRP$FFHVV$OJRULWKPVLQ3DFNHW 1HWZRUNV$5HYLHZRI7KUHH5HVHDUFK'HFDGHV International Journal of Communications Network and System Sciences ( IJCNS ), Vol. 5, No. 10, 2012, pp. 691707. doi:10.4236/ijcns.2012.510072 [7] A. T. Burrell and P. Papantoni.D]DNRV([WHQGHG6HTXHQWLDO$OJRULWKPVIRU 'HWHFWLQJ&KDQJHVLQ$FWLQJ6WRFKDVWLF3URFHVVHV IEEE Transactions on Systems Man and Cybernetics Vol. 28, No. 5, 1998, pp. 703710. doi:10.1109/3468.709621 [8] A. T. Burrell and P. Papantoni.D]DNRV5REXVW6HTXHQWLDO$OJRULWKPVIRUWKH 'HWHFWLRQRI&KDQJHVLQ'DWD*HQHUDWLQJ3URFHVVHV Journal of Intelligent and Robotic Systems Vol. 60, No. 1, 2010, pp. 317. [9] Emmanuel Candes, Justin Romberg, and Terence Tao, "Stable Signal Recovery from Incomplete and Inaccurate Measurements, Applied and Computational Mathematics June, 2005. [10] Ke Huang and Selin Aviyente Sparse Representation for Signal Classification [11] Marco F. Duarte, Mark A. Davenport, Michael B. Wakin, and Richard G. Baraniuk "Sparse Signal Detection From Incoherent Projections" Proc. Int. Conf. Acoustics, Speech, Signal Processing ICASSP, May 2006.
PAGE 58
50 APPENDIX The above code is used for evaluating expression (4) in section 3 which is gives the output for parametric detector in the absence of outliers. The results of expression (4) are exhibited in Figure 1 to 4. %Section3 equation 4 %Sinduja Seethapathy function y=sinduja(x) alpha =0.2; n = 140; m = ceil(alpha.*n); sigma = 5e4; SNR = 1; t = SNR/2; sphi = (exp(x.^2./2))./(sqrt(2*pi)); cphi = 0.5+0.5.*erf(x./sqrt(2)); cphi2 = 0.5+0.5.*erf((x+SNR)./sqrt(2)); y = m.*sphi.*cphi.^(alpha.*n1).*cphi2.^((1alpha).*n); end %section 4 equation 14 %Sinduja Seethapathy function z=sinduja14(x) SNR= 1; sigma= 5e4; %ci= 0.2; n= 140; alpha= 0.1; d=0.009; m= ceil(alpha.*n); Y= d./sigma; sphi= exp(x.^2./2)./(sqrt(2*pi)); cphi1= (0.5+0.5*erf((x)./sqrt(2))).^(m1); cphi2= (0.5+0.5*erf((x+SNR)./sqrt(2))).^(nm); cphi3= (0.5+0.5*erf((Y+SNR)./sqrt(2))).^(m); cphi4= (0.5+0.5*erf((Y)./sqrt(2))).^(nm); cons= cphi3.*cphi4 z= alpha.*n.*sphi.*cphi1.*cphi2;
PAGE 59
51 The above code is used for evaluating expression (14) in section 4 which is gives the output for robust detector in the absence of outliers. The results of expression (14) are exhibited in Figure 5 to 8. The above code is used for evaluating expression (16) in section 4 which is gives the output for parametric detector in the absence of outliers. The results of expression (16) are exhibited in Figure 9 to 12. %section 4 equation 16 %Sinduja Seethapathy function z=sinduja4(x) ci= 0.1; alpha= 0.3; n= 140; m=ceil(alpha.*n); SNR= 0.5; sigma= 5e4; sphi= exp(x.^2./2)./(sqrt(2*pi)); cphi1= 0.5+0.5*erf(x./sqrt(2)); cphi2= 0.5+0.5*erf((x+SNR)./sqrt(2)); cons= ((ci.^(alpha.*n)).*(1ci).^((1alpha).*n)) z= ((1 ci).^(1+(1alpha).*n)).*alpha.*n.*(sphi.*(((1ci).*cphi1+ci).^(alpha.*n1))); %+((ci.^(alpha.*n))).*(1ci).^((1alpha).*n)) end %section 4 equation 17 %Sinduja Seethapathy function z=sinduja417(x) ci= 0.1; alpha= 0.3; n= 140; m=ceil(alpha.*n); SNR= 0.5; sigma= 5e4; d=0.009; teetha= 0.002475; Y=d./teetha; sphi= exp(x.^2./2)./(sqrt(2*pi)); cphi1= 0.5+0.5*erf(x./sqrt(2)); cphi2= 0.5+0.5*erf((x+SNR)./sqrt(2)); cphi3=0.5+0.5*erf((Y+SNR)./sqrt(2));
PAGE 60
52 The above code is used for evaluating expression (17) in section 4 which is gives the output for parametric detector in the absence of outliers. The results of expression (17) are exhibited in Figure 13 to 16. The above code is used for evaluating expression (13) in section 4 which is gives the 'd' value which is the data/ truncation level per datum used for the robust detector. %syms teetha sigma d eps clear; d=[0.00600:0.000001:.01237]; sigma= 5e4; SNR= 9; teetha= SNR.*sigma; eps= 0.05; %solve('((0.5+0.5*erf(((d+teetha)/sigma)/sqrt(2)))+((exp((teetha*d/(sigma)^2)(teetha^2/2*sigma^2))*(0.5+0.5*erf((d/sigma)/sqrt(2)))))==(1/(1eps))',d) cphi1= 0.5+0.5*erf(((d+teetha)./sigma)./sqrt(2)); cphi2= 0.5+0.5*erf((d./sigma)./sqrt(2)); e1= exp((teetha.*d./sigma.^2)(teetha.^2./(2.*sigma^2))); %e2=exp((teetha.*d./sigma.^2)(teetha.^2./(2.*sigma^2))) %solve((cphi1+e1.*cphi2)==(1./(1eps)), d);? expression=(1eps).*(cphi1+e1.*cphi2)1; cphi4= 0.5+0.5*erf((Y)./sqrt(2)); cons= (1ci).^((1alpha).*n).*(((1ci).*cphi3+ci).^m).*(cphi4.^((1alpha).*n)) z= ((1ci).^(1+(1alpha).*n)).*alpha.*n.*(sphi.*(((1ci).*cphi1+ci).^(alpha.*n1))).*((cphi2).^((1alpha).*n)); end
PAGE 61
53 The above code is used for evaluating expression (15) in section 4 which is used in the evaluation of the expressions (16) and (17). %section 3 ens 15 %Sinduja Seethapathy SNR= 1; sigma= 5e4; ci= 0.1; n=200; alpha= 0.3; m= ceil(alpha.*n); cphi1= 0.5+0.5*erf((SNR./2)./sqrt(2)); cphi2= (0.5+0.5*erf((SNR./2)./sqrt(2))).^(nm); Pd15= (1ci).^(nm).*((1ci).*cphi1+ci).^m.*cphi2 %Beta values q=0.01; n=10; l=7; betaN= 2.*((1q).^(2.^(nl) 1))1; betaD= 4.*(2.^(nl1)1)+(2.*q1); beta= 2.*betaN/betaD beta1N= 2.*((1q).^(2.^(nl+1)1))1; beta1D= 4.*(2.^(nl) 1)+(2.*q1); beta1= 2.*beta1N/beta1D NR= 2.*q.*(1(2.*((1q).^(2.^(nl) 1)))); DR= 1+(2.*((1q).^(2.^(nl))))+((2.^(nl+1)).*q.*((1q).^(2.^(nl) 1))); beta= (1+(NR./DR)).^(1); lambda= (beta.*sigma)./(teetha.*(2.^((nl)./2))); mu= teetha./(sigma.*(2.^((nl)./2))); Cnl0= lambda+((2.^(nl1))0).*mu; Cnl1= lambda+((2.^(nl1))1).*mu; cphi1= 0.5+0.5*erf(Cnl0./sqrt(2)); cphi2= 0.5+0.5*erf(Cnl1./sqrt(2));
PAGE 62
54 The above code is used to calculate the beta values in expression (25) of the treesearch detector. %section 5 %Sinduja Seethapathy sigma= 5e4; q=0.01; n= 7; SNR= 1; teetha=SNR.*sigma; l= 0; % betaN= 2.*((1q).^(2.^(nl) 1))1; % betaD= 4.*(2.^(nl1) 1)+(2.*q1); % beta= 2.*betaN/betaD; cons= (1q).^(2.^(nl)).*cphi1 + 2.^(nl).*q.*(1q).^((2.^(nl))1).*cphi2; z= c.*cphi3; Pd= cons+z q=0.05; n=2; l=n2; k=nl; Pd1=(8.2E4).^(2.^(nk1)); for l=0:n2 cons= (2.^((nl).*(2.^l))).*(q.^(2.^l)).*((1q).^(2.^n2.^l)); c= cons.^(1); end for l=0:n2 cons1= Pd1.*(2.^((nl).*(2.^l))).*(q.^(2.^l)).*((1q).^(2.^n2.^l)); cN= factorial(2.^(nl)); cphi3=0; c=0; for k= 2:(2^(nl)) cD1= factorial(k); cD2= factorial((2.^(nl))k); po= (2.^(nl))k; c= (cN./(cD1.*cD2)).*q.^k.*((1q).^po); Cnlk= lambda+((2.^(nl1))k).*mu; cphi3= 0.5+0.5*erf(Cnlk./sqrt(2))+cphi3; end
PAGE 63
55 The above code is used for evaluating expression (26) in section 5 for the treesearch detector. The results of the expression are exhibited in figures 17 and 18. end Pd2= c.*cons1; Pd3=(4.16E13).^(2.^(nk1)); for l=0:n2 cons= (2.^((nl).*(2.^l))).*(q.^(2.^l)).*((1q).^(2.^n2.^l)); c= cons.^(1); end for l=0:n2 cons1= Pd1.*(2.^((nl).*(2.^l))).*(q.^(2.^l)).*((1q).^(2.^n2.^l)); end Pd4= c.*cons1; Pd5=(1.3E33).^(2.^(nk1)); for l=0:n2 cons= (2.^((nl).*(2.^l))).*(q.^(2.^l)).*((1q).^(2.^n2.^l)); c= cons.^(1); end for l=0:n2 cons1= Pd1.*(2.^((nl).*(2.^l))).*(q.^(2.^l)).*((1q).^(2.^n2.^l)); end Pd6= c.*cons1; Pd= Pd2+Pd4+Pd6+Pd8
