Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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
up vote 4 down vote accepted

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)$$

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.