# Optimal sampling to estimate a quadratic function

Suppose I have a quadratic function: $$f(x) = a^T x + x^TBx$$ with $x \in \mathbb{R}^n$. Given a point $x$ I can measure $f(x)$ up to some noise, that is I can get a measurement: $$\hat{f}(x) = f(x) + z \; \; with \;\; z \sim N(0,\sigma^2).$$ Now given a point $x_0$ and an $n$-dimensional $S^n$ ball of radius $\epsilon$ centred around it ($S^n = \{x: ||x-x_0|| \leq \epsilon \}$), is there an optimal (in some sense) way to choose points from $S^n$ in order to estimate parameters $a$ and $B$?

So far I've just sampled points from $S^n$ at random, but maybe there is a way to exploit the fact that $f(x)$ is quadratic. Also I have chosen I sphere, but I could have used an hypercube, the important is that I have to evaluate the function around a point $x_0$ (which is given) without going to far from it.

• My question is more about determining the points $x_1,\dots,x_n$ where to evaluate the function, in order to obtain a sample $\hat{f}(x_1), \dots, \hat{f}(x_n)$. Once the sample has been obtained I would fit a quadratic model using Maximum Likelihood. – Matteo Fasiolo Nov 22 '12 at 14:56
• Then I think the crux of the choice is the optimality criterion. Do you have something in mind? – user10525 Nov 22 '12 at 15:18
• For me it's important to get some fairly stable estimates of $a$ and $B$, so I would like to minimize their variance. As I said it's not necessary to evaluate the function inside a ball $S^n$, I could even simulate the points from $x \sim N(x_0,\epsilon \mathbf{I})$, the important is not getting too far from $x_0$. – Matteo Fasiolo Nov 22 '12 at 15:30
• This is the area of (nonlinear) design of experiments. The optimality criteria usually have to do with the joint covariance of the parameters to be estimated (e.g., $\det {\mathbf{V}}[ \hat a, {\rm vec}\hat B ]$, aka $D$-optimality criterion). – StasK Nov 22 '12 at 18:35

Let $y_i$ denote the random variable $\hat{f}(x_i)$ and $Y_n$ denote $\{y_i\}_{i \leq n}$,
In the case where you have to fix all your points $\{x_i\}_{i \leq n}$ before you get any observation $y_i$, I suggest you to consider points which maximize some optimal design criterion. Like StasK said, D-optimality is a common criterion. Latin Hypercube Sampling is a simple way to approximate these designs, and is often implemented in software like Matlab.
If your procedure is sequential, i.e. you know $Y_i$ before to choose $x_{i+1}$, you may want to include your prior knowledge about $f$. A good criterion is then Information Gain (a.k.a Mutual Information). $$I(y_{i+1} \mid Y_i) = H(y_{i+1}) - H(y_{i+1} \mid Y_i)$$ where $H(X)$ denote the differential entropy of the variable $X$. You can then choose the $x$ maximising the information gain at each step, $$x_{i+1} = \underset{x \in S^n}{argmax}\ I(x \mid Y_i)$$
• Great! So, as I understand, if I have some prior knowledge about $a$ and $\mathbf{B}$ (maybe obtained with a previous sample), I can sample new points trying to optimize the Informational gain? Thanks a lot! – Matteo Fasiolo Nov 23 '12 at 15:54