## 4 Choosing a \(D\)-Optimal Subset of \(n\) Measurements
### Set
In the algorithm below (Algorithm 4), the mode is controlled by the flag \(i_{R}\):

```
Data: \(\bullet\) \(C\), an \(m\times n\) observation matrix \(C\), \(m>n\), \(\bullet\) \(V\), an \(n\times n\) full rank variance matrix \(V\) encoding the current state of knowledge of the parameters, \(\bullet\) \(p\), an integer \(1\leq p<m\) specifying the maximum number of observations to be made, and \(\bullet\) flag \(i_{R}=0\) or \(1\). If \(i_{R}=1\), rows of \(C\) can be selected more than once. Result: A \(p\times 1\) index set \(I\subset\{i=1,\ldots,m\}\), updated variance matrix \(V\) representing the variance in the parameters as a result of using observations \(C_{p}=C(I,:)\), the \(p\) rows of \(C\) specified by \(I\), and \(p\times 1\)\(t\) where \(0<t_{q}<1\), the reduction in the determinant of \(V\) at each iteration: \(|V_{q+1}|:=t_{q}|V_{q}|\). The rows are chosen to minimise \(t_{q}\) at each iteration. Set \(F=VC^{\top}\) and \(n\times m\) matrix \(G\) with \(G_{j,t}=F_{j,t}C_{j,t}\) with \(g_{i}=\|G(:,i)\|\), \(i=1,\ldots,m\). for\(q=1\)to\(p\)do
1. Evaluate \(\tau_{i}=1/(1+g_{i}^{2})\), \(i=1,\ldots,m\). 2. If \(q>1\) and \(i_{R}=0\), set \(\tau_{i}=2\), \(i=1(1),\ldots,I(q-1)\). 3. Find \(k\) such that \(\tau_{k}\leq\tau_{i}\), \(i=1,\ldots,m\). 4. Set \(I(q)=k\), \(t_{q}=\tau_{k}\), \(\boldsymbol{u}=F(:,k)/\sqrt{1+g_{k}^{2}}\), and \(\boldsymbol{w}=C\boldsymbol{u}_{k}\). 5. Update \(V:=V-\boldsymbol{u}\boldsymbol{u}^{\top}\), \(F=F-\boldsymbol{w}\boldsymbol{w}^{\top}\), and \(g_{i}=[(g_{i}-w_{i})(g_{i}+w_{i})]^{1/2}\), \(i=1,\ldots,m\). end for
```

**Algorithm 4**Sequential approach to optimising the D-measure in choosing \(p\) observations from a possible \(m>p\) observations

For each \(q\), the only operations required are matrix-vector multiplications and similar, requiring at most \(O(mn)\) steps. This compares with \(O(mn^{3})\) steps for an algorithm not exploiting rank-one updates. #### 4.4.2 Expected Information Gain Calculations

The quantities \(t_{q}\) calculated at each stage give the reduction in determinant of the variance matrix at the \(q\)th step. The following argument can be used to provide an expected value for \(t_{q}\), under the assumption that the rows of \(C\) each provide approximately the same amount of information. Suppose \(C\) consists of rows with a \(1\) in one column and zeros elsewhere. A D-optimal design would select rows so that the ones are distributed equally amongst the columns. If a total of \(q\) rows are selected, the variance matrix \(V_{q}\) is such that

\[V_{i}=(R^{\top}R+\mathbf{c}_{i}\mathbf{c}_{i}^{\top})^{-1}=V-\frac{V\mathbf{c}_{i}(V\mathbf{c }_{i})^{\top}}{1+\mathbf{c}_{i}^{\top}V\mathbf{c}_{i}},\]3

From this argument, the expected value of \(t_{q}\), \(q>n\), is such that

\[V_{i}=(R^{\top}R+\mathbf{c}_{i}\mathbf{c}_{i}^{\top})^{-1}=V-\frac{V\mathbf{c}_{i}(V\mathbf{c }_{i})^{\top}}{1+\mathbf{c}_{i}^{\top}V\mathbf{c}_{i}},\]4

In terms of the geometric mean \(\bar{d}\) of the eigenvalues of the variance matrices, we have

\[V_{i}=(R^{\top}R+\mathbf{c}_{i}\mathbf{c}_{i}^{\top})^{-1}=V-\frac{V\mathbf{c}_{i}(V\mathbf{c }_{i})^{\top}}{1+\mathbf{c}_{i}^{\top}V\mathbf{c}_{i}},\]5

For \(q=n+1\), we have

\[V_{i}=(R^{\top}R+\mathbf{c}_{i}\mathbf{c}_{i}^{\top})^{-1}=V-\frac{V\mathbf{c}_{i}(V\mathbf{c }_{i})^{\top}}{1+\mathbf{c}_{i}^{\top}V\mathbf{c}_{i}},\]6

where the left hand value corresponds to the case \(n=1\), and \(1/e\) is the limiting value as \(n\to\infty\). #### 4.4.3 Sequential A-Optimality Algorithm

We can also construct a counterpart of Algorithm 4 for A-optimality. For any \(\mathbf{v}\), \(\operatorname{Tr}(\mathbf{v}\mathbf{v}^{\top})=\mathbf{v}^{\top}\mathbf{v}=\|\mathbf{v}\|^{2}\).