## 4 Choosing a \(D\)-Optimal Subset of \(n\) Measurements
### Set
Suppose the (full rank) variance matrix \(V=LL^{\top}=(R^{\top}R)^{-1}\) represents the current knowledge about parameters \(\mathbf{a}\) and up to \(m\) (new) measurements are potentially available, modelled according to

\[y_{i}\sim\mathcal{N}(\mathbf{c}_{i}^{\top}\mathbf{a},1),\quad i=1,\ldots,m.\]

(As before, we assume that, for each \(i\), \(y_{i}\) and \(\mathbf{c}_{i}\) have been weighted so that the uncertainty associated with \(y_{i}\) is 1.) Which measurements should we make in order to best improve our knowledge about \(\mathbf{a}\)? We suppose that resources exist to make \(p\) more observations. An exhaustive search of all combinations is only feasible for small \(p\) and modest \(m\). The sequential algorithms below add the observations one at a time, with the choice at each stage designed to maximise the information. These are further examples of so-called 'greedy algorithms'. Let \(C\) be the \(m\times n\) observation matrix whose \(i\)th row is \(\mathbf{c}_{i}^{\top}\) and \(V_{i}\) the variance matrix associated with \(\mathbf{a}\) given that the \(i\)th measurement (and only the \(i\)th measurement) is made. Then,

\[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}},\]

using the Sherman-Morrison formula [26] (Appendix A.1). Let

\[\mathbf{f}_{i}=V\mathbf{c}_{i},\quad g_{i}^{2}=\mathbf{c}_{i}^{\top}\mathbf{f}_{i}=\mathbf{c}_{i}^ {\top}V\mathbf{c}_{i}. \tag{10}\]

Then,

\[V_{i}=V-\frac{\mathbf{f}_{i}\mathbf{f}_{i}^{\top}}{1+g_{i}^{2}}=V-\mathbf{u}_{i}\mathbf{u}_{i} ^{\top},\quad\mathbf{u}_{i}=\frac{1}{\sqrt{1+g_{i}^{2}}}\mathbf{f}_{i}. \tag{11}\]

so that \(V_{i}\) is a symmetric rank-one update of \(V\). The eigenvalues \(\lambda_{j,i}\) of \(V_{i}\) can be related to the eigenvalues \(\lambda_{j}\) of \(V\) through the following result [23] (Section 8.1), [27] (p. 94):

**Proposition 2**. : _Suppose \(W=V+\rho\mathbf{u}\mathbf{u}^{\top}\), where \(V\) is an \(n\times n\) symmetric matrix, \(\mathbf{u}\) is an \(n\)-vector with \(\mathbf{u}^{\top}\mathbf{u}=1\) and \(\rho\) is a constant. Suppose \(V\) and \(W\) have eigenvalues_

\[\lambda_{1}(V)\geq\lambda_{1}(V)\geq\lambda_{2}(V)\geq\cdots\geq\lambda_{n}(V),\]

_and_

\[\lambda_{1}(W)\geq\lambda_{1}(W)\geq\lambda_{2}(W)\geq\cdots\geq\lambda_{n}( W).\]

_If \(\rho\geq 0\), then_

\[\lambda_{i}(W)\in[\lambda_{i}(V),\;\lambda_{i-1}(V)],\quad i=2,\ldots,n,\]

_while if \(\rho\leq 0\), then_

\[\lambda_{i}(W)\in[\lambda_{i+1}(V),\;\lambda_{i}(V)],\quad i=1,\ldots,n-1.\]_In either case, there exist \(n\) constants \(\gamma_{i}\), \(\gamma_{i}\geq 0\), with \(\gamma_{1}+\cdots\gamma_{n}=1\), such that_

\[\lambda_{i}(W)=\lambda_{i}(V)+\gamma_{i}p.\]

#### 4.4.1 Sequential D-Optimality Algorithm

We use the relationship (5) to write

\[|V_{i}| = |(R^{\top}R+c_{i}c_{i}^{\top}|^{-1},\] \[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}},\]0 \[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}},\]1 \[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}},\]2

A sequential algorithm can therefore be designed which at each stage chooses the \(i\) that maximises \(g_{i}^{2}\). The algorithm can be run in two modes: the first in which the algorithm can choose any row at most one time, the second in which there is no limit in the number of times any row can be selected. Having a row repeated \(k\) times is equivalent to having a single more accurate observation with its uncertainty reduced by a factor of \(1/\sqrt{k}\). In the second mode, it is often the case that additional measurements correspond to repeat measurements chosen from the D-optimal set of \(n\) points.