Optimal Correlators and Waveforms for Mismatched Detection

The topic of detection of signals corrupted by noise has a very long history of active research efforts, as it has an extremely wide spectrum of engineering applications in the areas communications and signal processing. These include radar, sonar, light detection and ranging (LIDAR), object recognition in images and video streams, diagnosis based on biomedical signals, watermark detection in images and audio signals, seismological signal detection related to geophysical activity, and object detection using multispectral/hyperspectral imaging, just to name a few. One of the most problematic and frequently encountered issues in signal detection scenarios is mismatch between the signal model and the detector design, which is based upon certain assumptions on that model. Accordingly, the topic of mismatched signal detection has received considerable attention in the literature, see, e.g., [1], [10], [11], [18], [19], [20], [21], [28], and [30], for a non-exhaustive list of relevant references. The common theme in most of these works is the possible presence of uncertainties in the desired signal to be detected, in the steering vector, in the transfer function of the propagation medium, and/or in the distributions of the various kinds of noise, interference and clutter. Accordingly, adaptive detection mechanisms with tunable parameters have been developed and proposed in order to combat those types of mismatch.

Another line of earlier relevant research activity is associated with the notion of robust detection techniques, where the common theme is generally directed towards a worst-case design of the detector against small non-parametric uncertainties around some nominal noise distribution, most notably, a Gaussian distribution. See, e.g., [2], [4], [5], [9], [12], [13], [15], [16], [17], [22], [24], and [25]. See also [14] for a survey on the subject.

Last but not least, when the uncertainty is only in a finite number of parameters of the model, the problem is normally treated in the framework of composite hypothesis testing, where the popular approach is the well–known generalized likelihood ratio test (GLRT) [27], which is often (but not always) asymptotically optimal in the error exponent sense, see, for example, [3], [6], [7], and [29]. The GLRT is applied also in some of the above cited articles on mismatched detection, among many others. Another approach to composite hypothesis testing is the competitive minimax approach, proposed in [8].

Our objective in this work is partially related to those studies, but it is different. It is associated with mismatched detection, except that the origin of this mismatch is not quite due to uncertainty in the signal-plus-noise model, but it comes from practical considerations: the optimal likelihood ratio test (LRT) detector might be difficult to implement in many application examples, especially in the case of sensors that are built on small, mobile devices which are subjected to severe limitations on power and computational resources. In such situations, it is desirable that the detector would be as simple as possible, e.g., a correlation detector, or a detector that is based on correlation and energy. Within this framework, the number of arithmetic operations (especially the multiplications) should be made as small as possible. Clearly, a detector from this class cannot be optimal, unless the noise is Gaussian, hence the mismatch. Nonetheless, we would like to find the best correlator weights in the sense of optimizing the trade-off between the false-alarm (FA) and the missed–detection (MD) rates. This would partially compensate for the mismatch in case the noise is not purely Gaussian.

More precisely, consider the following signal detection problem, of distinguishing between two hypotheses:

where $\{N_{t}\}$ is an independently identically distributed (IID), zero-mean Gaussian noise process with variance $\sigma_{N}^{2}$, independent of $\{X_{t}\}$, which is another random process, that we decompose as $X_{t}=s_{t}+Z_{t}$, with $s_{t}=\mbox{\boldmath$E$}\{X_{t}\}$ being a deterministic waveform and $Z_{t}=X_{t}-s_{t}$ being an IID, zero-mean noise process, which is not necessarily Gaussian in general. The non–Gaussian noise component, $\{Z_{t}\}$, can be thought of as signal–induced noise (SIN), which may stem from several possible mechanisms, such as: echos of the desired signal, multiplicative noise, cross-talks from parallel channels conveying correlated signals, interference by jammers, and in the case of optical detection using avalanche photo-diodes (APDs), it corresponds to shot noise plus multiplicative noise due to the random gain of the device (see, e.g., [23] and references therein, for more details). In general, $\{Z_{t}\}$ may also designate randomness that could be attributed to uncertainty associated with the transmitted signal.

