11.6.2    UMP Detection with Both Composite Hypotheses

We now consider the more general case where both the hypotheses are composite. The UMP optimization problem can be stated as:

$\text{Maximize}{\text{P}}_{\text{D}}\left(\tilde{\delta };\theta \right),\text{for}\text{all}\theta \in {\text{Λ}}_1,\text{subject}\text{to}\underset{\theta \in {\text{Λ}}_0}{\text{sup}}{\text{P}}_{\text{F}}\left(\tilde{\delta };\theta \right)\le \alpha .$

(11.21)

If a UMP test δ̃_UMP exists, then it must satisfy the following conditions. First,

$\underset{{\theta }_0\in {\text{Λ}}_0}{\text{sup}}{\text{P}}_{\text{F}}\left({\tilde{\delta }}_{\text{UMP}};{\theta }_0\right)\le \alpha .$

(11.22)

Second, for any δ̃ ∈ Δ̃ that satisfies ${\sup }_{{\theta }_0\in {\text{Λ}}_0}{\mathrm{P}}_F\left(\tilde{\delta };{\theta }_0\right)\le \alpha$ we must have

${\text{P}}_{\text{D}}\left(\tilde{\delta };{\theta }_1\right)\le {\text{P}}_{\text{D}}\left({\tilde{\delta }}_{\text{UMP}};{\theta }_1\right)\text{for}\text{all}{\theta }_1\in {\text{Λ}}_1.$

(11.23)

The following example illustrates a case where a UMP solution can be found. Also see Exercises 11.9.12 and 11.9.13.

Example 11.6.4. Testing Between Two One-Sided Composite Signals in Gaussian Noise. This is an extension of Example 11.6.1 in which the observation is Y = θ+Z, with Z ~ $\mathcal{N}$(0, σ²), and we are testing

$H_0:\theta \in {\text{Λ}}_0=\left[0,1\right]\text{versus}{H}_1:\theta \in {\text{Λ}}_1=\left(1,\infty \right).$

For fixed θ₀ ∈ Λ₀ and θ₁ ∈ Λ₁, $L_{{\theta }_0,{\theta }_1}\left(y\right)$ has no point masses under ${\mathrm{P}}_{{\theta }_0}$ or ${\mathrm{P}}_{{\theta }_1}$, and therefore δ̃_NP(y; θ₀, θ₁) is a deterministic LRT:

