4
$\begingroup$

This is a follow up of the question in one dimension, that asked to show that the all the maxima of the sum of Gaussian

$$f_n(x):= \sum_{i=1}^{n}e^{-(x-x_i)^2}, x_1 < x_2 < \dots < x_n$$

are strict local maxima, i.e. there's a punctured neighborhood $U*$ around each local maxima $x*$, so that the $\forall x \in U*, f(x)< f(x*),$ (instead of $f(x)\le f(x*).$)**

The accepted answer used the identity theorem for real analytic function $f_n'$ to show that indeed all the critical points of $f_n$ are isolated, which, combined with the fact that the critical points must lie in $[x_1,x_n],$ proved that the critical points were finite in number and thus the answer proved that in one dimension, the local maxima of $f_n$ are strict local maxima.

This question is its generalization to higher dimensions $x_i, x \in \mathbb{R}^p.$ So here we consider:

$$f_n(x):= \sum_{i=1}^{n}e^{-||x-x_i||^2}.$$

Note that, here the critical points $x*$ will be given by:

$$\nabla{f_n}=0$$

$$ \implies \boxed{ x*=\frac{ \sum_{i=1}^{n}e^{-||x*-x_i||^2} x_i }{ \sum_{i=1}^{n}e^{-||x*-x_i||^2} } },$$

implying that $x*$ lie in the convex hull $C$ of $\{x_1\dots x_n\},$ just like in the one dimensional case, they lied in $[x_1,x_n]$ (see above or the link to the one dimensional case given above).

But this time, unlike one dimensional case, we cannot guarantee using the identity theorem that the zeros of the $\nabla{f_n}$ are isolated, because in higher dimensions, the usual identity theorem for real analytic function doesn't hold. We do know that zeros of the gradient has zero Lebesgue measure, thanks to this post and the references therein; but this doesn't prove that the the zeros are isolated, unlike one dimensional case.

Here's an image that shows a linear combination of three, two dimensional Gaussians:

enter image description here

It seems to me that its local maxima are all strict local maxima. I did an image search but never found any image otherwise.

So is there a proof that the local maxima of $f_n$ are strict?

Thought: (1) Since $0< f_n(x) \le n,$ I'm thinking if we can explore the topology of $y \in (0,n], f_n^{-1}(y)$. It seems to me that $\forall y \in (0,n], f_n^{-1}(y)$ consists of the disjoint union of at most $n$ points or hyperspheres $S^{p-1}\subset \mathbb{R}^p.$ whose supporting hyperplanes are orthogonal to the $x_n$ axis: so for example when $p=2, f_n^{-1}(y)$ is a disjoint union of at most $n$ points or horizontal circles whose supporting planes are orthogonal to the $x_3$ axis. If we can show that, then it'll show that for the local maximum $x*$ with local maximum value $y*, f_n^{-1}(y*)$ is a point or a disjoint union of points, as otherwise it'd be a disjoint union of hyperspheres orthogonal to the axis $x_{n+1}$ , which would mean that these hyperspheres can't come arbitrarily close to $x*,$ proving the local max is a strict one. Not sure if we need Morse theory to prove this?

Thought: (2) I'm not familiar with a lot of fixed point theory, but I see that the critical points are the fixed points of the map from $\Phi: \mathbb{R}^p\to \mathbb{R}^p, C\to C:$ (see the boxed equation above)

$$\Phi: x \mapsto \frac{ \sum_{i=1}^{n}e^{-||x-x_i||^2} x_i }{ \sum_{i=1}^{n}e^{-||x-x_i||^2} } $$

Now can we say something about the above map $\Phi$ that guarantees that its fixed points are isolated? I don't know, but I'm looking at this and this question on MSE that deal with isolatedness and thus finitely many Lefscetz fixed points on a compact manifold, and in our case, we know that these fixed points of $\Phi: \mathbb{R}^p\to \mathbb{R}^p$ are on a compact manifold with boundary and corners, namely $C,$ the convex hull of $\{x_1, x_2 \dots x_n\}.$ So it seems to me that all we may need to show is that: $\Phi:C \to C$ is Lefschetz, i.e. $D\Phi_{x*}:\mathbb{R}^p\to \mathbb{R}^p$ does not have the eigenvalue $1.$ Can we show that, probably?

Thought (3) [after the suggestion in the first comment]

We can try proving the positive definiteness of the Hessian at the critical point $x*$,, where the Hessian matrix $H(x)$ at $x$ is as follows:

$$H(x)={\sum_{i=1}^{n}(-2I+4{(x-x_i)(x-x_i)^{T}})exp(-||{x-x_i}||^2)}.$$ But it seems difficult to manipulate at the critical point $x*$ above.

$\endgroup$
11
  • 1
    $\begingroup$ how about computing the Hessian and possibly showing that it is positive definite locally at the local max? then it just follows by Taylor expansion. $\endgroup$ Feb 7, 2023 at 1:30
  • 1
    $\begingroup$ can you include the Hessian matrix expression, perhaps we can then use some inequality to prove strict positive definiteness? $\endgroup$ Feb 7, 2023 at 19:18
  • 1
    $\begingroup$ Techniques for showing positive definiteness show up in various nonlinear programming books such as Boyd's online notes, Bertsekas and Lu-Yuenberger books for ideas. They also handle many similar problems with exponentials. $\endgroup$ Feb 7, 2023 at 22:30
  • 1
    $\begingroup$ @ThomasKojar Doesn't work, even in one dimension. Look at $e^{-(x-1)^2} + 2 e^{-1} e^{-x^2} + e^{-(x+1)^2}$. It's a positive linear combination of Gaussians whose Taylor series around $0$ starts $4 e^{-1} - \tfrac{2}{3} e^{-1} x^4 + \cdots$. So it has a local maximum at $x=0$, but the Hessian is $0$ there. $\endgroup$ Feb 7, 2023 at 22:33
  • 1
    $\begingroup$ I meant to say negative definiteness. $\endgroup$ Feb 8, 2023 at 6:05

1 Answer 1

0
$\begingroup$

Here is one condition on the $x_{i}$ for negative definiteness of

$$H(x)={\sum_{i=1}^{n}(-2I+4{(x-x_i)(x-x_i)^{T}})exp(-||{x-x_i}||^2)}.$$

The matrix $M_i:=(-2I+4{(x-x_i)(x-x_i)^{T}})$ has the eigenvalues $-2$ (multiplicity n) and $4\|x-x_{i}\|^{2}-2$ and so by plugging in the $x_{*}$ we get the condition

$$\|\sum_{m}(x_{m}-x_{i})\frac{exp(-||{x_{*}-x_m}||^2)}{Z}\|^{2}-\frac{1}{2}<0$$

for $Z:=\sum_{i}exp(-||{x_{*}-x_i}||^2)$. One can get better conditions by using the full sum; here I just went term by term. But even here we see that if all the $\{x_{m}\}$ are close enough to each other, then all the $M_i$ are negative definite.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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