## 4 Choosing a \(D\)-Optimal Subset of \(n\) Measurements
### Exchange Approach Based on the Gu and Eisenstat Algorithm  
The second algorithm described in this paper is directly targeted at determining a D-optimal design. It is based on the iterative algorithm of [PERSON] and Eisenstat [25] for determining a strongly rank-revealing QR decomposition. Below, we show how it can be adapted to provide a reduction in the \(D\)-measure at each iteration through exchanging rows and to stop when no reduction is possible. It starts with a selection \(C_{0}\) of \(n\) rows of the \(m\times n\) observation matrix \(C\), where \(C_{0}\) is already full rank; e.g., that provided by the SSQR subset selection algorithm of Section 4.1. We recall that minimising the \(D\)-measure is equivalent to maximising the absolute value of the determinant of the upper-triangular factor of the observation matrix. The idea of the algorithm is as follows. Partition \(C^{\top}\) as \(C^{\top}=\left[ \begin{array}{cc}A&B\end{array} \right]\), where \(A\) is \(n\times n\) and \(B\) is \(n\times(m-n)\). We assume that \(A=C_{0}^{\top}\) is full rank. The Gu-Eisenstat (GE) algorithm uses the following result:  
Proposition 1: _For \(n\times n\) full rank matrix \(A\) and \(n\times p\) matrix \(B\), let \(\bar{A}\) be the matrix constructed by replacing the \(i\)th column of \(A\), \(1\leq i\leq n\), by the \(j\)th column of \(B\), \(1\leq j\leq p\). Then,_  
\[|\bar{A}|=F_{i,j}|A|\]_where \(F=A^{-1}B\)._  
Proof. : For \(n\)-vectors \(\mathbf{u}\) and \(\mathbf{v}\),  
\[|A+\mathbf{uv}^{\top}|=|A|(1+\mathbf{v}^{\top}A^{-1}\mathbf{u}); \tag{5}\]  
see Appendix A.2. The result follows for \(\mathbf{v}=\mathbf{e}_{i}\), the \(i\)th column of the identity matrix and \(\mathbf{u}=\mathbf{b}_{j}-\mathbf{a}_{i}\), noting that \(A^{-1}\mathbf{a}_{i}=\mathbf{e}_{i}\). This suggests the following approach, assuming that the first \(n\) rows of \(C\) are full rank (Algorithm 2). ```
Data: An \(m\times n\) observation matrix \(C\) such that the first \(n\) rows are full rank, and tolerance factor \(f>1\). Result: Index set \(I\subset\{i=1,\dots,m\}\) where the first \(n\) elements specify \(C_{n}\) such that no row interchange will increase the determinant of \(C_{n}\) by more than \(f\). Steps: Partition \(C^{\top}=\left[ \begin{array}{cc}A&B\end{array} \right]\) and form \(F=A^{-1}B\). Initialise \(m\times 1\) index set \(I\) with \(I(i)=i\). while\(\max_{i,j}|F_{i,j}|>f\)do  1. Choose \((i,j)\) such that \(|F_{i,j}|\) is maximised. 2. Row interchange: set \(A:=A+(\mathbf{b}_{j}-\mathbf{a}_{i})\mathbf{e}_{i}^{\top}\), \(B:=B-(\mathbf{b}_{j}-\mathbf{a}_{i})\mathbf{e}_{j}^{\top}\). 3. Update \(I\), swapping the \(i\)th and \((n+j)\)th elements. 4. Form \(F=A^{-1}B\). end
```  
**Algorithm 2**Basic steps to determine a \(D\)-optimal subset of an observation matrix  
The main computational element of this algorithm is forming \(F=A^{-1}B\) at each iteration. Forming \(F\) explicitly in this way involves \(O(n^{3})\) steps to evaluate \(A^{-1}\) and a further \(O(mn)\) steps to evaluate the matrix product. Let \(Q\) be orthogonal such \(\tilde{A}=Q^{\top}A\) is upper-triangular and set  
\[Q^{\top}\big{[} \begin{array}{cc}A&B\end{array} \big{]}=\big{[} \begin{array}[] {cc}\tilde{A}&\tilde{B}\end{array} \big{]}. \tag{6}\]  
Then, \(F=A^{-1}B=\tilde{A}^{-1}\tilde{B}\), and the latter can be computed efficiently using back-substitution. Thus, step 4 in Algorithm 2 can be replaced by  
```
Data: An \(m\times n\) observation matrix \(C\) such that the first \(n\) rows are full rank, and tolerance factor \(f>1\). Result: Index set \(I\subset\{i=1,\dots,m\}\) where the first \(n\) elements specify \(C_{n}\) such that no row interchange will increase the determinant of \(C_{n}\) by more than \(f\). Steps: Partition \(C^{\top}=\left[ \begin{array}{cc}A&B\end{array} \right]\) and form \(F=A^{-1}B\). Initialise \(m\times 1\) index set \(I\) with \(I(i)=i\). while\(\max_{i,j}|F_{i,j}|>f\)do  1. Choose \((i,j)\) such that \(|F_{i,j}|\) is maximised. 2.