snippetMinor
How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $
Viewed 0 times
thetaleftcomputelevelgeqhowsetright
Problem
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)'$.
$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)'$.
Solution
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.
$$ 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.
Context
StackExchange Computer Science Q#13365, answer score: 5
Revisions (0)
No revisions yet.