12
$\begingroup$

Let \begin{align} f(t)=\sum_{i=1}^n a_i e^{-(x_i-t)^2}-c \end{align} where $x_1<x_2<...< x_n$ and $a_i>0$. For some positive constant $c$.

Can we show that $f(t)$ has at most $2n$ zeros?

The intuition here is that if $n=1$ we have a simple bell curve. Then, a horizontal line $c$ can cross it at most $2$ times. Now if $n=2 $, then we have two mixed bell curves and we get at most $4$ crossings.

$\endgroup$
13
$\begingroup$

In proposition 7 (together with the proof in the appendix) of Efficiently Learning Mixtures of Two Gaussians, A.T. Kalai, A. Moitra, G. Valiant prove that the linear combination of $n$ Gaussians with distinct variances can have at most $2(n-1)$ zeros. Their argument is inductive adding the Gaussians in order of decreasing variance. Every new Gaussian is added as close to a delta function, which increases the number of zeros by at most 2, and then everything is convolved with a gaussian of appropriate width.

In order to use this in your problem, we have to slightly perturb $f(t)=0$ to $$e^{-t^2}\left(\sum_{i=1}^n a_i e^{-(1+\epsilon_i)(x_i-t)^2}-c\right)=0$$ for distinct $\epsilon_i$ of small absolute value. This is a linear combination of $n+1$ Gaussians of distinct variances, and therefore has at most $2n$ zeros, as desired.

$\endgroup$
  • 2
    $\begingroup$ Very nice argument! A slightly more direct variant would be to write $f(t)$ as a convolution of the Gauss–Weierstrass kernel $g(t) = (\pi (1-\delta))^{-1/2} e^{-t^2/(1-\delta)}$ and $h(t) = \sum_{i=1}^n a_i \delta^{-1/2} e^{-(x_i-t)^2/\delta} - c$ for a $\delta$ small enough, so that $h$ has $2 n$ zeroes. Convolution with a Gaussian does not increase the number of zeroes (as a Pólya frequency function, it is a variation diminishing kernel; for more on this, see, for example, review sections written by Karlin here). $\endgroup$ – Mateusz Kwaśnicki Jan 21 '19 at 20:47
  • $\begingroup$ I have a quick question. Is the function $e^{(-(1+\epsilon)(x_i-t)^2} \cdot e^{-\frac{t^2}{2}}$ still treated as Gaussian? $\endgroup$ – Boby Jan 21 '19 at 23:07
  • $\begingroup$ @MateuszKwaśnicki Could you put your solutions as an answer too? $\endgroup$ – Boby Jan 21 '19 at 23:09
  • $\begingroup$ @Boby Yes, just combine the exponentials and complete the square. $\endgroup$ – Gjergji Zaimi Jan 21 '19 at 23:10
  • $\begingroup$ Also, is it a problem if one of $x_i$'s equal to zero? We might not have a distinct number of zeros condition. Or am I wrong here $\endgroup$ – Boby Jan 21 '19 at 23:15
5
$\begingroup$

(This is a follow-up to Gjergji Zaimi's beautiful answer: a minor simplification of the method applied there rather than a different solution. Written as a separate answer upon request of the original poster.)


Let $g_s(x) = (\pi s)^{-1/2} \exp(x^2 / s)$ denote the Gauss–Weierstrass kernel. Note that $g_s * g_t = g_{s + t}$.

Choose $\delta \in (0, 1)$ sufficiently small, so that $$ \begin{aligned} h(x) & = \sum_{i = 1}^n a_i \delta^{-1/2} \exp((x - x_i)^2 / \delta) - c \\ & = \pi^{1/2} \sum_{i = 1}^n a_i g_\delta(x - x_i) - c \end{aligned} $$ has exactly $2 n$ zeroes; or, more precisely, it changes its sign exactly $2 n$ times. (Is is intuitively clear, and relatively straightforward to prove, that $\delta > 0$ small enough have this property, but the details are a bit messy.) Then $f$ can be written as a convolution of $h$ and $g_{1 - \delta}$: $$ \begin{aligned} f(x) & = \sum_{i = 1}^n a_i \exp((x - x_i)^2) - c \\ & = \pi^{1/2} \sum_{i = 1}^n a_i g_1(x - x_i) - c \\ & = \biggl(\pi^{1/2} \sum_{i = 1}^n a_i g_\delta(\cdot - x_i) - c\biggr) * g_{1 - \delta}(x) . \end{aligned} $$ However, convolution with the Gauss–Weierstrass kernel does not increase the number of sign-changes: $g_s$ is a Pólya frequency function, and hence a variation diminishing kernel. For more on this, see, for example, review sections written by Samuel Karlin in Selected works of I. J. Schoenberg. It follows that $f$ changes its sign at most $2 n$ times, as claimed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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