## 4 Choosing a \(D\)-Optimal Subset of \(n\) Measurements
### Set  
Since \(|Q^{\top}A|=|A|\), up to sign, the modified algorithm still determines the optimal index set. As described in the [PERSON] paper, these computations can be made much more efficient by exploiting the fact that at each iteration we are performing a rank-one modification to update an upper triangular matrix in step 2 in Algorithm 2 above. Suppose we have determined to replace \(i\)th column of the upper-triangular matrix \(A\) by the \(j\)th column of \(B\). First, we move the \(i\)th column of \(A\) to the \(n\)th column, as shown schematically in (7). \[ \begin{array}{cccccccccccc}*&*&i&*&*&*&*&*&*&*&*&*&i\\ &*&i&*&*&&&&*&*&*&i\\ &&i&*&*&*&*&*&*&i\\ &&&*&*&*&&&&*&*\\ &&&&*&&&&*\\ \end{array}  \tag{7}\]This step can be written as  
\[\left[ \begin{array}{ccccc}A_{1}&\mathbf{a}_{i}&A_{2}\end{array} \right]\mapsto\left[ \begin{array}{ccccc}A_{1}&A_{2}&\mathbf{a}_{i}\end{array} \right]=A\Pi_{i,n}\]  
where \(\Pi_{i,n}\) is the appropriate permutation matrix. The right-hand matrix is upper-triangular except for the sub-diagonal elements stored in \(A_{2}\). Let \(Q\) be the orthogonal matrix where \(\tilde{A}=Q^{\top}A\Pi_{i,n}\) is upper-triangular and set \(\tilde{B}=Q^{\top}B\). Note that \(Q^{\top}\) only acts on rows and columns \(i\) to \(n\) of \(A\Pi_{i,n}\) and rows \(i\) to \(n\) of \(B\). We have that  
\[\tilde{F}=\tilde{A}^{-1}\tilde{B}=\Pi_{i,n}^{\top}F.\]  
We can now replace the \(n\)th column \(\tilde{\mathbf{a}}_{n}\) of \(\tilde{A}\) by the \(j\)th column \(\tilde{\mathbf{b}}_{j}\) of \(\tilde{B}\), forming matrices  
\[\tilde{A}=\tilde{A}+\mathbf{ue}_{n}^{\top},\quad\tilde{B}=\tilde{B}-\mathbf{ue}_{j}^{ \top},\quad\mathbf{u}=\tilde{\mathbf{b}}_{j}-\tilde{\mathbf{a}}_{n}.\]  
Note that the matrix \(\tilde{A}\) on the left remains upper-triangular. For the next iteration it remains to calculate \(\tilde{F}=\tilde{A}^{-1}\tilde{B}\). Using the Sherman-Morrison formula [26] (Appendix A.1), we have  
\[\tilde{A}^{-1}=\left(\tilde{A}+\mathbf{ue}_{n}\right)^{-1}=\tilde{A}^{-1}-\frac{ \tilde{\mathbf{u}}\tilde{\mathbf{v}}^{\top}}{1+\mathbf{e}_{n}{}^{\top}\tilde{\mathbf{u}}}, \quad\tilde{\mathbf{u}}=\tilde{A}^{-1}\mathbf{u},\quad\tilde{\mathbf{v}}=\tilde{A}^{- \top}\mathbf{e}_{n},\]  
so that  
\[\tilde{A}^{-1}\tilde{B} = \tilde{A}^{-1}\tilde{B}-\tilde{A}^{-1}\mathbf{ue}_{j}^{\top}-\frac{ \tilde{\mathbf{u}}(\tilde{\mathbf{v}}^{\top}\tilde{B})}{1+\mathbf{e}_{n}{}^{\top}\tilde{ \mathbf{u}}}+\frac{\tilde{\mathbf{u}}(\tilde{\mathbf{v}}^{\top}\mathbf{u})\mathbf{e}_{j}^{\top}}{1 +\mathbf{e}_{n}{}^{\top}\tilde{\mathbf{u}}}\,, \tag{8}\] \[= \tilde{F}+\tilde{\mathbf{u}}\mathbf{w}^{\top},\]  
where  
\[\mathbf{w}=\left(\frac{\tilde{\mathbf{v}}^{\top}\mathbf{u}}{1+\mathbf{e}_{n}^{\top}\tilde\mathbf{{u}}}-1\right)\mathbf{e}_{j}-\frac{\tilde{B}^{\top}\tilde{\mathbf{v}}}{1+\mathbf{e}_{n}{} ^{\top}\tilde{\mathbf{u}}}.\]  
Thus, \(\tilde{F}\) is a rank-one update of \(\tilde{F}\). The expressions above can be considerably simplified. We note that  
\[\tilde{\mathbf{u}}=\tilde{F}(:,j)-\mathbf{e}_{n},\quad\frac{\tilde{\mathbf{v}}^{\top}\mathbf{ u}}{1+\mathbf{e}_{n}^{\top}\tilde{\mathbf{u}}}-1=-1/\tilde{F}(n,j),\quad\frac{\tilde{B}^{ \top}\tilde{\mathbf{v}}}{1+\mathbf{e}_{n}{}^{\top}\tilde{\mathbf{u}}}=-\tilde{F}(n,:)^{ \top}/\tilde{F}(n,j),\]  
so that  
\[\mathbf{w}=-\frac{1}{\tilde{F}_{n,j}}(\tilde{F}(n,:)^{\top}+\mathbf{e}_{j}).\]  
Recalling that \(\tilde{F}=\Pi_{i,n}^{\top}A^{-1}B\), we see that from (8), \(\tilde{A}^{-1}\tilde{B}\) can be constructed as a rank-one update of the previously calculated \(F=A^{-1}B\). We also note that \(\tilde{F}(n,j)=F(i,j)>1\) (since the update is only invoked to increase \(|A|\)) so that the rank-one update of \(F\) is numerically stable. The formation of \(\tilde{A}\) and \(\tilde{A}\) requires \(O(n^{2})\) steps and the formation of \(\tilde{F}\) requires \(O(mn)\) steps.