Convex Optimization · Problem 7.11

Geometric problems — Boyd & Vandenberghe

Mathematics — Optimization · randomized-detectors-convex-combination

Problem

Randomized detectors. Show that every randomized detector can be expressed as a convex combination of a set of deterministic detectors: If

T = \begin{bmatrix} t_1 & t_2 & \cdots & t_n \end{bmatrix} \in \mathbf{R}^{m \times n}

satisfies

t_k \succeq 0

and

\mathbf{1}^T t_k = 1

, then

T

can be expressed as

T = \theta_1 T_1 + \cdots + \theta_N T_N,

where

T_i

is a zero-one matrix with exactly one element equal to one per column, and

\theta_i \geq 0

\sum_{i=1}^N \theta_i = 1

. What is the maximum number of deterministic detectors

N

we may need? We can interpret this convex decomposition as follows. The randomized detector can be realized as a bank of

N

deterministic detectors. When we observe

X = k

, the estimator chooses a random index from the set

\{1, \ldots, N\}

, with probability

\mathbf{prob}(j = i) = \theta_i

, and then uses deterministic detector

T_j