11
$\begingroup$

Let $f:\mathbb{R}\to\mathbb{R}$ be a smooth function whose support is a closed interval, e.g. $\text{supp}(f)=[a,b]$. Then $f$ can be approximated (e.g. in $L^2$) by a linear combination of Gaussian densities, i.e. $$ f(x) \approx G_n(x) :=\sum_{i=1}^n a_{i,n} g(x;\mu_{i,n},\sigma_{i,n}^2), \quad a_{i,n}\in\mathbb{R}, \quad g(x;\mu,\sigma^2) =\frac1{\sqrt{2\pi\sigma^2}}e^{-\frac1{2\sigma^2}(x-\mu)^2}. $$

Suppose that for sufficiently large $n$, a best approximation to $f$ exists in some norm (again, e.g. $L^2$, but it doesn't really matter), i.e. $$ \Vert f-G_n^*\Vert \le \inf\big\{\Vert f-G_n\Vert : a_{i,n}\in\mathbb{R},\, \mu_{i,n}\in\mathbb{R},\, \sigma_{i,n}^2>0 \big\} $$

and furthermore $G_n^*\to f$.

I'd like to show that as long as $n$ is sufficiently large, then $\mu_{i,n}^*\in [a,b]$ for all $i=1,\ldots,n$. In other words, if a best approximation is arbitrarily close to $f$, it can't do something stupid like use a Gaussian component whose mass is mostly concentrated off of $\text{supp}(f)$.

The difficulty as I see it is that the weights $a_i$ can be arbitrarily close to 0, so there exist (arbitrarily) good approximators $G_n$ with "rogue" components (i.e. $\mu_i\not\in\text{supp}(f)$), but whose weight $a_i$ is very small. the challenge is showing somehow that "best" approximators avoid this kind of pathology.

Edit: Changed the assumptions so that the support of $f$ is necessarily an interval---this may not be true for arbitrary compact sets.

$\endgroup$
  • $\begingroup$ Do you allow $G_n$ to be an arbitrary linear combination of Gaussians, i.e. the parameters under the inf are all $a$s, $\mu$s and $\sigma$s? $\endgroup$ – Dirk Mar 20 '19 at 18:01
  • $\begingroup$ @Dirk: Yes. (Although, does it matter? Even if you restrict all parameters to lie in some compact set, I still don't see a way out.) $\endgroup$ – JohnA Mar 20 '19 at 18:07
  • $\begingroup$ What about taking $f$ as a truncated (and suitably smoothed) Gaussian where $\mu$ is far away from $K$? If $n$ is equal 1 you should get this Gaussian back (if the smoothing is small enough). $\endgroup$ – Dirk Mar 20 '19 at 18:15
  • 1
    $\begingroup$ @enthdegree "obviously has weights outside of [0,1]" This is not at all obvious to me. I am also not sure why your approximation is norm zero away from $f$. (To be clear, the error is being measured globally on all of $\mathbb{R}$, and not just on $[a,b]$.) $\endgroup$ – JohnA Mar 26 '19 at 19:03
  • 1
    $\begingroup$ Suppose $\mu_i \notin [a,b]$. Can we show that it is always better to replace $(a_i,\mu_i,\sigma_i^2)$ with $$\left(a_i\Phi\left(\frac{b-\mu_i}{\sigma_i}\right)-a_i\Phi\left(\frac{a-\mu_i}{\sigma_i}\right), E[X], Var[X]\right)$$ where $X$ is the normal distribution $N(\mu_i,\sigma_i^2)$ truncated to $[a,b]$? $\endgroup$ – Matt F. Mar 26 '19 at 19:47
2
+100
$\begingroup$

Case 1: Let $f\geq 0$. We consider the following easier problem :$$ \|f-G_n^*\|_{L^1}\leq \inf \{\|f-G_n\|_{L^1}:a_{i,n}\geq 0, \mu_{i,n}\in \mathbb{R}, \sigma_{i,n}>0 \}. $$ Since $f\geq 0$, we have $G_n^*\rightarrow f $. In this case, for any $n$ we have $\mu_{i,n}^*\in [a,b]$. Intuitively, otherwise more than half of the mass of a gaussian would be outside $[a,b]$ and gives a strictly positive contribution to the norm.

Detailed proof: We have $$ \int_\mathbb{R} |G_n - f|dt=\int_a^b |G_n - f|dt + \sum_{i=1}^n a_i \left(\int_{-\infty}^a g_i(t)+ \int^{-\infty}_b g_i(t)dt\right)$$where $g_i(t)=g(t;\mu_i,\sigma_i)$. Let $G_n^*$ a best approximation and suppose that there exists $\mu_i^*<a$ (resp $>b$). For $s\in [0,1]$, define $$G_n(s)=G_n^* - (1-s)a_i g_i. $$ $G_n(s)$ is the same as $G_n^*(s)$ with $a_i$ replaced by $s a_i^*$. Therefore $$\begin{align} \int_{\mathbb{R}} |G_n(s) - f|dt & = \int_\mathbb{R} |G_n^* -(1-s)a_ig_i- f|dt\\ &\leq \int_a^b \Big\{|G_n^* - f|+(1-s)|a_i g_i|\Big\}dt + \int_{t\notin [a,b]} |G_n^*-(1-s)a_i g_i| \\ &= \int_a^b \Big\{|G_n^* - f|+(1-s)|a_i g_i|\Big\}dt + \int_{t\notin [a,b]} G_n^*-(1-s)a_i g_i \\ &= \int_a^b |G_n^* - f|dt+\int_{t\notin [a,b]} G_n^* dt \\ &\quad+(1-s)a_i \left(\int_a^b g_idt-\int_{t\notin[a,b]} g_i(t)dt\right)\\ \end{align}$$ But because $\int_{-\infty}^a g_i(t)dt> \frac{1}{2}$ and $\int_a^b g_i(t)dt< \frac{1}{2}$ the last term is stictly negative and we have $$\|G_n(s)-f\|=\int_{\mathbb{R}} |G_n(s) - f|dt < \int_{\mathbb{R}} |G_n^* - f|dt = \|G_n^* - f\|$$ for all $s\in (0,1)$ which is in contradiction to the minimisation of $G_n^*$. $\square$

Case 2: We don't make any assumption in $f$, the norm $\|.\|$ or the positivity of $a_i$. Here I don't have a rigorous proof but I argue that your claim is not true. I try to construct the following counter example: Let $$f(t)=1_{[-1,1]}(t)g(t)$$ and $$h(t)=f(t)-g(t)$$ where $g(t)=g(0,1,t)$.

I make the following natural generalisation of your claim: if $\text{supp}(f) = (-\infty,a]$ or $\text{supp}(f) = \mathbb{R}-[a,b]$ and $f$ decay to 0 fast enough at $\pm \infty$ then your claim is also true for $f$.

We note $F_n^*$ be the best approximation of $f$ and $H_n^*$ the best approximation of $h$. Now remark that $$\|h - H_{n+1}^*\| \leq \| h - F_n^* +g\|= \|f-F_n^*\|$$ and $$\|f - F_{n+1}^*\| \leq \| f - H_n^* -g\|= \|h-H_n^*\|$$ So $$\|f - F_{n+2}^*\| \leq \|h-H_{n+1}^*\| \leq \|f - F_{n}^*\|$$ Therefore $H_{n+2}^* + g $ is also a very good approximation of $f$ and is least better than $F_n^*$. But if both yours claim and the natural generalisation I proposed were true then as $n\rightarrow \infty$ all the gaussian of $H_n^*$ should be centered in $\mathbb{R}-[-1,1]$ and all the gaussiaan of $F_n^*$ should be centered in $[-1,1]$. But this seems to me very hard to believe that $H_n^*-g$ and $F_n^*$ are so different one to another and yet gives almost as good approximation of $f$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is more or less the strategy I have been trying, but I don't quite follow your line of reasoning (e.g. where do you use $\int_{-\infty}^ag_i(t)dt>1/2$?). $\endgroup$ – JohnA Mar 28 '19 at 18:45
  • $\begingroup$ Also, your argument does not appear to use the fact that $G_n\to f$ -- as @Dirk pointed out in the comments it is easy to construct counterexamples otherwise, even when $G_n$ is a best approximation. These counterexamples are somewhat pathological, however, so maybe I just missed some steps in your argument. $\endgroup$ – JohnA Mar 28 '19 at 19:59
  • $\begingroup$ If $\int_{-\infty}^a < 1/2$ then $\int_a^b - \int _{-\infty}^a-\int_b^\infty < 0$. And if $f$ is positive the best approximation $G_n$ with $a_i \geq 0$ converge to $f$. $\endgroup$ – RaphaelB4 Mar 29 '19 at 8:46
  • $\begingroup$ @JohnA What about the given example, $f(x) = \mathbb{1}_{[a,b]}(x) \, g(x; \frac{a+b}{2}, \sigma)$? I think it is easy to imagine that this will have $\mu_i$ spread out over all of $\mathbb{R}$, and should even be easy to verify numerically? Even as $n \to \infty$, I find it hard to convince myself that at any point the Gaussian at the centre should be replaced. $\endgroup$ – student Apr 1 '19 at 14:16
  • $\begingroup$ @student The case $a_i\ge 0$ discussed in this answer seems more interesting, but the given example certainly sheds doubt on the case $a_i\in\mathbb{R}$. Nonetheless, it is still not clear that with sufficiently many Gaussians you couldn't approximate the interior of $[a,b]$ better than the tails in the complement $[a,b]^c$. Also, I am not sure how easy this would be to verify numerically? $\endgroup$ – JohnA Apr 1 '19 at 16:31

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.