As mentioned above, the optimal LRT detector might be considerably difficult to implement in practice since the probability density function (PDF) of $\{Y_{t}\}$ under ${\cal H}_{1}$ involves the convolution between the Gaussian PDF of $N_{t}$ and the (non-Gaussian) PDF of $Z_{t}$, which is typically complicated. As said, a reasonable practical compromise, valid when the underlying signal $\{s_{t}\}$ is not identically zero, is a correlation detector, which compares the correlation, $\sum_{t=1}^{n}w_{t}Y_{t}$, to a threshold, where $w_{1},\ldots,w_{n}$ are referred to as the correlator weights, and the threshold controls the trade-off between the FA probability and the MD probability. Our first objective is to characterize the best correlator weights, $w_{1}^{*},\ldots,w_{n}^{*}$, in the sense of the optimal trade-off between the FA probability and the MD probability, or more precisely, the optimal trade-off between the asymptotic exponential rates of decay of these probabilities as functions of the sample size $n$, i.e., the FA exponent and the MD exponent. Clearly, the optimal correlation detector is, in general, not as good as the optimal, LRT detector, but it is the best compromise between performance and the practical implementability in the framework of correlation detectors. As very similar study was already carried out in [23], in the context of optical signal detection using photo-detectors, where the optimal correlator waveform was characterized in terms of the optical transmitted signal in continuous time, and was found to be given by a certain non-linear function of the optical signal.

Here, we study the problem in a more general framework, in the sense that the PDF of the SIN, $Z_{t}$, is arbitrary. Moreover, we expand the scope in several directions, in addition to the study that is directly parallel to that of [23].

1. 1.

   We consider the possibility of limiting the number of levels $\{w_{t}\}$ to be finite (e.g., binary, ternary, etc.), with the motivation of significantly reducing the number of multiplications needed to calculate the correlation, $\sum_{t}w_{t}Y_{t}$.

2. 2.

   We jointly optimize both the signal $\{s_{t}\}$ and the correlator, $\{w_{t}\}$. Interestingly, here both the optimal signal and the optimal correlation weights turn out to have a finite number of levels even if this number is not restricted a-priori. The number of levels depends on the PDF of $Z_{t}$, and it is typically very small (e.g., two to four levels). Moreover, the optimal $\{s_{t}\}$ and $\{w_{t}\}$ turn out to be proportional to each other, in contrast to the non-linear relation resulting when only $\{w_{t}\}$ is optimized while $\{s_{t}\}$ is given.

3. 3.

   We outline an extension to a wider class of detectors that are based on linear combinations of the correlation, $\sum_{t}w_{t}Y_{t}$, and the energy, $\sum_{t}Y_{t}^{2}$, with the motivation that it is, in fact, the structure of the optimal detector when $Z_{t}$ is Gaussian noise, and that it is reasonable regardless, since the under ${\cal H}_{1}$ the power (or the variance) of the received signal is larger than under ${\cal H}_{0}$.¹¹1In fact, when $s_{t}\equiv 0$, the correlation term becomes useless altogether and the energy term becomes necessary. We also address the possibility of replacing the energy term by the sum of absolute values, $\sum_{t}|Y_{t}|$, which is another measure of signal intensity, with the practical advantage that its calculation does not require multiplications.

The outline of the remaining part of this work is as follows. In Section 2, we formalize the problem rigorously and spell out our basic assumptions. In Section 3, we characterize the optimal correlator, $\{w_{t}^{*}\}$, for a given signal, $\{s_{t}\}$, subject to the power constraint. In Section 4, we address the problem of joint optimization of both $\{w_{t}\}$ and $\{s_{t}\}$, both under power constraints, and finally in Section 5, we outline extensions to wider classes of detectors that are based on correlation and energy.