${\delta }_{\text{NP}}\left(y:{\theta }_0,{\theta }_1\right)=\{\begin{array}{lll}1\hfill & \text{if}\hfill & L_{{\theta }_0,{\theta }_1}\left(y\right)\ge \eta \left({\theta }_0,{\theta }_1\right)\hfill \\ 0\hfill & \text{if}\hfill & L_{{\theta }_0,{\theta }_1}\left(y\right)<\eta \left({\theta }_0,{\theta }_1\right)\hfill \end{array}=\{\begin{array}{lll}1\hfill & \text{if}\hfill & y\ge {\eta }^{\prime }\left({\theta }_0,{\theta }_1\right)\hfill \\ 0\hfill & \text{if}\hfill & y<{\eta }^{\prime }\left({\theta }_0,{\theta }_1\right)\hfill \end{array}$

where η′(θ₀, θ₁) is given by

${\eta }^{\prime }\left({\theta }_0,{\theta }_1\right)=\frac{{\sigma }^2\log \eta \left({\theta }_0,{\theta }_1\right)}{{\theta }_1-{\theta }_0}+\frac{{\theta }_0+{\theta }_1}{2}.$

Now in order to set the threshold η′ to meet the constraint on P_F given in (11.21), we first compute:

${\text{P}}_{\text{F}}\left({\delta }_{{\eta }^{\prime }};{\theta }_0\right)={\text{P}}_{{\theta }_0}\left\{Y\ge {\eta }^{\prime }\right\}=Q\left(\frac{{\eta }^{\prime }-{\theta }_0}{\sigma }\right)$

and note that this probability is an increasing function in θ₀. Therefore

$\underset{{\theta }_0\in \left[0,1\right]}{\text{sup}}{\text{ P}}_{\text{F}}\left({\delta }_{{\eta }^{\prime }};{\theta }_0\right)=Q\left(\frac{{\eta }^{\prime }-1}{\sigma }\right)$

and we can meet the P_F constraint with equality by setting η′ such that:

$Q\left(\frac{{\eta }^{\prime }-1}{\sigma }\right)=\alpha \Rightarrow {{\eta }^{\prime }}_{\alpha }=\sigma Q^{-1}\left(\alpha \right)+1.$

Note that η′_α is independent of θ₀ and θ₁. Define the test

${\delta }_{{{\eta }^{\prime }}_{\alpha }}\left(y\right)=\{\begin{array}{lll}1\hfill & \text{if}\hfill & y\ge {{\eta }^{\prime }}_{\alpha }\hfill \\ 0\hfill & \text{if}\hfill & y<{{\eta }^{\prime }}_{\alpha }\hfill \end{array}.$

We will now establish that ${\delta }_{{{\eta }^{\prime }}_{\alpha }}$ is a UMP test, by showing that conditions (11.22) and (11.23) hold. By construction,

$\underset{{\theta }_0\in \left[0,1\right]}{\text{sup}}{\text{ P}}_{\text{F}}\left({\delta }_{{{\eta }^{\prime }}_{\alpha }};{\theta }_0\right)={\text{P}}_{\text{F}}\left({\delta }_{{{\eta }^{\prime }}_{\alpha }};1\right)=\alpha$

and so (11.22) holds. Also, ${\delta }_{{{\eta }^{\prime }}_{\alpha }}$ is an a-level N-P test between the simple hypotheses H₀ : θ = 1 and H₁ : θ = θ₁, and being independent of θ₁, it is an α-level N-P test between these hypotheses for all θ₁ ∈ (1, ∞). Now, consider any test δ̃ ∈ Δ̃ that satisfies sup_{θ∈[0, 1]} P_F(δ̃; θ) ≤ α. Then clearly it is also true that P_F(δ̃; 1) ≤ α. This means that δ̃ is an α-level test for testing the simple hypotheses H₀ : θ = 1 versus H₁ : θ = θ₁, and it cannot be more powerful than ${\delta }_{{{\eta }^{\prime }}_{\alpha }}$, i.e.,

${\text{P}}_{\text{D}}\left(\tilde{\delta };{\theta }_1\right)\le {\text{P}}_{\text{D}}\left({\delta }_{{{\eta }^{\prime }}_{\alpha }};{\theta }_1\right)\text{for}\text{all}{\theta }_1\in \left(1,\infty \right).$

Therefore (11.23) holds and we have:

${\delta }_{\text{UMP}}\left(y\right)={\delta }_{{{\eta }^{\prime }}_{\alpha }}\left(y\right)=\{\begin{array}{lll}1\hfill & \text{if}\hfill & y\ge \sigma Q^{-1}\left(\alpha \right)+1\hfill \\ 0\hfill & \text{if}\hfill & y<\sigma Q^{-1}\left(\alpha \right)+1\hfill \end{array}.$

Again, while the test δ_UMP is independent of the θ₁, the performance of the test in terms of the P_D depends on θ₁. In particular

${\text{P}}_{\text{D}}\left({\delta }_{\text{UMP}};{\theta }_1\right)={\text{P}}_{\theta }\left\{Y\ge \sigma Q^{-1}\left(\alpha \right)+1\right\}=Q\left(Q^{-1}\left(\alpha \right)-\frac{{\theta }_1-1}{\sigma }\right).$

□

11.6.3    Generalized Likelihood Ratio (GLR) Detection

While it is always desirable to have a UMP solution to the composite hypothesis testing problem, such solutions rarely exist in practice, especially in situations where both hypotheses are composite. One approach to generating a good test when UMP solutions do not exist is through the use of a “GLR” defined by

$T_{\text{GLR}}\left(y\right)=\frac{{\sup }_{{\theta }_1\in {\text{Λ}}_1}{p}_{{\theta }_1}\left(y\right)}{{\sup }_{{\theta }_0\in {\text{Λ}}_0}{p}_{{\theta }_0}\left(y\right)}.$

It is important to note that the maximization over θ₀ and θ₁ has to be performed for each realization of the observation y, and so this test statistic is considerably more complex that the LRT. Also the result of the maximization may not produce a PDF (or PMF) in the numerator and denominator. We can use the statistic T_GLR(y) to produce a test, which is called the “generalized likelihood ratio test (GLRT)”:

${\tilde{\delta }}_{\text{GLRT}}\left(y\right)=\{\begin{array}{lll}1\hfill & \text{if}\hfill & T_{\text{GLRT}}\left(y\right)>\eta \hfill \\ 1\text{w}\text{.p}\text{.γ}\hfill & \text{if}\hfill & T_{\text{GLRT}}\left(y\right)=\eta .\hfill \\ 0\hfill & \text{if}\hfill & T_{\text{GLRT}}\left(y\right)<\eta \hfill \end{array}$

The use of the GLRT can be justified via an asymptotic analysis with a sequence of independent and identically distributed (i.i.d.) observations under each hypothesis, where it can be shown to have certain optimality properties. The maximization in numerator and denominator in T_GLR(y) can also be justified from the viewpoint of maximum likelihood parameter estimation [2].

Example 11.6.5. Detection of One-Sided Composite Signal in Cauchy Noise (continued). This problem was introduced in Example 11.6.3. The conditional PDF is given by

$p_{\theta }\left(y\right)=\frac{1}{\text{π}\left[1+{\left(y-\theta \right)}^2\right]}$

and we are testing H₀ : θ = 0 against the one-sided composite hypothesis H₁ : θ > 0. As we saw in Example 11.6.3, there is no UMP solution to this problem. The GLR statistic is given by

$T_{\text{GLR}}\left(y\right)=\frac{{\sup }_{\theta >0}{p}_{\theta }\left(y\right)}{p_0\left(y\right)}$

with

$\underset{\theta >0}{\sup }{p}_{\theta }\left(y\right)=\underset{\theta >0}{\sup }\frac{1}{\text{π}\left[1+{\left(y-\theta \right)}^2\right]}=\{\begin{array}{lll}\frac{1}{\text{π}}\hfill & \text{if}\hfill & y\ge 0\hfill \\ \frac{1}{\text{π}\left(1+y^2\right)}\hfill & \text{if}\hfill & y<0\hfill \end{array}.$

Thus

$T_{\text{GLR}}\left(y\right)=\{\begin{array}{lll}1+y^2\hfill & \text{if}\hfill & y\ge 0\hfill \\ 1\hfill & \text{if}\hfill & y<0\hfill \end{array}.$

To find an α-level test we need to evaluate P₀{T_GLR(Y) ≥ η}. Clearly

${\text{P}}_{\text{0}}\left\{T_{\text{GLR}}\left(y\right)\ge \eta \right\}=1\text{for}0\le \eta <1.$

For η ≥ 1

${\text{P}}_{\text{0}}\left\{T_{\text{GLR}}\left(Y\right)\ge \eta \right\}={\displaystyle {\int }_{\sqrt{\eta -1}}^{\infty }\frac{1}{\text{π}}\frac{1}{1+y^2}dy=0.5}-\frac{{\tan }^{-1}\left(\sqrt{\eta -1}\right)}{\text{π}}.$

There is a point of discontinuity in P₀{T_GLR(Y) ≥ η} at η = 1 as the value drops from 1 to the left to 0.5 to the right. For α ∈ (0.5, 1], we would need to randomize to meet the P_F constraint with equality. For α ∈ (0, 0.5], which would be more relevant in practice, the GLRT is a deterministic test:

${\delta }_{\text{GLRT}}\left(y\right)=\{\begin{array}{lll}1\hfill & \text{if}\hfill & T_{\text{GLR}}\left(y\right)\ge {\eta }_{\alpha }\hfill \\ 0\hfill & \text{if}\hfill & T_{\text{GLR}}\left(y\right)<{\eta }_{\alpha }\hfill \end{array}$

where

${\eta }_{\alpha }={\left[\tan \left(\text{π}\left(0.5-\alpha \right)\right)\right]}^2+1.$

□

11.6.4    Locally Most Powerful (LMP) Detection

Another approach to finding good detectors in cases where UMP tests do not exist is via a local optimization approach, which works when only one of the hypotheses is composite. Consider the scenario where Y ~ P_θ, we are interested in testing H₀ : θ = θ₀ versus H₁ : θ > θ₀, and there is no UMP solution. Also, suppose that θ takes values close to θ₀ under H₁; this might occur in practice in the detection of weak signals with unknown amplitude in noise.

Fix θ > θ₀ and let δ̃_θ be an α-level N-P test between θ and θ₀. Then assuming that P_D(δ̃_θ; θ) is differentiable with respect to θ, we can write the Taylor series approximation:

$\begin{array}{l}{\text{P}}_{\text{D}}\left({\tilde{\delta }}_{\theta };\theta \right)={\text{P}}_{\text{D}}\left({\tilde{\delta }}_{{\theta }_0};{\theta }_0\right)+\left(\theta -{\theta }_0\right)\frac{\partial }{\partial \theta }{\text{P}}_{\text{D}}\left({\tilde{\delta }}_{\theta };\theta \right)|{}_{\theta ={\theta }_0}+\left(\theta -{\theta }_0\right)\\ \approx \alpha +\left(\theta -{\theta }_0\right)\frac{\partial }{\partial \theta }{\text{P}}_{\text{D}}\left({\tilde{\delta }}_{\theta };\theta \right)|{}_{\theta ={\theta }_0}.\end{array}$

The locally optimal criterion can described as:

$\text{Maximize}\frac{\partial }{\partial \theta }{\text{P}}_{\text{D}}\left({\tilde{\delta }}_{\theta };\theta \right)|{}_{\theta ={\theta }_0}\text{subject}\text{to}{\text{P}}_{\text{F}}\left(\tilde{\delta };{\theta }_0\right)\le \alpha$

(11.24)

the idea being that maximizing P_D should be approximately the same as maximizing the slope of P_D at θ = θ₀ for values of θ close to θ₀. Now

${\text{P}}_{\text{D}}\left({\tilde{\delta }}_{\theta };\theta \right)={\displaystyle {\int }_y{\mathbb{I}}_{\left\{\tilde{\delta }\left(y\right)=1\right\}}}{p}_{\theta }\left(y\right)\mu \left(dy\right).$

Assuming that p_θ (y) is differentiable in θ

$\frac{\partial }{\partial \theta }{\text{P}}_{\text{D}}\left({\tilde{\delta }}_{\theta };\theta \right)|{}_{\theta ={\theta }_0}={\displaystyle {\int }_y{\mathbb{I}}_{\left\{\tilde{\delta }\left(y\right)=1\right\}}}\frac{\partial }{\partial \theta }{p}_{\theta }\left(y\right)|{}_{\theta ={\theta }_0}\mu \left(dy\right).$

Therefore, the solution to the locally optimal detection problem of (11.24) can be seen as being equivalent to N-P testing between $p_{{\theta }_0}\left(y\right)$ and

$\frac{\partial }{\partial \theta }{p}_{\theta }\left(y\right)|{}_{\theta ={\theta }_0}.$

Even though the latter quantity is not necessarily a PDF (or PMF), the steps that we followed in deriving the N-P solution in Section 11.4 can be repeated to show that the solution to (11.24) has the form:

${\tilde{\delta }}_{\text{LMP}}\left(y\right)=\{\begin{array}{lll}1\hfill & \text{if}\hfill & T_{\text{lo}}\left(y\right)>\eta \hfill \\ 1\text{w}\text{.p}\text{γ}\hfill & \text{if}\hfill & T_{\text{lo}}\left(y\right)=\eta \hfill \\ 0\hfill & \text{if}\hfill & T_{\text{lo}}\left(y\right)<\eta \hfill \end{array}$

where

$T_{\text{lo}}\left(y\right)=\frac{\frac{\partial }{\partial \theta }{p}_{\theta }\left(y\right)|{}_{\theta ={\theta }_0}}{p_{{\theta }_0}\left(y\right)}.$

Example 11.6.6. Detection of One-Sided Composite Signal in Cauchy Noise (continued). This problem was introduced in Example 11.6.3, and we saw that there was no UMP solution. We studied the GLRT in Example 11.6.5, and now we examine the LMP solution.

$p_{\theta }\left(y\right)=\frac{1}{\text{π}\left[1+{\left(y-\theta \right)}^2\right]}\Rightarrow \frac{\partial }{\partial \theta }{p}_{\theta }\left(y\right)|{}_{\theta =0}=\frac{2y}{\text{π}{\left(1+y^2\right)}^2}$

Thus

$T_{\text{lo}}\left(y\right)=\frac{2y}{1+y^2}$

and

${\tilde{\delta }}_{\text{LMP}}\left(y\right)=\{\begin{array}{lll}1\hfill & \text{if}\hfill & T_{\text{lo}}\left(y\right)\ge \eta \hfill \\ 0\hfill & \text{if}\hfill & T_{\text{lo}}\left(y\right)<\eta \hfill \end{array}.$

Randomization is not needed since T_lo(y) does not have point masses under P₀.

□

11.7    Binary Detection with Vector Observations

In the detection problems we have studied so far, we did not make any explicit assumptions about the observation space, although the examples were restricted to scalar observations. The theory that we have developed applies equally to scalar and vector observations. Nevertheless, it is useful to study the case of vector observations in more detail as such a study reveals aspects of detector structures that are useful in applications.

Consider the detection problem:

$H_0:Y\sim p_0\left(y\right)\text{versus}{H}_1:Y\sim p_1\left(y\right)$

where Y = [Y₁ Y₂ ⋯ Y_n]^⊤ and y = [y₁ y₂ ⋯ y_n]^⊤. The optimum detector for this problem, no matter which criterion (Bayes, Neyman-Pearson, minimax) we choose, is of the form

${\tilde{\delta }}_{\text{OPT}}\left(y\right)=\{\begin{array}{lll}1\hfill & \text{if}\hfill & \log L\left(y\right)>\eta \hfill \\ 1\text{w}\text{.p}\text{.γ}\hfill & \text{if}\hfill & \log L\left(y\right)=\eta \hfill \\ 0\hfill & \text{if}\hfill & \log L\left(y\right)<\eta \hfill \end{array}$

(11.25)

where L(y) = p₁(y)/p₀(y) is the likelihood ratio, and taking the log of L(y) does not affect the structure of the test since log is a monotonic function. The threshold η and randomization parameter γ are chosen based on the criterion used for detection. Of course, in the Bayesian setting, η = log τ, with τ given in (11.11), and γ = 0.

11.7.1    Conditionally Independent Observations

Consider the special case where the observations are (conditionally) independent under each hypothesis. In this case

$p_j\left(y\right)=\underset{k=1}{\overset{n}{{\displaystyle \text{Π}}}}{p}_{j,k}\left(y_k\right)$

and the log likelihood ratio in (11.25) can be written as

$\log L\left(y\right)={\displaystyle \sum _{k=1}^n\log }{L}_k\left(y_k\right)$

where L_k(y_k) = p_1,k(y_k)/p_0,k(y_k).

Example 11.7.1. Deterministic signals in i.i.d. noise. Here, the hypotheses are given by:

$H_0:Y=s_0+Z\text{versus}{H}_1:Y=s_1+Z$

where s₀ and s₁ are deterministic vectors (signals) and Z₁, Z₂, …, Z_n are i.i.d. random variables with zero mean and density given by p_Z. Hence, the log likelihood ratio in (11.25) can be written as:

$\log L\left(y\right)={\displaystyle \sum _{k=1}^n\log }\frac{p_Z\left(y_k-s_1{,}_k\right)}{p_Z\left(y_k-s_0{,}_k\right)}.$

A special case of this example is one where Z is a vector of i.i.d. $\mathcal{N}$(0, σ²) random variables, in which case (based on the more general result derived in the following section), we can show that the optimum detector structure is of the form:

${\delta }_{\text{OPT}}\left(y\right)=\{\begin{array}{lll}1\hfill & \text{if}\hfill & {\left(s_1-s_0\right)}^{\top }y\ge \eta \hfill \\ 0\hfill & \text{if}\hfill & {\left(s_1-s_0\right)}^{\top }y<\eta \hfill \end{array}.$

□

11.7.2    Deterministic Signals in Correlated Gaussian Noise

In general, the detection problem with vector observations that are conditionally dependent, given the hypothesis, does not admit any special structure beyond what is described in (11.25). However, in some special cases, we can simplify the expression for the log likelihood ratio to obtain some more insight into the detector structure. In this section, we consider the example of detecting deterministic signals in correlated Gaussian noise, for which the hypotheses are described by:

$H_0:Y=s_0+Z\text{versus}{H}_1:Y=s_1+Z$

with s₀ and s₁ being deterministic signals as in Example 11.7.1, and Z is a Gaussian vector with zero mean and covariance matrix Σ, denoted by Z ~ $\mathcal{N}$(0, Σ). In this case

$p_j\left(y\right)=\frac{1}{\sqrt{{\left(2\text{π}\right)}^n\left|\text{Σ}\right|}}\exp \left\{-\frac{1}{2}{\left(y-s_j\right)}^{\top }{\text{Σ}}^{-1}\left(y-s_j\right)\right\}.$

where ∣Σ∣ is the absolute value of the determinant of Σ. Therefore

$\log L\left(y\right)-\log \frac{p_1\left(y\right)}{p_0\left(y\right)}={\left(s_1-s_0\right)}^{\top }{\text{Σ}}^{-1}\left(y-\frac{s_1-s_0}{2}\right).$

Since log L(y) does not have any point masses under either hypothesis, the optimum detector is deterministic and has the form:

${\delta }_{\text{OPT}}\left(y\right)=\{\begin{array}{lll}1\hfill & \text{if}\hfill & T\left(y\right)\ge \eta \hfill \\ 0\hfill & \text{if}\hfill & T\left(y\right)<\eta \hfill \end{array}$

where T(y) = (s₁ − s₀)^⊤Σ⁻¹y and the η is chosen based on the detection criterion. In the special case of Bayesian detection,

$\eta =\log \tau +\frac{1}{2}{\left(s_1-s_0\right)}^{\top }{\text{Σ}}^{-1}\left(s_1+s_0\right)$

with τ given in (11.11).

If we define the pseudosignal s̃ by

$\tilde{s}\triangleq {\text{Σ}}^{-1}\left(s_1-s_0\right)$

then the test statistic T(y) can be written as:

$T\left(y\right)={\tilde{s}}^{\perp }y={\displaystyle \sum _{k=1}^n{\tilde{s}}_k{y}_k}.$

We see that the optimum detector is a correlation detector or matched filter [2].

Note that T(y) is linear in Y and hence has a Gaussian PDF under both H₀ and H₁. In particular,

${\text{E}}_j\left[T\left(Y\right)\right]={\tilde{s}}^{\top }{\tilde{s}}_j\triangleq {\tilde{\mu }}_j$

and

${\text{Var}}_j\left[T\left(Y\right)\right]=\text{Var}\left({\tilde{s}}^{\top }Z\right)={\tilde{s}}^{\top }{\text{Σ}}_{\tilde{s}}={\tilde{\mu }}_1-{\tilde{\mu }}_0\triangleq d^2$

where d² is called the Mahalanobis distance between the signals s₁ and s₀.

Based on the above characterization of T(y), we can conclude that the problem of deterministic signal detection in correlated Gaussian noise is equivalent to the following detection problem involving the scalar observation T(y):

$H_0:T\left(y\right)~\mathcal{N}\left({\tilde{\mu }}_0,d^2\right)\text{versus}{H}_1:T\left(y\right)~\mathcal{N}\left({\tilde{\mu }}_1,d^2\right).$

11.7.3    Gaussian Signals in Gaussian Noise

In this section we consider another important example involving dependent observations, that of detecting Gaussian signals in Gaussian noise. The hypotheses are described by:

$H_0:Y=S_0+Z\text{versus}{H}_{\text{1}}:Y=S_1+Z$

where S₀, S₁, and Z are jointly Gaussian random vectors. It is easy to see that this problem is equivalent to the following detection problem:

$H_0:Y~\mathcal{N}\left({\mu }_0,{\displaystyle {\sum }_0}\right)\text{versus}{H}_{\text{1}}:Y~\mathcal{N}\left({\mu }_1,{\displaystyle {\sum }_1}\right)$

(11.26)

for some vectors μ₀, μ₁, and covariance matrices Σ₀ and Σ₁. Note that

$p_j\left(y\right)=\frac{1}{\sqrt{{\left(2\text{π}\right)}^n\left|{\displaystyle {\sum }_j}\right|}}\exp \left\{-\frac{1}{2}{\left(y-{\mu }_j\right)}^{\top }{\displaystyle {\sum }_j^{-1}\left(y-{\mu }_j\right)}\right\}$

and therefore the log likelihood ratio is given by:

$\begin{array}{c}\log L\left(y\right)=\frac{1}{2}{y}^{\top }\left({\displaystyle {\sum }_0^{-1}-{\displaystyle {\sum }_0^{-1}}}\right)y+\left({\mu }_1^{\top }{\displaystyle {\sum }_1^{-1}-{\mu }_0^{\top }{\displaystyle {\sum }_0^{-1}}}\right)y\\ +\frac{1}{2}\left[\log \frac{\left|{\displaystyle {\sum }_0}\right|}{\left|{\displaystyle {\sum }_1}\right|}+{\mu }_0^{\top }{\displaystyle {\sum }_1^{\top }{\displaystyle {\sum }_1^{-1}{\mu }_1}}\right].\end{array}$

Thus, the optimum detector in general involves both a quadratic term as well as a linear term in y. If Σ₀ = Σ₁ and μ₀ ≠ μ₁, then the quadratic term vanishes and we have the detector structure we saw earlier for the detection of deterministic signals in Gaussian noise. If μ₀ = μ₁ = 0 and Σ₁ ≠ Σ₀, then the linear term vanishes and we have a purely quadratic detector.

Example 11.7.2. Signaling over Rayleigh Fading Channel with Random Phase. The following detection problem arises in the context of wireless communication systems, when the carrier phase is not known at the receiver:

$H_0:Y=Z\text{versus}{H}_1:Y=\left[\begin{array}{c}A\cos \varphi \\ A\sin \varphi \end{array}\right]+Z$

(11.27)

where Z ~ $\mathcal{N}$(0, σ²I), A is the fading amplitude that is Rayleigh distributed, and ϕ is the random phase that is uniformly distributed on [0, 2π]. The PDF of A is given by:

$p_A\left(a\right)=\frac{a}{v^2}\exp \left[-\frac{a^2}{2v^2}\right]{\mathbb{I}}_{\left\{a\ge 0\right\}}$

If we define the fading signal vector S to have components S₁ = A cos ϕ and S₂ = A sin ϕ, then it is not difficult to show that S₁ and S₂ are independent $\mathcal{N}$(0, ν²) random variables. Thus the hypothesis test of (11.27) reduces to:

$H_0:Y~\mathcal{N}\left(0,{\sigma }^{2}I\right)\text{versus}{H}_1:Y~\mathcal{N}\left(0,\left({\sigma }^2+v^2\right)I\right).$

This is a special case of (11.26) with μ₀ = μ₁ = 0, and Σ₀ = σ²I, Σ₁ = (σ² + ^ν2)I. Thus the log likelihood ratio has the form:

$\log L\left(y\right)=\left(\text{constant}\right)y^{\top }y+\left(\text{constant}\right)$

from which we can conclude that the optimum detector is of the form:

${\delta }_{\text{OPT}}\left(y\right)=\{\begin{array}{cc}1& \text{if}{y}^{\top }y\ge \eta \\ 0& \text{if}{y}^{\top }y\ge \eta \end{array}.$

The test statistic $Y^{\top }Y=Y_1^2+Y_2^2$ has an exponential distribution with mean 2σ² under H₀, and an exponential distribution with mean 2(σ² + ν²) under H₁. Thus, if we are interested in N-P detection, for an α-level test, we can set P₀{Y^⊤Y ≥ η_α] = α by setting

$\exp \left[\frac{\eta \alpha }{2{\sigma }^2}\right]=\alpha \Rightarrow {\eta }_{\alpha }=-2{\sigma }^2\log \alpha .$

The corresponding power of the test is given by:

${\text{P}}_{\text{D}}\left({\delta }_{\text{OPT}}\right)={\text{P}}_{\text{1}}\left\{Y^{T}Y\ge {\eta }_{\alpha }\right\}=\exp \left[-\frac{{\eta }_{\alpha }}{2\left({\sigma }^2+v^2\right)}\right]={\alpha }^{\frac{{\sigma }^2}{{\sigma }^2+v^2}}.$

□

11.8    Summary and Further Reading

This chapter covered the fundamentals of detection theory, with an emphasis on binary detection problems. In Section 11.1, we provided a general statistical decision theory framework for detection problems. In Section 11.2, Section 11.4, we introduced the three basic formulations for the binary detection problem: Bayesian, minimax, and Neyman-Pearson. We saw that in all cases the optimum detection rule is a LRT with possible randomization. In Section 11.5, Section 11.6, we studied composite detection problems where the distributions of the observations are not completely specified. In particular, we saw that Bayesian composite detection can be reduced to an equivalent simple detection problem. The Neyman-Pearson version of the composite detection problem is more interesting, and we studied various approaches to this problem, including UMP detection, GLR detection, and LMP detection. Finally, we examined the detection problem with vector observations in more detail, and discussed optimum detector structures for both the cases where the observations are conditionally independent and dependent, under each hypothesis.

This chapter was inspired by the textbook on detection and estimation theory by Poor [2]. While we focused almost exclusively on binary detection problems, extension to M-ary detection is straightforward at least in the Bayesian setting (see Exercise 11.9.6). More details on M-ary detection can be found in the books by Van Trees [3], Levy [4] and Kay [5]. An alternative formulation to the detection problem with incompletely specified distributions is the robust formulation of Huber [6]. Other extensions of detection theory include sequential [7] and quickest change detection [8], where observations are taken sequentially in time and decisions about the hypothesis need to be made online. Asymptotic performance analysis and design of detection procedures for large number of observations using tools from large deviations theory has been an active area of research (see, e.g., [9]). Finally, distributed sensor networks have generated interesting new directions for research in detection theory [10].

Acknowledgments

The writing of this chapter was supported in part by the U.S. National Science Foundation, under grant CCF-0830169, through the University of Illinois at Urbana-Champaign. The author would also like to thank Taposh Banerjee for help with the figures.

11.9    Exercises

Exercise 11.9.1. Consider the binary statistical decision theory problem for which $\mathcal{S}=\mathcal{D}=\left\{0,1\right\}$. Suppose the cost function is given by

$C\left(i,j\right)=\{\begin{array}{cc}0& \text{if}i=j\\ 1& \text{if}j=0,i=1\\ 10& \text{if}j=1,i=0\end{array}$

The observation Y takes values in the set Γ = {a, b, c} and the conditional p.m.f.’s of Y are:

$p_0\left(a\right)=p_0\left(b\right)=0.5p_1\left(a\right)=p_1\left(b\right)=0.25,p_1\left(c\right)=0.5$

1.  Is there a best decision rule based on conditional risks?

2.  Find Bayes (for equal priors) and minimax rules within the set of deterministic decision rules.

3.  Now consider the set of randomized decision rules. Find a Bayes rule (for equal priors). Also construct a randomized rule whose maximum risk is smaller than that of the minimax rule of part (b).

Exercise 11.9.2. For the binary hypothesis testing problem, with C_0,0 < C_1,0 and C_1,1 < C_0,1, show there is no “best” rule based on conditional risks, except in the trivial case case where p₀(y) and p₁(y) have disjoint supports.

Exercise 11.9.3. Let $\mathcal{S}$ = {0, 1}, and $\mathcal{D}$ = {0, 1, e}. This would correspond to binary communication with erasures. Now suppose

$p_j\left(y\right)=\frac{1}{\sqrt{2\text{π}\sigma }}\exp \left[-\frac{{\left(y-{\left(-1\right)}^{j+1}\right)}^2}{2{\sigma }^2}\right],j=0,1,-\infty <y<\infty .$

That is, Y has distribution $\mathcal{N}$(−1, σ²) when the state is 0, and Y has distribution $\mathcal{N}$(1, σ²) when the state is 1. Assume a cost structure

$C_{i,j}=\{\begin{array}{l}0\text{if}i=0,j=0\text{or}i=\text{1,}j=1\hfill \\ 1\text{if}i=1,j=0\text{or}i=\text{0,}j=1\hfill \\ c\text{if}i=e\hfill \end{array}$

Furthermore, assume that the two states are equally likely.

1.  First assume that c < 0.5. Show that the Bayes rule for this problem has the form:

${\delta }_B\left(y\right)=\{\begin{array}{l}0y\le -t\hfill \\ e-t<y<t\hfill \\ 1y\ge t\hfill \end{array}$

Also give an expression for t in terms of the parameters of the problem.

2.  Now find δ_B(y) when c ≥ 0.5.

Exercise 11.9.4. Consider the binary detection problem with

$p_1\left(y\right)=\{\begin{array}{cc}1/4& \text{if}y\in \left[0,4\right]\\ 00& \text{otherwise}\end{array}$

and

$p_0\left(y\right)=\{\begin{array}{cc}\left(y+3\right)/18& \text{if}y\in \left[-3,3\right]\\ 0& \text{otherwise}\end{array}$

1.  Find a Bayes rule for uniform costs and equal priors and the corresponding minimum Bayes risk.

2.  Find a minimax rule for uniform costs, and the corresponding minimax risk.

Exercise 11.9.5. For Exercise 11.9.2 above, find the minimum Bayes risk function V(π₀), and then find a minimax rule in the set of randomized decision rules using V(π₀).

Exercise 11.9.6. In this chapter, we formulated and solved the general Bayesian binary detection problem. We may generalize this formulation to M-ary detection (M > 2) as follows:

•  $\mathcal{S}$ = {0, …, M − 1}, with a priori probability of state j being π_j.

•  $\mathcal{D}$ = {0, …, M − 1}

•  C(i, j) = C_ij ≥ 0, for i, j = 0, …, M − 1.

•  $\mathcal{Y}$, the observation space being continuous/discrete with conditional density (PDF/PMF) p_j(y), j = 0, …, M − 1.

•  δ ∈ Δ, δ partitions $\mathcal{Y}$ into M regions $\mathcal{Y}$₀, …, $\mathcal{Y}$_M−1, where δ(y) = i when y ∈ $\mathcal{Y}$_i.

Find δ_B(y) by specifying the Bayes decision regions $\mathcal{Y}$_i, i = 0, …, M − 1. Simplify as much as possible.

Exercise 11.9.7. Consider the 5-ary detection problem in which the hypotheses are given by

$H_j:Y=\left(j-2\right)+Z,j=0,1,2,3,4,$

where Z ~ $\mathcal{N}$(0, 1). Assume that the hypotheses are equally likely.

1.  Find the decision rule with minimum probability of error (i.e., Bayes rule with uniform costs).

2.  Also find the corresponding minimum Bayes risk.

Hint: Find the probability of correct decision making first.

Exercise 11.9.8. Consider the binary detection problem with

$p_0\left(y\right)=\frac{1}{2}{e}^{-\left|y\right|}\text{and}{p}_1\left(y\right)=e^{-2\left|y\right|},y\in ℝ$

1.  Find the Bayes rule for equal priors and a cost structure of the form C₀₀ = C₁₁ = 0, C₁₀ = 1, and C₀₁ = 2.

2.  Find the Bayes risk for the Bayes rule of part (a). (Note that the costs are not uniform.)

3.  Find a Neyman-Pearson rule for α = 1/4.

4.  Find the probability of detection for the rule of part (c).

Exercise 11.9.9. Consider the detection problem for which Γ = {0, 1, 2, …} and the PMF’s of the observations under the two hypotheses are:

$p_0\left(y\right)=\left(1-{\beta }_0\right){\beta }_0^y,y=0,1,2,\dots$

and

$p_1\left(y\right)=\left(1-{\beta }_0\right){\beta }_1^y,y=0,1,2,\dots$

Assume that 0 < β₀ < β₁ < 1.

1.  Find the Bayes rule for uniform costs and equal priors.

2.  Find the Neyman-Pearson rule with false-alarm probability α ∈ (0, 1). Also find the corresponding probability of detection as a function of α.

Exercise 11.9.10. Consider a binary detection problem, where the goal is to minimize the following risk measure

$\rho \left(\tilde{\delta }\right)={\left[{\text{P}}_{\text{F}}\left(\tilde{\delta }\right)\right]}^2+{\text{P}}_{\text{M}}\left(\tilde{\delta }\right)$

1.  Show that the optimal solution is a (possibly randomized) likelihood-ratio test.

2.  Find the optimal solution for the observation model

$p_0\left(y\right)\{\begin{array}{cc}1& \text{if}y\in \left[0,1\right]\\ 0& \text{otherwise}\end{array}$

and

$p_1\left(y\right)\{\begin{array}{cc}2y& \text{if}y\in \left[0,1\right]\\ 0& \text{otherwise}\end{array}$

Exercise 11.9.11. Consider the detection problem where L(y) has no point masses under either hypothesis. Let δ_η denote the likelihood ratio test:

${\delta }_{\eta }\left(y\right)=\{\begin{array}{cc}1& \text{if}L\left(y\right)\ge \eta \\ 0& \text{if}L\left(y\right)<\eta \end{array}.$

As discussed in Section 11.4.2, a plot of P_D(δ_η) versus P_F(δ_η) for various values of η is called the ROC. This plot is a concave function with the point (0, 0) corresponding to η = ∞, and the point (1, 1) corresponding to η = 0. Prove the following properties of ROC’s:

1.  P_D(δ_η) ≥ P_F(δ_η) for all η. (Hint: consider cases η ≤ 1 and η > 1 separately.)

2.  The slope of the ROC at a particular point is equal to the value of the threshold η required to acheive the P_D and P_F at that point, i.e.,

$\frac{d{\text{P}}_{\text{D}}}{d{\text{P}}_{\text{F}}}=\eta .$

(Hint: Use the fact that L(Y) has a density under each hypothesis.)

Exercise 11.9.12. Consider the following composite detection problem with Λ = ℝ:

$H_0:\theta \le \tilde{\theta }\text{versus}{H}_{\text{1}}:\theta >\tilde{\theta }$

where θ̃ is a fixed real number. Now suppose that for each fixed θ₀ ≤ θ̃ and each fixed θ₁ > θ̃, we have

$\frac{p_{{\theta }_1}\left(y\right)}{p_{{\theta }_0}\left(y\right)}=g_{{\theta }_0,{\theta }_1}\left(T\left(y\right)\right)$

where the function T does not depend on θ₁ or θ₀, and the function $g_{{\theta }_0,{\theta }_1}$ is strictly increasing in its argument.

Show that for any level α, a UMP test between H₀ and H₁ exists.

Exercise 11.9.13. Consider the composite binary detection problem in which

$p_{\theta }\left(y\right)=\{\begin{array}{cc}\theta e^{-{\theta }_y}& \text{if}y\ge 0\\ 0& \text{if}y<0\end{array}$

1.  For α ∈ (0, 1), show that a UMP test of level α exists for testing the hypotheses

$H_0:{\text{Λ}}_{\text{0}}=\left[1,2\right]\text{versus}{H}_{\text{1}}:{\text{Λ}}_{\text{1}}=\left(2,\infty \right).$

Find this UMP test as a function of α.

2.  Find the structure of the generalized likelihood ratio test.

Exercise 11.9.14. (UMP testing with Laplacian Observations) Consider the composite binary detection problem in which

$p_{\theta }\left(y\right)=\frac{1}{2}{e}^{-\left|y-\theta \right|},y\in ℝ.$

and we are testing:

$H_0:\theta =0\text{versus}{H}_{\text{1}}:\theta >0$

1.  Does a UMP test exist? If so, find it for level α and derive its power P_D. If not, find the generalized likelihood ratio test for level α.

2.  Find a locally most powerful α-level test and derive its power P_D.

Exercise 11.9.15. Consider the detection problem:

$H_0:Y=\left[\begin{array}{c}-a\\ 0\end{array}\right]+Z\text{versus}{H}_1:Y=\left[\begin{array}{c}a\\ 0\end{array}\right]+Z$

where Z ~ $\mathcal{N}$(0, Σ) with

${\displaystyle \sum =}\left[\begin{array}{cc}1& \rho \\ \rho & 1+{\rho }^2\end{array}\right].$

Assume that a > 0 and ρ ∈ (0, 1).

1.  For equal priors show that the minimum-probability-of-error detector is given by

${\delta }_{\text{B}}\left(y\right)=\{\begin{array}{cc}1& \text{if}{y}_{\text{1}}-b{y}_2\ge \text{τ}\\ 0& \text{if}{y}_{\text{1}}-b{y}_2<\text{τ}\end{array}$

where b = ρ/(1 + ρ²) and τ = 0.

2.  Determine the minimum probability of error.

3.  Consider the test of part (a) in the limit as ρ → 0. Explain why the dependence on y₂ goes away in this limit.

4.  Now suppose the observations Y ~ $\mathcal{N}$([a 0]^⊤, Σ), with ρ = 1 but a being an unknown parameter, and we wish to test between the hypotheses:

$H_0:0<a<1\text{versus}{H}_1:a>1.$

Show that a UMP test exists for this problem, and find the UMP test of level α ∈ (0, 1).

Exercise 11.9.16. Consider the detection problem with n-dimensional observations:

$H_0:Y=Z\text{versus}{H}_{\text{1}}:Y=s+Z$

where the components of Z are zero mean correlated random variables with

$E\left[Z_k{Z}_{\mathit{\ell }}\right]={\sigma }^2{\rho }^{\left|k-\mathit{\ell }\right|},\text{for}\text{all}\text{1}\le k\text{,}\mathit{\ell }\le n$

where ∣ρ∣ < 1.

1.  Show that the N-P test for this problem has the form:

${\delta }_{\eta }\left(y\right)=\{\begin{array}{cc}1& \text{if}{\displaystyle {\sum }_{k=1}^n{b}_k{x}_k}\ge \eta \\ 0& \text{if}{\displaystyle {\sum }_{k=1}^n{b}_k{x}_k}<\eta \end{array}$

where b₁ = s₁/σ, x₁ = y₁/σ, and

$b_k=\frac{s_k-\rho s_{k-1}}{\sigma \sqrt{1-{\rho }^2}},x_k=\frac{y_k-\rho y_{k-1}}{\sigma \sqrt{1-{\rho }^2}},k=2,\dots ,n.$

Hint: Note that ${\displaystyle {\sum }_Z^{-1}=A/\left({\sigma }^2\left(1-{\rho }^2\right)\right)}$, where A is a tridiagonal matrix with main diagonal (1 1 + ρ² 1 + ρ² … 1 + ρ² 1) and superdiagonal and subdiagonal entries all being −ρ.

2.  Find the α-level N-P test, ${\delta }_{\eta }{}_{{}_{\alpha }}$.

3.  Find the ROC for the above detector, i.e., find P_D(δη_α) as a function of α.

Exercise 11.9.17. Consider the composite detection problem with twodimensional observations:

$H_0:Y=Z\text{versus}{H}_{\text{1}}:Y=\theta s+Z$

where Z₁ and Z₂ are independent $\mathcal{N}$(0, 1) random variables, and s₁ = 1 and s₂ = −1.

The parameter θ is a deterministic but unknown parameter that takes one of two possible values +1 or −1.

1.  Is there a UMP test for this problem? If so, find it for level a. If not, explain why not.

2.  Show that an α-level GLRT for this problem is given by:

${\delta }_{\text{GLRT}}\left(y\right)=\{\begin{array}{cc}1& \text{if}\left|y_1-y_2\right|\ge {\eta }_{\alpha }\\ 0& \text{othwerwise}\end{array}$

with ${\eta }_{\alpha }=\sqrt{2}{Q}^{-1}\left(\frac{\alpha }{2}\right)$.

3.  Give a clear argument to establish that the probability of detection for the GLRT of part (b) is independent of θ.

4.  Now find the probability of detection for the GLRT as a function of η_α.

References

[1]  Ferguson, T.S., Mathematical Statistics: A Decision Theoretic Approach. Academic Press, 1967.

[2]  Poor, H.V., An Introduction to Signal Detection and Estimation, second edition. Springer-Verlag, 1994.

[3]  Van Trees, H.L., Detection, Estimation and Modulation Theory, Part 1. Wiley, 1968.

[4]  Levy, B.C., Principles of Signal Detection and Parameter Estimation. Springer-Verlag, 2008.

[5]  Kay, S.M., Fundamentals of Statistical Signal Processing: Detection Theory. Prentice Hall, 1998.

[6]  Huber, P.J., Robust Statistics. Wiley, 1981.

[7]  Wald, A., Sequential Analysis. Wiley, 1947.

[8]  Poor, H.V. and Hadjiliadis, O., Quickest Detection. Cambridge University Press, 2009.

[9]  Dembo, A. and Zeitouni, O., Large Deviations Techniques and Applications, Second Edition. Springer-Verlag, 1998.

[10]  Varshney, P.K., Distributed Detection and Data Fusion. Springer-Verlag, 1997.

¹As will be the convention in the rest of the chapter, we denote random variables by uppercase letters and their corresponding realizations by lowercase letters. In particular, a realization of Y is denoted by y.

²This condition typically holds for continuous observations when p₀(y) and p₁(y) are PDF’s with the same support, but not necessarily even in this case.