Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

I want to find an approximation of the gradient $\nabla V(J)$ of the following function $V(J) = P(X\in T(J))$. Where $X$ is a multidimensional stochastic vector with a smooth continuous probability density and $T$ is a (convex) set that depends on some parameters $J=(J_1,...,J_n)$. $V(J)$ is considered to be many times continuously differentiable.

I have $N$ independent samples $x_n$ drawn from $X$. And $V(J)$ is approximated with the relative frequency $$\hat{V}(J)=\frac{ | \{n \mid x_n\in T(J) \}| }{N}.$$ The approximation is piecewise constant.

Now I want to find an operator $\hat{D}$ that approximates the gradient.

For example: If J is one-dimensional. The gradient could be approximated by central difference $\hat{D}\hat{V}(J) = \frac{\hat{V}(J+h)-\hat{V}(J-h)}{2h}$. The problem with central difference is that since $\hat{V}$ is piecewise constant if $h$ is chosen too small, the difference is identically $0$ for most $J$.

The number of evaluations of $\hat{V}$ should be kept small as it is naturally quite expensive to compute. The approximation should be consistent in the sense that it becomes more accurate as $N$ increases.

Is there a standard way to solve this problem? Is there a limit on how accurate the approximation could get? Does it exist a theory for this kind of problems and where can I read more about it?

share|cite|improve this question
What's the quantifier doing in the sum in the displayed equation? Do you mean a sum over all $n$ such that $x_n\in T(J)$? I think that would be more clearly expressed by a sum over "$n:x_n\in T(J)$", or perhaps even more clearly simply by "$\lvert \{n\mid x_n\in T(J)\}\rvert$". – joriki Apr 4 '11 at 12:40
Thanks @joriki . Makes more sense this way. – Nxcho Apr 4 '11 at 12:58
You're welcome. Using \mid instead of | for the "such that" bar gives the proper spacing. – joriki Apr 4 '11 at 13:01

Perhaps there might be a solution based on a Fourier transform. If $A(J)(x)$ is the indicator function of $T(J)$ and $f(x)$ is the density of $X$, you have $V(J) = \int f(x) A(J)(x)\, dx = \int \overline{\hat{f}(k)} \widehat{A(J)}(k)\, dk$. Now the gradient (wrt $J$) of $A(J)(x)$ is a rather singular object, but the gradient of its Fourier transform is likely to be a smooth function, much more tractable. You could then use your samples to produce a numerical approximation of $\hat{f}$, and integrate numerically.

share|cite|improve this answer
Thank you for your answer. I see some problems with this approach. $T(J)$ is a compact set which means that the transformed integral will be an infinite one. Also I want my method to work even without much a priori knowledge of $f$ so it can be hard to get a good global estimate of the pdf. But I will investigate if I can get some good results out of this approach. – Nxcho Apr 5 '11 at 7:48

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.