Nonuniform sampling walls in wideband signal detection

Nonuniform Sampling Walls in Wideband Signal Detection Josep Font-Segura, Student Member, IEEE, Gregori Vazquez, Senior Member, IEEE, and Jaume Riba, Senior Member, IEEE, Abstract—This work shows the existence of sampling walls in detection of wideband signals from Bernoulli nonuniform sampling (BNS) in the presence of noise uncertainty. A sampling wall is defined as the sampling density below which the target error probabilities, i.e., the missed detection and false alarm probabilities, cannot be guaranteed at a given signal to noise ratio (SNR) regardless the number of acquired samples. The BNS is adopted because it exhibits good tradeoff properties between complexity and performance. It is shown that BNS suffers from noise enhancement, which translates into a whitening effect in the correlation of the legacy signal. Contrarily to the existing literature, the signal detection problem is addressed without having to reconstruct neither the signal nor its spectrum. More specifically, the optimal low SNR detector is formulated as a generalized likelihood ratio test (GLRT) to exploit the available side information of the problem, i.e., the noise variance, the sampling density and the legacy signal autocorrelation. By deriving the asymptotic performance of the GLRT in the presence of noise uncertainty, explicit expressions for sampling walls are obtained as a function of the legacy signal occupancy, the SNR and the noise uncertainty. Further, numerical results are provided to assess the behavior of the sampling walls and signal detection performance. Index Terms—Bernoulli nonuniform sampling, GLRT, sampling walls, SNR walls, cognitive radio. I. INTRODUCTION WIDEBAND signal detection plays a central role in a wide range of wireless communication problems [1] and has been recently identified as one of the most challenging problems in the proliferation of the cognitive radio technology [2]. Cognitive radio has been motivated by the tremendous growth of data rates in wireless devices combined with the foreseeable spectrum occupancy problem [3]. In order to allow opportunistic communication, the unlicensed users must reliably detect the presence of the legacy users to avoid harmful interference in a broad range of frequencies [4]. The challenges identified in wideband signal detection are twofaced. Firstly, it is recognized that wideband regimes are asymptotically characterized by low signal-to-noise ratios (SNRs) [5]. Copyright (c) 2013 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to [email protected]. J. Font-Segura, G. Vazquez and J. Riba are within the Signal Theory and Communications Department of the Technical University of Catalonia (UPC), Jordi Girona 1-3, Campus Nord D5-{214, 204, 116}, 08034 Barcelona, Spain, {josep.font-segura, gregori.vazquez, jaume.riba}@upc.edu. This work has been partially funded by the Spanish Government under TEC2010-21245-C02-01 (DYNACS), CONSOLIDER INGENIO CSD2008- 00010 (COMONSENS), CENIT CEN-20101019 (THOFU), and the Catalan Government (DURSI) under Grant 2009SGR1236 and Fellowship FI-2010. Signal detection in the low SNR regime has received recent attention in the form of signal detectors exploiting the signal autocorrelation properties or spectrum properties of the legacy signal [6]–[9]. This is not surprising, as the second order statistic usually is the sufficient statistic in the low SNR regime [10]. A natural approach to exploit the prior information on the licensed signal is the generalized likelihood ratio test (GLRT). One advantage of the GLRT is that it provides joint detection and estimation of unknown parameters [11], and is the optimal statistical test in the Neyman-Pearson sense [1]. Relevant work on GLRT signal detection has been conducted in the context of multiantenna communications [12]–[15]. The algorithms reported in [12]–[15] exploit the correlation that arises in the spatial domain. Hence, these algorithms are resorted to cognitive radios with multiple antennas. Contrarily, this work exploits the time correlation of the legacy signal when the cognitive radio is equipped (but not limited to) with a single antenna. The detection of legacy signals with a single antenna takes advantage of the well defined structure of time correlation matrices of stationary signals. Specifically, because the time domain correlation matrices involved in signal detection have Toeplitz structures, the algorithms developed in this paper will have good properties of stability and computational complexity. Secondly, scanning the whole spectrum is a challenging task due to the power consumption involved in the analog- to-digital converters (AGCs). Adopted alternatives include sequential sensing and filter bank techniques. However, the former incurs significant delay in the sensing process, whereas the latter burdens implementation efficiency. To overcome the aforementioned limitations, nonuniform sampling has gained recent attention as a machinery to exploit the sparsity in the spectrum of the legacy signal [16]. Methods for detecting sparse wideband signals from sub-Nyquist sampling have been discussed in [17]–[20]. The results reported in [17]–[20] show the advantages of nonuniform sampling in the spectrum sensing for cognitive radio problem. However, these works concentrate in reconstructing the spectrum from the samples based on compressed sensing (CS) algorithms [21]. Contrarily to the existent literature, in this work the signal detection problem is posed directly on the nonuniform samples without having to reconstruct the samples neither at the signal level nor at the spectrum level. This work adopts a nonuniform sampler based on the Bernoulli distribution and formulates the GLRT as the optimal signal detector in the low SNR regime. The Bernoulli distribution, initially advocated to solve reconstruction problems This work is under IEEE copyright and its IEEE published version may be found in http://www.ieeexplore.ieee.org. This file constitutes the draft version. Work retroactively supported by project TEC2013-47020-C2-2-R (Ministerio de Economia y Competitividad - SPAIN), published in 2014 before the project's official awarding date 2 in the 1980s [22], has been investigated in the literature for sequential sampling [23] and sparse signal reconstructions [24]. The advantages of Bernoulli nonuniform sampling (BNS) are that it satisfies the restricted isometry property (RIP) with overwhelming probability [25] on the one hand, and that is exhibits good tradeoff properties between complexity and performance on the other hand. The following contributions are obtained under the BNS GLRT setting: 1) The asymptotic analysis of BNS shows that nonuniform sampling incurs a self interference phenomenon, as initially reported in [26]. This phenomenon translates into a whitening effect in the correlation of the legacy signal, which incurs a noise enhancement effect in the signal spectrum as initially observed by the spectral analysis presented in [27]. 2) It is shown that the optimal GLRT signal detector in the low SNR regime strictly depends on the normalized correlation matrix of the legacy signal and the sampling density. The low SNR GLRT with unknown signal powers have been recently addressed in practical scenarios such as uniformly sampled multi-frequency signals [28] and compressive sampled signals [29]. These works report preliminary results without performance analysis. 3) The asymptotic performance of the GLRT is derived in the frequency domain as a function of the sampling density, the legacy signal occupancy and the number of samples. A first approach into performance analysis in uniformly sampled likelihood ratio test (LRT) has been addressed in [30] by making use of the Stein’s lemma. However, this work tackles the asymptotic performance problem, as the Stein’s lemma is not available for unknown parameters [31]. 4) A novel noise uncertainty outage model is introduced, and SNR walls are derived as a function of the sampling density and the legacy signal occupancy. 5) It is shown that, when the SNR is comprised within the sampling walls region given by κ0(U−1) <SNR < U−1, closed-form expressions of sampling walls are derived as κwall =sκ0(U−1−SNR) (1 −κ0)SNR ,(1) where κ0is the legacy signal occupancy and Uevaluates the noise uncertainty. Therefore, defining the sampling density κas the rate between BNS and Nyquist uniform sampling, it is shown that signal detection is not feasible in the sense that the target missed detection and false alarm probabilities cannot be guaranteed regardless the number of samples if κ<κwall. The rest of the paper is organized as follows. Sec. II describes the BNS and the signal detection problem. The GLRT in BNS is derived and statistically characterized in Sec. III. The novel noise uncertainty outage model and the sampling walls are introduced in Sec. IV. Numerical evaluations of the results presented in this paper are reported in Sec. V, and Sec. VI concludes the paper. II. PROBLEM SETTING This paper considers the problem of detecting the presence of a legacy signal in the additive noise model. Let S(t)and Z(t)denote the wide sense stationary (WSS) signal and noise complex analytic processes, respectively. Within the band of interest W, it is assumed that the additive noise is a zero-mean white Gaussian process with known power spectral density (PSD) equal to N0, whereas the signal has known spectral support and unknown power Ps1. The spectral support of S(t) is parameterized by the occupancy κ0comprised within 0< κ0≤1, which is defined as the ratio between the `1-norm of the spectral support and W. The detector must infer between the hypothesis H0in which the observation process has only noise, and the hypotheses H1in which the observation process has both signal and noise. The detection problem is cast as an hypotheses testing problem based on a set of N=TW nonuniform samples acquired during a sensing period of Tseconds. The aim of the hypotheses testing problem is to exploit the side information available in the problem, i.e., the noise variance, the sampling density and the legacy signal autocorrelation. To the end of the paper, the wideband regime W1and asymptotically large number of samples N1are considered. A. Bernoulli Nonuniform Sampling For the sake of simplicity and without loss of generality, the BNS is presented in the noise free case. The signal detection scenario is addressed by extension. The sampling pattern ψn, for 0≤n<N, is distributed according to a Bernoulli distribution, independent from the signal process, with parameter κsuch that Pψn=1 √κ=κ, (2a) P[ψn= 0] = 1 −κ, (2b) where 0< κ ≤1. Because E[ψn6= 0] = κ, the parameter κdenotes the sampling density. Notice that for κ= 1, the BNS reduces to the Nyquist rate uniform sampling case. One advantage of BNS is that it can be related to the Nyquist rate uniform sampling extreme by the following product of discrete-time sequences xn=ψn·sn,(3) where sn. =S(n/W)are uniformly samples at a rate W. A second advantage of BNS is that it admits the following compressed sensing formulation. By collecting the Nconsecutive samples into the vector x. = (x0, . . . , xN−1)T, the nonuniform samples can be mathematically expressed as2 x=Ψs,(4) 1Because this work focuses on detecting whether the band of interest is totally or partially occupied, a general formulation on S(t)is adopted based on the normalized correlation matrix. This model encompasses practical scenarios such as multiple legacy signals S(t) = PjSj(t), or the exploitation of channel state information (CSI) S(t) = PjHj(t)∗Sj(t). 2Even though (4) reminds the CS formulation, this work adopts a different approach by considering zeros in the non-sampled positions. This allows to tackle the problem as a product of random discrete-time sequences and conduct a second order statistical analysis. 3 where s. = (s0, . . . , sN−1)T, and the sensing matrix is constructed as Ψ. = diag(ψ0, . . . , ψN−1). The motivation of BNS is supported by the fact that the vector sis mathematically sparse in the spectrum domain. The third advantage of BNS is that it permits a closed form formulation of the second order statistic of x. Let Rs. =EssHbe the correlation matrix of s, and recall that Psis the power of S(t). Then, the correlation matrix of x,Rx. =ExxH, admits the following equivalence Rx=κRs+ (1 −κ)PsIN,(5) where INis the identity matrix. The equivalence (5) follows from the properties of the correlation of the sampling pattern ψn. For the details the reader is referred to the Appendix A and the work in [26]. It is interesting that, even in the noise free case, the correlation of a BNS signal suffers from a self interference term or noise enhancement term which is proportional to the product between (1 −κ)and the signal power. This self interference has white statistics, i.e., it only affects to the main diagonal of Rs. It is also important to point out that the signal power is preserved, since tr(Rx) = tr(Rs) for any value of κ. As a consequence, the nonzero correlation lags suffer from an attenuation factor of κ, decreasing the overall correlation of the BNS signal. This is not surprising, as the nonzero samples in xbecome more separate in average as κdecreases. B. Hypothesis Testing Problem The detector acquires samples during a sensing time of duration T. Because the paper focuses on the asymptotic performance of exploiting the side information of the problem, i.e., the noise variance, the sampling density and the legacy signal autocorrelation, the sensing time is scaled in order to satisfy a constant average nonzero samples in the observation process equal to M. This parameter will be referred to as the number of effective samples, or simply the number of samples. This is straightforwardly accomplished by setting the sensing time Tto satisfy the relation TκW =M, where M is a constant independent on κ. Under these assumptions, the signal detection problem reads H0:x=Ψz,(6a) H1:x=Ψ(s+z),(6b) where the observation size is the nearest integer Nto satisfy M=κN. Signal detection in wideband regimes is a challenging problem due to the hard low SNR and sparsity conditions. Let SNR . =Ps N0W.(7) Notice that the SNR of the problem is preserved in BNS, as the power is preserved for both the signal and noise processes. Clearly, for a fixed signal power, it follows that when the sensing bandwidth increases as W1, the SNR asymptotically approaches to zero. In statistical signal detection, the signal detection problem described in (6) is equivalent to consider H0:x∼g0(x),(8a) H1:x∼g1(x),(8b) where g0(x)and g1(x)denote the Gaussian distributions of the observations under H0and H1, respectively3. Let CNN(µ,R)denote the N-dimensional circular symmetric complex Gaussian distribution with mean µand covariance matrix R. Then, g0(x) = CNN(0,R0)and g1(x) = CNN(0,R1), where the correlation matrices are given, from (5) and (6), as H0:R0=σ2IN,(9a) H1:R1=σ2IN+PsΣκ,(9b) where σ2=N0Wis the total noise power, and Σκis the normalized correlation matrix of Ψs, given from (5) as Σκ. =κΣs+ (1 −κ)IN,(10) being Σsthe normalized correlation matrix of s, related to Psand Rsas Rs=PsΣs. The definition of the normalized correlation matrices Σκand Σshas been done in analogy to the noise correlation matrix, i.e., all satisfy tr(Σκ) = tr(Σs) = tr(IN) = N. The matrix Σκis a function of the sampling density and the normalized correlation of S(t). In a cognitive radio scenario the detector may have knowledge on the noise power σ2and on the normalized statistics of the signal. However, the knowledge on the signal power is rather impractical. For this reason, this work considers signal detection in the general case of unknown Psand studies the effect of uncertainty around the knowledge of σ2. III. OPTIMAL LOW SNR TEST In this Section, the formulation of the optimal test statistic to solve the signal detection problem (6) in the Neyman- Pearson sense is discussed. The optimal test statistic that exploits the available side information of the problem, i.e, the noise variance, the sampling density and the legacy signal autocorrelation, and addresses unknown parameters (Ps)is given by the GLRT. The GLRT consists of the ratio of the probability density functions (PDFs) of the observations where the unknown parameter is substituted by its maximum likelihood (ML) estimate. In the sequel, the ML estimation of the signal power is first addressed for the case of W1. The expression of the ML estimate is then used to formulate the GLRT. The asymptotic performance of the GLRT is further analyzed for the asymptotic cases of large data records, i.e., when the observation size N1. A. GLRT Signal Detector The ML estimate of the signal power, derived in Appendix C, is given as W1by ˆ Ps=xHΣκx−Nσ2 tr(Σ2 κ).(11) 3While under H0the Gaussian assumption on the noise process is widely accepted, in general the distribution of the observations under H1remains unknown. In this paper, the properness of the Gaussian assumption of sis twofold. Firstly, it has been proved that adopting the Gaussian distribution for the signal statistic is valid in the low SNR regime [32]. And secondly, the Gaussian distribution is the least favorable distribution in signal detection for a given signal power, as claimed in Appendix B. Furthermore, in practical scenarios such as multiple legacy signals S(t) = PjSj(t), the Gaussian assumption holds for each Sj(t)and, hence, for S(t). 4 The estimate (11) admits the following two interpretations. At first, the term xHΣκximplements a generalized energy detector (ED) in the norm defined by the BNS normalized correlation matrix. As the power in the observations includes the noise contribution, the latter is compensated with the term Nσ2. The power estimation is finally obtained after a normalization factor given by the trace of the squared value of the BNS normalized correlation matrix. A second interpretation is understood when arranging the numerator of (11) as tr[Σκ(xxH−σ2IN)], which implements the scalar product between the BNS normalized correlation matrix and the matrix (xxH−σ2IN). The latter evaluates solely the contribution of the signal in the second order statistic of the observations, because the rank-1 matrix xxHbehaves as an estimation of the correlation matrix and the noise contribution is balanced by subtracting its correlation matrix, i.e., σ2IN. The GLRT is given by the ratio L(x) = CNN(0, σ2IN+ˆ PsΣκ) CNN(0, σ2IN)≥γ, (12) where ˆ Psis given by (11), and the threshold γdefines the regions for which H0(L(x)< γ)or H1(L(x)≥γ)are decided. The threshold can be set analytically when the test statistic (12) admits perfect statistical characterization, which is not the case in most situations except in some special assumptions such as the asymptotic scenarios considered in this work with W1and N1. Under these premises, the GLRT signal detector is derived in Appendix D, and is given as W1by T(x) = xHΣκx≥τ, (13) where the new threshold can be related to the original threshold by the expression τ=σ2hN+ptr(Σ2 κ) log(γ)i.(14) Interestingly, the expression of the GLRT signal detector (13) is simply given by the part of the ML estimate of the signal power which involves the observations. It is also worth noting that, in general, the non-negativity of the numerator of (11) is not guaranteed, and therefore (11) is not properly an estimate of the signal power. If the constraint Ps∈R+is included as a complimentary Lagrange multiplier in the optimization problem involved in the derivation of (11), it will follow that the non-negativity must be forced by max(0,ˆ Ps). However, this remains unnecessary when the purpose of (11) is signal detection, because the mathematical operations which relate (11) and (13) incur in a shift and scaling in the computation of the threshold, independent on the observations. Recall that in this work the GLRT signal detector (13) is derived under the wideband assumption W1. Since the wideband regime is equivalent to the low SNR regime, (13) puts in remembrance classical results [1] and several works in the recent literature. One recent method for spectrum sensing in open spectrum communications based on the correlation matching approach has been reported in [6]. Although [6] adopts a different technique, it is worth noting that (13) acts as a correlation matching estimate when the candidate matrix is the BNS normalized correlation matrix. This is not surprising, as the correlation matching behaves as an equivalence to ML in the low SNR regime [33]. Similarly, the recent work [8] has shown that exploiting spectral features, i.e., a second order statistic of the legacy signal, is optimal for asymptotically low SNR regimes. B. Asymptotic Statistical Characterization The statistical characterization of GLRTs is usually a hard problem. The GLRT signal detector (13) is a quadratic form on the observation vector x. The statistics of a quadratic form is known if and only if the matrix involved in the quadratic form has properties of symmetry and idempotence within the covariance matrix of the observations [34]. That is not the case, as in general Σκis not idempotent, i.e., Σ2 κ6=Σκ, nor it is idempotent within any correlation matrix under the two hypotheses (9), i.e., ΣκR0Σκ6=Σκand ΣκR1Σκ6=Σκ. Alternatively, the quadratic form (13) has the same distribution as the following weighted sum of independent Chi-square random variables with two degrees of freedom [35] T(x)∼ r X n=1 λn(RxΣκ)wn 2,(15) where r= rank(Σκ),wn∼ X2 2and the weights λn(RxΣκ) denote the n-th largest eigenvalue of the quadratic form, given by H0:λn(R0Σκ) = σ2λn(Σκ)(16a) H1:λn(R1Σκ) = σ2λn(Σκ) + Psλ2 n(Σκ),(16b) where λn(Σκ)the n-th largest eigenvalue of Σκ. As N1, the former weighted sum of Chi-square random variables can be approximated by Gaussian distributions [36] whose means and variance are derived in Appendix E. As a result, the GLRT signal detector (13) is asymptotically distributed as H0:T(x)∼ N Nσ2,2Nσ4ρ(17a) H1:T(x)∼ N Nσ2(1 + SNRρ), 2σ4tr(Σ2 κ(IN+SNRΣκ)2),(17b) where N(µ, σ2)denotes the continuous Gaussian probability distribution with mean µand variance σ2. The properness of the Gaussian distribution for T(x)is corroborated in Figure 1, which shows the theoretical (17) and empirical PDFs in four sampling density scenarios. As it can be appreciated, the Gaussian distribution is more pessimistic than the true distribution. Hence, the Gaussian assumption on the distribution of the GLRT signal detector (13) behaves again as a worst case formulation. Also, it is worth noting that as the sampling density diminishes, the theoretical distribution behaves as better approximation because the BNS observations become more uncorrelated. In (17), the squared correlation coefficient has been introduced as ρ. =1 N r X n=1 λ2 n(Σκ).(18) This parameter, which can be rewritten as ρ= (1/N)tr(Σ2 κ), is a measure of dependence, and plays a relevant role in the 5 400 500 600 700 0 0.005 0.01 0.015 T(x) PDFs κ= 1/8 150 200 250 300 350 400 0 0.005 0.01 0.015 0.02 T(x) κ= 1/4 50 100 150 200 0 0.005 0.01 0.015 0.02 0.025 T(x) κ= 1/2 0 50 100 150 0 0.005 0.01 0.015 0.02 0.025 T(x) κ= 1 H0 H1 H0 H1 H0 H1 H1 H0 Fig. 1. Theoretical (lines) and empirical (stems) PDFs of the GLRT signal detector (13) under H0and H1, for several sampling densities of a randomly generated signal with squared correlation coefficient ρ= 8/3,M= 64 and SNR =−10 dB. rest of the paper. The parameter ρstrongly depends on the sampling density κof BNS, as well as the structure of the correlation matrix Σs. By employing the Cauchy-Schwarz inequality Pr n=1 λ2 n(Σκ)≥(1/N) (Pr n=1 λn(Σκ))2and recalling the normalization Pr n=1 λn(Σκ) = N, it follows that the squared correlation coefficient (18) is lower bounded by ρ≥1, where the equality ρ= 1 is achieved for Σκ=IN. It is easy to see from the BNS correlation equivalence (10) that this situation is asymptotically true as κ1. On the other extreme, since ρcomputes the sum of the squared value of the eigenvalues of Σκ, the maximum of ρis achieved when Σκ has a unique eigenvalue equal to N. This corresponds to the uniform sampling (κ= 1) fully correlated case (e.g., deterministic signals employed as pilots) in which Σκis a rank-1. In such a scenario, ρ=N. Therefore, the squared correlation coefficient is comprised within the interval 1≤ρ≤N. C. Frequency-Domain Interpretation In [37], it has been shown that quadratic detectors can be approximated by the correlation between the periodogram of the observations and an spectral mask corresponding to the N- points sampled vector of the Fourier transform of the matrix involved in the quadratic detection. In fact, this approximation behaves asymptotically as N1equivalently to the optimum quadratic detector, because the matrix involved in the quadratic detection is equivalent to a circulant matrix whose eigenvalues are given by the spectrum evaluated at the n-th frequency bins and whose eigenvectors are from the Fourier matrix [38]. In this work, the GLRT signal detector (13) is asymptotically equivalent to the frequency domain test T(x)≃N 2πZπ −π φκ(ω)P(ω)dω, (19) In (19), φκ(ω)is the normalized spectrum of the BNS signal (i.e, the frequency domain version of Σκ) normalized to the unit power as 1 2πZπ −π φκ(ω)dω = 1,(20) and P(ω)is the periodogram of the observations, i.e., P(ω) = 1 NeH ωx2,(21) where eH ω= [1 e−ω . . . e−(N−1)ω]. Analogously, the squared correlation coefficient ρdefined in (18) admits the following asymptotic frequency domain implementation ρ≃1 2πZπ −π φ2 κ(ω)dω. (22) Because φκ(ω)is normalized, the squaring operation in (22) attenuates the areas in which the spectrum is low and preserves the areas in which the spectrum is high. Therefore, the frequency domain squared correlation coefficient is a measure of the concentration of the spectrum in frequency. In BNS, the spectrum of the observations suffers from the self interference term or noise enhancement term analogous to the normalized correlation (10). The normalized spectra are then related by the linear combination φκ(ω) = κφs(ω) + (1 −κ),(23) being φs(ω)the normalized spectrum of S(t). Restricting the study to flat spectrum signals4with unknown spectral support and known occupancy κ0, it rapidly follows that the normalized spectrum of S(t)is of the form φs(ω)=1/κ0 when ωlies in the spectrum support, and φs(ω) = 0 otherwise. This formulation allows to parameterize the frequency domain squared correlation coefficient as a function of the sampling density and the occupancy by ρ≃κ0+ (1 −κ0)κ2 κ0 .(24) The former expression will essentially describe the behavior of the asymptotic performance of the GLRT signal detector (13) in terms of the relation between κand κ0. To this point, the coherence between (18) and (24) is complemented in the following extreme cases. When the occupancy approaches to one, ρ≃1regardless the sampling density κ. This corresponds to the case in which the BNS signal has white statistics, i.e., Σκ=IN, and the GLRT signal detector only exploits the zero 4The properness of adopting the flat spectrum assumption is threefold. Firstly, it allows to obtain clear insights as the frequency domain squared correlation coefficient is characterized by a single parameter of the legacy signal, i.e, the occupancy κ0. Secondly, the flat spectrum assumption holds in many practical legacy systems, such as terrestrial digital video broadcasting (DVB-T) based orthogonal frequency-division multiplexing (OFDM). And thirdly, for a given occupancy, the flatness assumption acts as a worst case scenario, as any signal with equal power and non-flat spectrum will exhibit larger correlation coefficient. This claim is proved in Appendix F. 6 lag correlation. Finally, if the sampling density approaches to one (uniform sampling), the remaining terms simplify to ρ≃1/κ0which increases inversely proportional to the occupancy. Therefore, the frequency domain squared correlation coefficient is comprised within the interval 1≤ρ≤1/κ0, provided that N1/κ0. D. Asymptotic Performance The performance of the GLRT signal detector (13) is evaluated by means of the error probability pair (α, β), namely the false alarm and missed detection probabilities, defined as α. =P0[T(x)≥τ]and β. =P1[T(x)< τ], respectively, where P0and P1evaluate the probability in the events H0and H1, respectively. From the asymptotic PDFs (17), in Appendix G it is shown that the minimum SNR for achieving a target error probability pair (α0, β0)scales with the observation size and the squared correlation coefficient as SNRmin ∝1 √Nρ.(25) The rate at which SNRmin decreases is strongly related to the correlation level present in the BNS signal. Restricting to uniform sampling (κ= 1 and N=M), the squared correlation coefficient (18) evaluates the correlation level of S(t). Therefore, the scaling of SNRmin has the following extreme values. On the one hand, the worst scenario is given by the lower bound ρ= 1, which represents a totally uncorrelated signal. In such a case, SNRmin ∝p1/M, which corresponds to the scaling of the SNR in the ED [1]. This is a known detection result in digital communications, as the error probability in non-coherent communications (e.g., detection or synchronization of unknown waveforms) scales as the inverse of the squared root of the sensing time. On the other hand, the best scenario is given by the upper bound ρ=M, which represents a fully correlated signal. In such a case, it follows that SNRmin ∝1/M, i.e., the minimum SNR scales inversely proportional to the observation size. This is also a known result in digital communications, as the error probability in coherent communications (e.g., detection or synchronization of known waveforms) scales with the inverse of the sensing time [1]. For arbitrary sampling density 0< κ ≤1, one can evaluate the evolution of SNRmin by making use of the frequency domain interpretation of the squared correlation coefficient (22). After some mathematical manipulations and recalling that Nis the nearest integer that satisfies M=κN, it follows that the minimum SNR scales as SNRmin ∝rκκ0 κ0+ (1 −κ0)κ2·1 √M.(26) The importance of the former expression is given by the fact that it evaluates the rate at which the minimum SNR required for signal detection in BNS scales with the sampling density and the occupancy. In Fig. 2, the normalized minimum SNR is plotted against the sampling density for several occupancies. It is appreciated that if the occupancy is below κ0<1/2, there exists a sampling density given by κmin =rκ0 1−κ0 ,(27) 0 0.2 0.4 0.6 0.8 1 −10 −8 −6 −4 −2 0 κ √M·SNRmin (dB) κ0= 1 κ0= 3/8 κ0= 1/8 κ0= 1/32 κmin Fig. 2. Evolution of the minimum SNR (26) as a function of the sampling density and the occupancy, and location of the sampling densities that achieve worst case minimum SNR (27). above which the GLRT signal detector is able to exploit the remaining correlation in the BNS signal. Hence, the minimum SNR is monotonically decreasing (improves) with the sampling density (higher rates) only if κ>κmin. On the other hand, for sampling densities κ < κmin, the white self interference incurred in BNS degrades the signal autocorrelation in such a level that the GLRT signal detector essentially resorts to energy detection. Therefore, in this range the minimum SNR decreases with a rate of √κas κ1, because the sensing time is increased with a factor of κ. In conclusion, the minimum sampling density κmin acts as a worst case scenario on the minimum SNR in BNS signal detection. Interestingly, both the location of the minimum sampling density and the value of the worst case minimum SNR (red cross markers in Fig. 2) increase with the occupancy. This corroborates that smaller sampling rates can be attained when the occupancy of the signal is small compared to W. In the limit, as κ01, the minimum sampling density can be approximated by κmin ≈√κ0. In such a case, the BNS sampling density must be higher than the squared root of the occupancy in order to take advantage of the side information of the problem, i.e., the noise variance, the sampling density and the legacy signal autocorrelation. A final highlight is that an alternative indicator of the asymptotic performance of the GLRT signal detector is the normalized minimum sensing time Tmin. This parameter behaves as a measure of complexity involved in the detection process, as the complexity of a quadratic form with Toeplitz matrices is of the order O(2N). From (25) and after some mathematical manipulations, it follows that the normalized minimum sensing time that achieves a target error probability pair scales with the SNR and the squared correlation coefficient as Tmin ·W∝1 SNR2ρ,(28) i.e., it scales inversely to the squared value of the SNR and with the inverse of the squared correlation coefficient. 7 IV. SAMPLING WALLS IN NOISE UNCERTAINTY This section addresses the performance of (13) in the presence of noise uncertainty. Because the noise variance cannot be known with infinite precision in real physical systems, a small error model is adopted as noise uncertainty. This model imposes fundamental limitations on the detection performance, even though when the noise level in silent times is estimated in a time duration that do not scale with the sensing time [39]. These limitations are presented in terms of SNR walls [40]. In this paper, these detection walls are extended to sampling walls, i.e., sampling densities below which the detection is not possible, even for infinite sensing time. Let ˆσ2be a random variable denoting the prior information on the noise variance. In the small error model, it is assumed to be uniformly distributed within the range σ2/δ ≤ˆσ2≤δσ2.(29) In the sequel, this will be referred as having a noise uncertainty of u= 10 log10 δdB. From the asymptotic PDFs (17), the error probability pair (α0, β0)cannot be guaranteed because the uncertainty on the noise variance translates to a wrong setting of the threshold (14). In this work, the threshold is set to guarantee a given outage on the false alarm and missed detection probabilities. In other words, the value of τdelivers a false alarm αand a missed detection βsuch that P[α≥α0]<  and P[β≤β0]< ,0≤  < 1, where the probability is evaluated in the randomness of σ2. If = 0, then the target error probability pair is satisfied for any range of ˆσ2(worst case approach). In Appendix H, it is shown that the minimum SNR for achieving a target error probability pair (α0, β0)with outage probability scales with the observation size and the squared correlation coefficient as SNRmin ∝1 √Nρ +U−1 ρ,(30) where Ua parameter that relates the uncertainty level and the outage probability as U=δ2(1 −) +  δ2+ 1 −.(31) Notice that for = 0,Ubecomes the peak-to-peak ratio of the uncertainty model. By comparing (30) to (25), it is easy to see that the noise uncertainty incurs in a penalty in terms of SNR which is inversely proportional to the squared correlation coefficient and that it is always nonnegative, as U≥1. This term is referred as the SNR wall associated to the GLRT signal detector (13), defined as SNRwall . = lim N→∞ SNRmin =U−1 ρ.(32) In the worst case of uncorrelated signal (ρ= 1), the SNR wall is linear with the parameter (31) as SNRwall =U−1. This is the classical ED SNR wall [40]. In the most favorable scenario of fully correlated signal, i.e., when ρ=N, the SNR wall improves as it scales inversely proportional to the observation size. Region Interval Unfeasibility Region 0≤SNR < κ0(U−1) Sampling Walls Region κ0(U−1) <SNR < U −1 Wallfree Region SNR > U −1 TABLE I SNR REGIONS FOR SAMPLING WALLS The SNR wall (32) admits the following frequency domain interpretation by plugging the expression of the squared correlation coefficient that relates the BNS sampling density and the occupancy. This leads to SNRwall =κ0 κ0+ (1 −κ0)κ2·(U−1).(33) For Nyquist uniform sampling, i.e, κ= 1, the SNR wall is directly related to the occupancy as SNRwall =κ0(U−1). This means that the SNR wall is smaller when the legacy signal has low occupancy, because the signal detector preserves the ability of distinguishing a narrowband signal immersed in white noise, regardless the exact level. On the contrary, for a very low sampling density, i.e., κapproaching zero, the SNR wall approaches the ED: SNRwall =U−1. The two aforementioned SNR walls, which correspond to Nyquist uniform sampling and ED, define the SNR region in which sampling walls are experienced. In Tab. IV, the three following SNR regions are introduced: •First, the unfeasibility region is the SNR region characterized by the inability of the GLRT signal detector (13) to guarantee the target error probabilities, even for an infinite number of samples. •Second, the wallfree region is lower bounded by the SNR wall of ED. In this region, the nonexistence of sampling walls is guaranteed regardless the combination of sampling density and legacy signal occupancy. •And third, the sampling walls region is the SNR region comprised within the SNR walls κ0(U−1) and U−1. The existence of sampling walls inside this region is consequence from the feasibility condition SNR >SNRwall in (33). After some mathematical manipulations, the feasibility condition (33) is translated to the feasibility condition κ>κwall,(34) where the sampling wall κwall is given as a function of the noise uncertainty, the legacy signal occupancy and the SNR by the following expression κwall =sκ0(U−1−SNR) (1 −κ0)SNR .(35) The sampling wall (35) is a fundamental limit, below which detection is not feasible, i.e., the target error probabilities cannot be guaranteed. From (35), it is seen that the sampling wall is proportional to the occupancy. Therefore and as expected, higher compression rates can be achieved in low occupancy scenarios. Finally, an alternative representation of sampling walls is reported through the normalized minimum sensing time that 8 10−3 10−2 10−1 100 10−3 10−2 10−1 100 α β κ0= 1/8 κ0= 3/8 κ0= 1 SNR= −7.5 dB SNR= −2.5 dB Fig. 3. Theoretical (lines) and empirical (markers) receiver operating characteristics for several occupancies at a sampling density κ=κmin at two values of SNR. achieves the target error probabilities, Tmin. By rewriting (30), the normalized minimum sensing time scales as Tmin ·W∝1 ρ(SNR −SNRwall)2,(36) i.e., inversely proportional to the squared correlation coefficient and with asymptotes located at the SNR walls and sampling walls. V. NUMERICAL RESULTS In this Section, the performance of the GLRT signal detector (13) and the behavior of the fundamental limits derived in this paper are empirically evaluated. In what follows, the legacy signal is generated according to the terrestrial video broadcasting (DVB-T) standard in the 2k-mode with 8 bands, which exhibits a flat spectrum in the spectral support and allows concrete configurations of the occupancy. A. Performance of the GLRT Signal Detector in BNS The performance of the GLRT signal detector (13) in BNS is evaluated in terms of the false alarm and missed detection probabilities in the following scenarios of occupancies and noise uncertainties. In the following, the number of samples has been fixed to M= 64 samples. First, Fig. 3 plots the receiver operating characteristics (ROC) at two values of SNR for several occupancies when the sampling density of BNS has been set to κ=κmin, according to the expression (27). Markers denote the empirical probabilities obtained through 100,000 random realizations of the BNS with occupancy κ0. Because the sampling density has been set to the minimum sampling density, the ROC depicted in Fig. 3 are fundamentally worst case scenarios. In other words, the maximum penalty incurred in BNS is evaluated. At an SNR =−7.5dB, it can be appreciated that the theoretical false alarm and missed detection probability pair given in (54) and (56) in Appendix G behave as good approximations of the empirical probabilities. However, as the −15 −10 −5 0 0 0.2 0.4 0.6 0.8 1 SNR (dB) 1−β κ0= 1/8 κ0= 3/8 κ0= 1 u= 0 dB u= 0.5 dB Fig. 4. Theoretical (lines) and empirical (markers) complimentary missed detection probability versus SNR for several occupancy at a sampling density κ=κmin, with (red) and without (black) noise uncertainty. SNR increases, it is seen that the theoretical expressions based on the Gaussian assumption act as a worst case scenario, being an upper bound on the empirical missed detection probability for any false alarm probability. In both SNR ranges, the performance of the GLRT signal detector improves with smaller occupancies. For instance, for a false alarm probability of 10% and SNR =−2.5dB, a signal with an occupancy of 12.5% has an improvement in terms of missed detection probability of almost two orders of magnitude with respect to the energy detection of white signals. Analogous results are obtained in the evolution of the complimentary missed detection probability, as plotted in Fig. 4 against the SNR for a fixed false alarm probability of 1% for several occupancies when the sampling density of BNS has been also set to κ=κmin. Markers denote the empirical probability obtained through 100,000 random realization of the BNS and a flat spectrum signal with occupancy κ0. In this plot, it is noted that for a fixed missed detection probability level, the gain attained with BNS in low occupancy scenarios is of several dBs of SNR. Further, the penalty incurred by a noise uncertainty of u= 0.5dB with a probability outage of = 0.1is of the same order regardless the occupancy of the signal, and implies a shift in the missed detection probability of about 1-2 dB. B. SNR Walls and Sampling Walls In this paper, two fundamental detection walls have been derived under noise uncertainty, namely the SNR walls and the sampling walls. The theoretical SNR walls and sampling walls are visually depicted as asymptotes in Fig. 5 and 6, respectively, both plotting the evolution of the normalized minimum sensing time (36) for a target error probability pair α0=β0= 0.01. In both figures, markers denote the empirical sensing times obtained through 100,000 random realizations of the BNS signal. The SNR walls are illustrated in Fig. 5 when plotting the normalized minimum sensing time versus the SNR for several 9 sampling densities for an occupancy of 37.5%. When there is no noise uncertainty (u= 0 dB), the scaling of Tmin with the SNR is linear in the logarithmic scale, according to (28). In other words, for every increase of 5 dB in SNR, the target error probability pair can be achieved 10 times faster. Further, sampling at a lower density also requires sensing during a larger period of time. Finally, when the noise variance has an uncertainty of u= 0.5dB with a probability outage of = 0.1, the SNR walls (33) appear as asymptotes on the normalized minimum sensing time, as if SNR ≤SNRwall, the false alarm and missed detection target error probability pair cannot be achieved regardless the normalized minimum sensing time devoted to detection. Also, as it can be appreciated in the expression of the SNR walls, the location of the walls moves toward higher SNRs as the sampling density is smaller. The empirical results validate both the slope of the minimum sensing time with the SNR and the location of the SNR walls for the sampling densities considered. On the other hand, the sampling walls are illustrated in Fig. 6 when plotting the normalized minimum sensing time versus the sampling density for several occupancies and for a fixed SNR of −11.5dB. For a given occupancy, the normalized minimum sensing time is monotonically increasing when moving toward smaller sampling densities. Since the SNR conditions are inside the sampling wall region, the sampling walls (35) appear as asymptotes in the normalized minimum sensing time. For instance, for an occupancy of κ0= 1/8and a noise uncertainty of u= 0.5dB, the SNR wall in the ED and the SNR wall in Nyquist uniform sampling are given by U−1 = −10.15 dB and κ0(U−1) = −19.18 dB, respectively. Hence, for SNR =−11.5dB, the inequality κ0(U−1) <SNR < U −1(37) is satisfied. The location of the specific sampling wall is given, from (35), by κwall = 0.2275, which is slightly below the minimum sampling density κmin =p1/7 = 0.3780. In other words, sampling below κmin makes impossible signal detection based on the signal autocorrelation, while sampling below κwall makes the target error probability pair unattainable. Finally, the empirical markers confirm the existence and location of sampling walls for the occupancy rates considered, as well as the behavior of the minimum sensing time with the sampling density of BNS. VI. CONCLUSIONS In this paper, closed-form expressions of sampling walls in BNS have been derived in the presence of noise uncertainty. The optimal low SNR GLRT signal detector has been derived. The asymptotic statistical characterization of the test has provided theoretical insights into the minimum SNR, false alarm probability, missed detection probability, SNR walls and sampling walls as functions of the legacy signal occupancy and sampling density. Numerical results have been reported to assess the validity of the derived theoretical expressions. −16 −14 −12 −10 −8 −6 100 102 104 106 108 1010 SNR (dB) Tm in ·W κ= 1/4 κ= 1/2 κ= 1 u= 0.5 dB u= 0 dB SNRwall Fig. 5. Theoretical (lines) and empirical (markers) evolution of the normalized minimum sensing time (36) as a function of the SNR for several sampling densities, several noise uncertainties, and occupancy κ0= 3/8. 0 0.2 0.4 0.6 0.8 1 100 102 104 106 108 1010 κ Tm in ·W κ0= 1/8 κ0= 3/8 κ0= 5/8 κwall u= 0.5 dB u= 0 dB Fig. 6. Theoretical (lines) and empirical (markers) evolution of the normalized minimum sensing time (36) as a function of the sampling density for several occupancies and noise uncertainties, at SNR =−11.5dB. APPENDIX A DERIVATION OF THE BERNOULLI NONUNIFORM SAMPLING CORRELATION EQUIVALENCE (5) Consider the BNS sequence xn=ψn·sn, where ψnis distributed as in (2) and sn=S(n/W )are uniformly sampled at the Nyquist rate W. Given the statistical independence between ψnand sn, it follows that the autocorrelation of xnis given by the product of autocorrelations, i.e., rx[m]. = E[xnx∗ n−m] = rs[m]·rψ[m], where rψ[m]. =E[ψnψ∗ n−m]and rs[m]. =E[sns∗ n−m]. As a Bernoulli process, the autocorrelation of ψnis given by rψ[m] = δ[m] + κPm06=mδ[m−m0]. A more convenient way to write rψ[m]is rψ[m] = (1 −κ)δ[m] + κX m06=m δ[m−m0].(38) Hence, from rx[m] = rs[m]·rψ[m], it follows that rx[m] = κrs[m] + (1 −κ)Psδ[m].(39)