# How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\}$

I have a real function $f:\mathbb{{R}}^{d}\mapsto\mathbb{R}$, where $d>1$. The question is how to compute the level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\}$. I am a statistician knowing very few things about computer science. I would appreciate very much if anyone could suggest some reference, methods and/or alogirthms.

In my problem, $f\left(\theta\right)=\sum_{i=1}^{N}\log g\left(\mathbf{z}_{i};\theta\right)$, where $g\left(\mathbf{z}_{i};\theta\right)$ is a probability density function of $\mathbf{z}_{i}$ parameterized by a vector of parameters $\theta$. $\mathbf{z}_1,\ldots, \mathbf{z}_N$ are observed samples. For example, $g\left(\mathbf{z}_{i};\theta\right)$ is the density function of a normal distribution with variance $1$ $$g\left(\mathbf{z}_{i};\theta\right)=\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{\left(y_{i}-\mathbf{x}_{i}'\theta\right)^{2}}{2}\right).$$ Here $\mathbf{z}_{i}=\left(y_{i},\mathbf{x}_{i}\right)'$.

• How is $f$ represented, i.e., what do you know about $f$? Clearly, there are uncountably many $f$s and only countably many methods/algorithms, so we need to know something about $f$. – Pål GD Jul 20 '13 at 19:33
• Thanks for reply. I have updated my question with more details about the function $f$. Hopefully, the question is better framed. – semibruin Jul 20 '13 at 19:50
• Real numbers can not be handled in general; what are your requirements on the result (quality)? – Raphael Jul 20 '13 at 20:51
• @Raphael You are being very pedantic. Real numbers are manipulated all the time in computers, usually using a floating point representation. Of course, computations are approximate. It could be that semibruin is interested in solving a practical problem rather than some theoretical question. – Yuval Filmus Jul 20 '13 at 21:06
• @YuvalFilmus: See, that's why I'm asking. I fail to see how it's "pedantic" to inquire what the desired result is, if only to rule out misconceptions. (And no, IEEE floats are not reals. And that really hurts in any kind of numerical computation.) – Raphael Jul 21 '13 at 17:20

We can compute $$f(\theta) = -N\log (2\pi)-\frac{1}{2}\sum_{i=1}^N (\langle x_i,\theta \rangle -y_i)^2.$$ Expanding this out, we get that $f(\theta)$ is some quadratic form: $$f(\theta) = \theta' A \theta + v'\theta + C,$$ where $A$ is symmetric. The next step is to get rid of the linear term. Let $\theta = \psi + \epsilon$. Then $$\theta' A \theta + \langle v,\theta \rangle + C = \psi' A \psi + (2\epsilon' A + v') \psi + (\epsilon' A \epsilon + v'\epsilon + C).$$ So choosing $\epsilon' = -v' A^{-1}/2$ (assuming $A$ is invertible), we get $$f(\psi + \epsilon) = \psi' A \psi + C'.$$ The theory of quadratic forms tells us that if $A$ is invertible then we can write $A = P'DP$, where $D$ is a diagonal matrix with $\pm 1$ on the diagonal and $P$ is invertible. If $\psi = P \chi$ then $$f(P^{-1} \chi + \epsilon) = \chi' D \chi + C' = \sum_{i=1}^k \delta_i \chi_i^2 + C',$$ where $\delta_i \in \{\pm 1\}$. Suppose for example that the first $k_+$ are $+1$ and the rest $k_- = k - k_+$ are $-1$, and write $\chi = [\chi_+\;\chi_-]$. Then $$f(P^{-1} \chi + \epsilon) = \|\chi_+\|^2 - \|\chi_-\|^2 + C'.$$ If $k_+ = 0$ or $k_- = 0$ then the level sets are spheres or cospheres, up to an affine transformation of course. Otherwise it gets more complicated.
In your case, however, it is clear from the function $f$ itself then the quadratic form $A$ is negative semidefinite, probably in fact negative definite. In other words, $k_+ = 0$. So the sets you're after are affine transformations of cospheres. In other words, they are "outsides" of ellipsoids.
The only non-trivial step is finding the matrix $P$. Since your matrix is negative definite, you can use Cholesky decomposition.
• Thanks for your answer, Yuval. The normal distribution is an elliptical distribution. I guess your approach after slight modification shall work for all elliptical distributions. I am indeed working on more complicated scenario. Would it make some sense by considering the Taylor expansion $f(\theta)\approx\theta'f_{\theta=0}^{(2)}\theta+f_{\theta=0}^{(1)}\theta$. The hessian matrix here is usually negative definite in my case. – semibruin Jul 21 '13 at 6:17