Consider the signal detection model described in the fifth paragraph of the Introduction. We assume that $Z_{1},\ldots,Z_{n}$ are independent copies of a zero–mean random variable (RV), $Z$, that has a symmetric²²2The symmetry assumption is imposed mostly for convenience, but the results can be extended to address also non-symmetric PDFs. PDF, $f_{Z}(z)$, around the origin, and that it has a finite cumulant generating function (CGF),

at least in a certain interval of the real valued variable $v$. Note that since $f_{Z}(\cdot)$ is assumed symmetric around the origin, then so is $C(\cdot)$. We also assume that $C(\cdot)$ is twice differentiable within the range it exists. It is well known to be a convex function, because its second derivative cannot be negative, as it can be viewed as the variance of $Z$ under the PDF that is proportional to $f_{Z}(z)e^{vz}$. Further assumptions on $Z$ and its CGF will be spelled out in the sequel, at the places they will be needed. The following simple special cases will accompany our derivations and discussions repeatedly in the sequel:

The signal vector, $\mbox{\boldmath$s$}=(s_{1},\ldots,s_{n})$, $s_{t}\in{\rm I\!R}$, $t=1,\ldots,n$, is assumed known, and we denote its power by $P(\mbox{\boldmath$s$})$, that is,

Consider the class of correlation detectors, i.e., detectors that compare the correlation, $\sum_{t=1}^{n}w_{t}Y_{t}$, to a certain threshold $T$, where $\mbox{\boldmath$w$}=(w_{1},\ldots,w_{n})$ is a vector of real valued correlator coefficients, henceforth referred to as the correlator, for short. The decision rule is as follows: If $\sum_{t=1}^{n}w_{t}Y_{t}<T$, accept the null hypothesis, ${\cal H}_{0}$, otherwise, accept the alternative, ${\cal H}_{1}$. The threshold, $T$, controls the trade-off between the FA probability and the MD probability of the detector. To allow exponential decay (as $n$ grows without bound) of both types of error probabilities, we let $T$ vary linearly with $n$, and denote $T=\theta n$, where $\theta$ is a real valued constant, independent of $n$.

In order to have a well-defined asymptotic FA exponent, we assume that the correlator, $w$, has a fixed power,

which is independent of $n$, or, more generally, that the right–hand side (RHS) of eq. (9) tends to a certain fixed positive power level, as $n\to\infty$ (otherwise, the normalized logarithm of the FA probability would oscillate indefinitely, without a limit). Indeed, the FA probability of the correlation detector is given by

where $Q$ is the well-known $Q$-function,

and $\stackrel{{\scriptstyle\cdot}}{{=}}$ denotes equivalence in the exponential scale, in other words, the notation, $a_{n}\stackrel{{\scriptstyle\cdot}}{{=}}b_{n}$, for two positive sequences $\{a_{n}\}$ and $\{b_{n}\}$, means that $\lim_{n\to\infty}\frac{1}{n}\log\frac{a_{n}}{b_{n}}=0$. It follows from (10) that the FA exponent is given by

Thus, the FA exponent depends on $w$ only via $P(\mbox{\boldmath$w$})$. It follows that for a given $\theta$, if we wish to achieve a given, prescribed FA exponent, $E_{\mbox{\tiny FA}}(\theta)\geq E_{\mbox{\tiny FA}}$ (where $E_{\mbox{\tiny FA}}$ is a given positive number), we must have

In other words, a constraint on the FA exponent means a corresponding constraint on the asymptotic power of $w$ to be no larger than $P_{w}$.

In order to have a well–defined MD exponent, our assumptions concerning the asymptotic behavior of $w$ and $s$ will have to be more restrictive: We will assume that as $n\to\infty$, the pairs $\{(w_{t},s_{t})\}_{t=1}^{n}$ obey a certain joint PDF, $f_{WS}(w,s)$, in the following sense: For every $\lambda\geq 0$,

