Convex Optimization 2026, 28 - Optimal Detector Design

A random variable X with values in {1, ..., n} with distribution depending on a parameter θ in {1, ..., m} is distributed for the m possible values of θ and as such represented by a matrix P ∈ ℝ^{n × m}; p_kj prob(X = k | θ = j). The values of θ are hypotheses, and guessing which of them is correct is hypothesis testing (or detection) (p. 364) A deterministic detector is a function ψ from {1, ..., n} to {1, ..., m}. If X has value k, then the guess would be θ' = ψ(k). A generalization is a randomized detector, mapping onto a random variable in the target set, with a distribution depending on the observed value of X. A randomized detector is defined in terms of a matrix T with t_ik = prob(θ' = i | X = k). If X = k, then θ' = i with probability t_ik (7.3.1). The randomized detector defined by T, the detection probability matrix is D = TP, D_ij = (TP)_ij = prob(θ' = i | θ = j). The vector P^d containing D_ii are the detection probabilities and their complements 1 - D_ii form the error probabilities P^e (7.3.2). A wide variety of objectives for detector design are linear, affine or convex piecewise-linear functions of D, and hence of T. Some LPs emerging from the optimal detector design problems have simple solutions. A lower bound can be imposed on the probability of correctly detecting the j-th hypothesis P^d_j = D_jj ≥ L_j. Similar for upper bounds. A minimax error probability max_jP_j^e is piecewise-linear convex w.r.t. D. Minimizing it expressible as an LP (p. 367). A Bayes detector requires a prior distribution for the hypotheses q ∈ ℝ^m; q_i = prob(θ = i). It solves the LP minimizing q^TP^e (p. 367). Assuming the order of values θ is significant, the solution θ = i can be interpreted as a larger value of the parameter than θ = j; i > j. Given prob(θ' > θ | θ = i) which is the probability that we overestimate θ = i; which is an affine function of D prob(θ' > θ | θ = i) = ∑_{j > i}D_ji. Maximum allowable values for it can be expressed as a linear inequality on D (p. 368). The optimal detector design problem can be considered a multicriterion problem with linear equality and inequality constraints of T, and the m(m - 1) objectives given by the off-diagonal entries of D, with probabilities of the different types of detection error minimizing D_ij. Each objective D_ij is a linear function of the variables, which is a multicriterion linear program. We can scalarize the multicriterion problem through the weighted sum objective ∑^m_{i, j = 1}W_ijD_ij = tr(W^TD) with weight matrix W; given W_ii = 0. It's also referred to as the loss matrix. Pareto optimal point for the multicriterion problem forms the scalar optimization problem minimizing tr(W^TD) under t_k ⪰ 0, which is an LP, separable in its variables t_k. The objective is expressed as a sum of linear functions of t_k (p. 369). The Bayes detector design with prior distribution q has a mean probability of error q^TP^e = ∑^m_{i, j = 1}W_ijD_ij. The Bayes optimal detector is given by the deterministic detector (p. 370, 7.3.4).

Considering the case where the distribution of X is unknown, but prior information is known, defining a set of possible distributions. With a randomized detector, the detection probability matrix D depends on the particular value of P, which judges the error probabilities by their worst-case values over any distribution of ℙ. The worst case detection probability matrix is D^wc_ij = sup_{P ∈ ℙ} D_ij and D^wc_ii = inf_{P ∈ ℙ} D_ii. The off-diagonal gives the smallest possible probability of detection over P. The largest probability of error P^wce_i is equal to 1 - D^wc_ii. With these quantities one can define robust minimax detectors, such as the robust minimax detector max_i P_i^wce = 1 - min_i inf_{P ∈ ℙ}(TP)_ii, which minimizes the worst possible probability of error over all hypotheses (p. 372). If the set of possible distributions is finite, this problem can be solved with a piecewise linear and concave objective. Alternatively, the robust minimax detector can be written as an LP if ℙ is a polyhedron with linear equality and inequality constraints (7.3.6).