## 4 Choosing a \(D\)-Optimal Subset of \(n\) Measurements
### Subset Selection Using the QR Factorisation with Column Pivoting  
The QR factorisation of an \(m\times n\) matrix \(C=QR\) has the following geometrical interpretation. The column vectors \(c_{j}\) of \(C\) define an \(n\) dimensional subspace \(\mathcal{C}\) of \(\mathbb{R}^{m}\). The orthogonal matrix \(Q\) defines an axis system for \(\mathbb{R}^{m}\), such that the \(n\) columns of \(Q_{1}\) define an axis system for \(\mathcal{C}\) and the \(m-n\) columns of \(Q_{2}\) define an axis system for the space of vectors \(\mathcal{C}^{\perp}\) orthogonal to \(\mathcal{C}\). The columns for \(Q_{1}\) are constructed so that \(q_{1}\) is aligned with \(c_{1}\), and so that there is an \(r_{11}\) such that \(c_{1}=r_{11}q_{1}\). The vector \(q_{2}\) is chosen to lie in the plane defined by \(c_{1}\) and \(c_{2}\), and so there are scalars \(r_{12}\) and \(r_{22}\) such that \(c_{2}=r_{12}q_{1}+r_{22}q_{2}\), etc. This gives the factorisation  
\[[c_{1}\ \cdots\ c_{n}]=[q_{1}\ \cdots\ q_{n}]\left[ \begin{array}{cccc}r_{11}& r_{12}&\cdots&r_{1n}\\ 0&r_{22}&\cdots&r_{2n}\\ 0&0&\ddots&\vdots\\ 0&0&\cdots&r_{m}\end{array} \right],\]  
i.e., in matrix notation \(C=Q_{1}R_{1}\). An equivalent geometrical interpretation is that the orthogonal matrix \(Q^{\top}\), a combination of rotations and reflections, transforms \(C\) so that its first column is aligned with the first axis in \(\mathbb{R}^{m}\), the second column lies in the plane defined by the first and second axes in \(\mathbb{R}^{m}\), the third column lies in the three-dimensional space defined by the first three axes in \(\mathbb{R}^{m}\), and so on: \(Q^{\top}C=R\). For the standard QR algorithm, the columns of \(C\) are processed in the order they appear in the matrix \(C\). For the QR algorithm with column pivoting [23], the order of the columns is changed to improve the numerical properties of the algorithm. The column of largest Euclidean length is aligned with the first axis. Of the remaining columns, the column that is furthest from the space defined by the first axis is then rotated to the plane defined by the first and second axes. At the \(k+1\)th stage, it is the column furthest from the subspace defined by the first \(k\) axes directions that is chosen to be transformed to lie in the space defined by the first \(k+1\) axes directions. The output of the algorithm includes the specification of a permutation matrix \(P\) that permutes the columns of \(C\), along with an orthogonal \(Q\) and upper triangular \(R\) such that \(CP=QR\). The first algorithm considered here is based on a subset selection algorithm described in [23] (Section 5.5). The issue addressed by the subset selection algorithm is that of trying to explain a measured response vector \(y\) in terms of basis vectors, usually representing covariates \(x\) and functions of covariates, stored in an \(m\times p\) matrix \(C\). It is assumed that \(y\) lies close to a \(n\) dimensional subspace defined by a subset of the columns of \(C\). The problem is to estimate \(n\) and choose \(n\) columns of \(C\) that best explain the response, using the QR with column pivoting to select columns that are optimally mutually independent. This information can then be used to predict other, possibly future, responses based on knowledge of the variates represented by the selected columns. The algorithm uses the singular value decomposition (SVD) to estimate \(n\) and the QR algorithm with column pivoting to select an appropriate set of \(n\) columns. Our design of experiment problem is different. The observation matrix \(C\) of all potential measurements is assumed to be full rank, so estimating the rank of \(C\) is not required. More importantly, our selection problem is to select from the rows of \(C\), not the columns. However, the selection of a set of vectors that are maximally mutually independent is directly relevant. Suppose \(C\) has QR factorisation \(C=Q_{1}R_{1}\), where \(Q_{1}\) is \(m\times n\) and \(R_{1}\) in \(n\times n\) and upper-triangular and full rank.