where $\mbox{\boldmath$E$}_{WS}\{\cdot\}$ denotes expectation with respect to (w.r.t.) $f_{WS}$. Whenever there is no room for confusion, the subscript $WS$ will be omitted and the expectation will be denoted simply by $\mbox{\boldmath$E$}\{\cdot\}$. The function $f_{WS}(\cdot,\cdot)$ will be referred to as the asymptotic empirical joint PDF of $w$ and $s$.³³3In the sequel, we will encounter one scenario where the asymptotic empirical PDF will be irrelevant, but this scenario will be handled separately, in the original domain of vectors of dimension $n$.

The MD probability is now upper bounded, exponentially tightly, by the Chernoff bound, as follows. Denoting the Gaussian random variable, $U\stackrel{{\scriptstyle\Delta}}{{=}}\sum_{t=1}^{n}w_{t}N_{t}$, we have

where the last step is due to the symmetry of the $C(\cdot)$. The resulting MD exponent is therefore given by

which is a functional of $f_{WS}$.

The problem of optimal correlator design for a given $s$, is equivalent to the problem of finding a conditional density, $f_{W|S}$, that maximizes the MD exponent subject to the power constraint, $\mbox{\boldmath$E$}\{W^{2}\}\leq P_{w}$. The problem of joint design of both $w$ and $s$ is asymptotically equivalent to the problem of maximizing the MD exponent over $\{f_{WS}\}$ subject to the power constraints, and $\mbox{\boldmath$E$}\{W^{2}\}\leq P_{w}$ and $\mbox{\boldmath$E$}\{S^{2}\}\leq P_{s}$, for some given $P_{s}>0$. The first problem is relevant when the detector designer has no control of the transmitted signal, for example, when the transmitter and the receiver are hostile parties, which is typically the case in military applications. The second problem is relevant when the transmitter and the receiver cooperate. In radar applications, for example, the transmitter and the receiver are the same party. In sections 3 and 4, we address the first problem and the second problem, respectively.

In view of the discussion in Section 2, we wish to find the optimal conditional density, $f_{W|S}$, in the sense of maximizing

subject to the power constraint,

At this stage, we carry out this optimization for a given $\lambda\geq 0$, but with the understanding that eventually, $\lambda$ will be subjected to optimization as well. To this end, let us denote the derivative of $C(v)$ by $\dot{C}(v)$, and for a given $\rho\geq 0$, define the function

Observe that since $C$ is convex, $\dot{C}$ is monotonically non-decreasing, and so, $g(\cdot|\rho,\lambda)$ is monotonically strictly increasing, which in turn implies that it has an inverse. We denote the inverse of $g(\cdot|\rho,\lambda)$ by $g^{-1}(\cdot|\rho,\lambda)$. Also, since $Z$ is assumed zero mean, then $\dot{C}(0)=0$, and hence also $g(0|\rho,\lambda)=0$ and $g^{-1}(0|\rho,\lambda)=0$. Note also that $g(\cdot|\rho,\lambda)$ (and hence also $g^{-1}(\cdot|\rho,\lambda)$) is a linear function if and only if $Z$ is Gaussian. The following lemma characterizes the optimal $f_{W|S}$.

The theorem tells that the best correlator, $\mbox{\boldmath$w$}^{*}=(w_{1}^{*},\ldots,w_{n}^{*})$, for a given $\mbox{\boldmath$s$}=(s_{1},\ldots,s_{n})$, is obtained by the relation,

