## 1 Introduction  
While machine learning paradigms are based on access to large sets of data to extract the information of interest, many practical problems in science and technology arise in a context in which data are sparse and potentially expensive to generate. Given limited experimental resources, it is important that these resources are used effectively. The design of experiment (DoE) is an important area of study in applied mathematics and statistics. Many DoE studies relate to problems in which a response variable of interest, e.g., the yield of a crop, is possibly influenced by a number of control or stimulus variables, e.g., crop variety, soil type, irrigation regime, fertiliser treatment, etc. The form of the response function is usually unknown and the DoE problem is to design a number of experiments with the control variables set to different values, in order to estimate the response function from a set of candidate response functions and consequently choose control values that optimise the response; see, e.g., [1; 2; 3; 4; 5; 6; 7; 8]. The DoE problem has been addressed in applications across many scientific disciplines, including the placement of sensors in a electrical power grid [9; 10] and the measurement of thermal properties of materials [11; 12], for example. In this paper, we look at a particular aspect of the design problem: given a known response model, how do we choose a minimal number of measurements, taking into account the associated uncertainties, in order to estimate all the parameters of the system under study as accurately as possible. Thus, the problem can be posed as: given \(m\) potential observations to determine \(n\) parameters, \(m>n\), what is the best choice of \(n\) observations. In the context of (linear) least squares estimation, a version of the problem can be formulated as finding the \(n\times n\) submatrix of the complete \(m\times n\) observation matrix that has maximum determinant. The problem can be posed as an example of the following general optimisation problem. Suppose \(A=\{a_{i},i=1,\ldots,m\}\) is a set with \(m\) elements. Represent the set \(P(A)\)of all subsets of \(A\) as the set of characteristic functions \(\chi:A\longrightarrow\{0,1\}\): if \(B\subset A\), then the corresponding function \(\chi_{B}\in P(A)\) is such that \(\chi_{B}(a_{i})=1\) if \(a_{i}\in B\) and is \(0\) otherwise. Let \(D:P(A)\longrightarrow\mathbb{R}\) be a real valued function defined on \(P(A)\). The optimisation problem is  
\[\min_{\chi\in P(A)}\ \ D(\chi)\quad\text{subject to}\quad\sum_{i=1}^{m}\chi(a_{i})=n. \tag{1}\]  
In theory, the global solution to this DoE problem can be found by a brute force assessment of all choices of subsets, a total of \(m!/(n!(m-n)! )\) possibilities. For all but small \(m\) and \(n\), this approach will be computationally infeasible, even if the functional \(D\) is cheap to evaluate. Two other related approaches are commonly used to partially solve this type of combinatorial optimisation problem. The first approach, with a long history, see e.g., [13; 14; 15], is to use a sequential approach that at each stage constructs a new candidate subset by removing one element from the subset, replacing it by a new element that leads to a strict improvement in \(D\). The computational cost per step for such an algorithm will be given by the cost evaluating \(D\) and the cost of searching for a suitable exchange from the \(n(m-n)\) possibilities. Ideally, the computational cost of an exchange should be no worse than \(O(m)\) or \(O(m\log m)\) as a function of \(m\). The second approach is based on convex relaxation, replacing a combinatorial problem by a convex optimisation problem [16]. Let \(0\leq w_{i}=w(a_{i})\leq 1\), where we think of \(w_{i}\) as specifying the degree to which the \(i\)th element is in the solution optimal subset.