which means that $w_{t}^{*}$ is given by a function of $s_{t}$, which is non-linear unless $Z$ is Gaussian. To gain an initial insight regarding the condition on $\rho$, consider the Gaussian example (Case 1, eq. (4)). In this case, $g(W|\rho,\lambda)=[(\sigma_{N}^{2}+\sigma_{Z}^{2})\lambda+\rho/\lambda]W$, and so, $g^{-1}(S|\rho,\lambda)=\lambda S/[(\sigma_{N}^{2}+\sigma_{Z}^{2})\lambda^{2}+\rho]$, whose power is $P_{w}$ for $\rho=\lambda\sqrt{\mbox{\boldmath$E$}\{S^{2}\}/P_{w}}-(\sigma_{N}^{2}+\sigma_{Z}^{2})\lambda^{2}$, which is non-negative as long as $P_{w}\leq\mbox{\boldmath$E$}\{S^{2}\}/[(\sigma_{N}^{2}+\sigma_{Z}^{2})^{2}\lambda]$. In general, the exact choice of $P_{w}$ is not crucial, as the prescribed FA exponent can be achieved by adjusting $\theta$ proportionally to $\sqrt{P_{w}}$. However, once $P_{w}$ is chosen, we will keep it fixed throughout (see Comment 1 above).

Suppose, more generally, that $\{w_{t}\}$ is constrained to take on values in a finite set whose cardinality $k$ is fixed, independent of $n$. This can be considered as a compromise between the above two extremes of performance and computational complexity, since the number of multiplications need not be larger than $k-1$. The design of such a signal is very similar to the scalar quantizer design problem: A finite–alphabet signal $w_{t}$ is defined as follows. Let $s_{\min}\equiv a_{0}<a_{1}<\ldots<a_{k-1}<a_{k}\equiv s_{\max}$, where $s_{\min}=\min_{t}s_{t}$, $s_{\max}=\max_{t}s_{t}$, and let ${\cal I}_{i}\stackrel{{\scriptstyle\Delta}}{{=}}[a_{i},a_{i+1})$, $i=0,1,\ldots,k-1$, be given. Define

for some given $\omega_{0},\omega_{1},\ldots,\omega_{k-1}$. We wish to minimize

over $\{a_{i}\}$, $i=1,\ldots,k-1$, and $\{\omega_{i}\}$, $i=0,1,\ldots,k-1$. The necessary conditions for optimality are obtained by equating to zero all partial derivatives w.r.t. $\{a_{i}\}$, $i=1,\ldots,k-1$, and $\{\omega_{i}\}$, $i=0,1,\ldots,k-1$. This results in the following sets of equations:

Alternatively, we may represent these equations as:

where $\rho$ is tuned such that

as before. The first set of equations is parallel to the nearest-neighbor condition in optimal quantizer design, and the second set corresponds to the centroid condition. Optimal signal design can be conducted iteratively, like in quantizer design, by alternating between the two sets of equations.

If $\{s_{t}\}$ is itself a finite–alphabet signal, then the optimal $\{w_{t}^{*}\}$ is also a finite-alphabet signal with the same alphabet size, even without restricting it to be so in the first place. If this alphabet is small enough and/or there is a strong degree of symmetry, one might as well optimize the levels of $\{w_{t}\}$ directly subject to the power constraint. Consider, for example, the case of a 4-ASK signal, $s_{t}\in\{-3a,-a,+a,+3a\}$, for some given $a>0$. Then, since the PDF of $Z$ is assumed symmetric, the alphabet of the optimal $\{w_{t}\}$ must be of the form $\{-\beta,-\alpha,+\alpha,+\beta\}$ for some $0<\alpha<\beta$. Assuming that $s_{t}=\pm a$ along half of the time and $s_{t}=\pm 3a$ along the other half, then $w_{t}=\pm\alpha$ and $w_{t}=\pm\beta$ in the corresponding halves, and so, $\frac{1}{2}\alpha^{2}+\frac{1}{2}\beta^{2}=P_{w}$, or $\beta=\sqrt{2P_{w}-\alpha^{2}}$. Thus, the MD exponent should be maximized over one parameter only (beyond the optimization over $\lambda$), which is $\alpha\in[0,\sqrt{2P_{w}}]$. In particular,

We next examine this expression in several examples.