5
$\begingroup$

Let $\epsilon > 0$. I would like to know if there exists $c < \infty$ such that for all $d \in \mathbb{N}$ the following holds. If $x \in \mathbb{R}^d$ let $N_x$ be the standard Gaussian centered at $x$. Let $\mathcal{V}$ be the subspace of $L^2(\mathbb{R}^d)$ spanned by the vectors $\{N_x: x \in \mathbb{Z}^d,||x||_2 \geq c\}$. Then the $L^2$ norm of the orthogonal projection of $N_0$ onto $\mathcal{V}$ is less than $\epsilon$.

I am also interested in the version of this question where the functions $N_x$ are the normalized indicators of balls of radius $\sqrt{d}$.

An idea that might be useful is as follows. In order to obtain the desired bound, it suffices to bound the norm of the projection onto the closed span $\mathcal{W}$ of $\{N_x :x \in \mathbb{R}^d,||x||_2 \geq c \}$. Since both $N_0$ and $\mathcal{W}$ are rotation-invariant, the projection of $N_0$ onto $\mathcal{W}$ must be rotation-invariant. Intuitively, this suggests that the projection should be a positive scalar multiple of

$f = \int_{\mathrm{O}(d)} u \cdot N_{\overline{x}} \, \mathrm{d} \sigma(u)$

where $\sigma$ is the Haar measure on the orthogonal group $\mathrm{O}(d)$ and $\overline{x} \in \mathbb{R}^d$ is any fixed point with $||\overline{x}||_2 = c$. Now,

$\langle N_0,f \rangle = \int_{\mathbb{R}^d} N_0(x) f(x) \, \mathrm{d}x = \int_{\mathbb{R}^d} N_0(x) \left( \int_{\mathrm{O}(d)} u \cdot N_{\overline{x}} \, \mathrm{d} \sigma(u) \right)(x) \, \mathrm{d}x \\ \int_{\mathrm{O}(d)} \int_{\mathbb{R}^d} N_0(x)( u \cdot N_{\overline{x}})(x)\, \mathrm{d}x \, \mathrm{d} \sigma(u) \\ = \int_{\mathrm{O}(d)} \int_{\mathbb{R}^d} (u \cdot N_0)(x) N_{\overline{x}}(x) \, \mathrm{d}x \,\mathrm{d}\sigma(u) \\ = \int_{\mathbb{R}^d} N_0(x) N_{\overline{x}}(x) \, \mathrm{d}x \leq \delta(c)$

where $\delta:[0,\infty) \to [0,\infty)$ is a function independent of $d$ with $\lim_{c \to \infty} \delta(c) = 0$.

Let $p$ be the projection of $N_0$ on $\mathcal{W}$ and let $\alpha > 0$ be such that $p = \alpha f$. We have $||p||^2 = \langle N_0,p \rangle = \langle N_0,\alpha f \rangle \leq \alpha \delta(c)$. Since $||p||_2 \leq 1$, we have $\alpha \leq 1/||f||_2$. Thus one would need to show that $||f||_2 > \beta$ for some absolute constant $\beta > 0$, as well as confirming the hypothesis about $f$.

$\endgroup$
  • $\begingroup$ Do you mean that $c$ is uniform in $d$? $\endgroup$ – Asaf May 14 '18 at 21:46
  • $\begingroup$ Yes, otherwise it's obvious that the case of indicators of balls has a positive answer. $\endgroup$ – burtonpeterj May 14 '18 at 22:01
  • $\begingroup$ I mean for the Gaussians in question to be $L^2$ unit vectors. This could be arranged by multiplying the whole function by an appropriate scalar or by modifying the variance. I'm not sure whether the answer to the problem changes based on which method is used. $\endgroup$ – burtonpeterj Jun 1 '19 at 18:56
0
$\begingroup$

For the question as it is currently stated, we only need to consider finitely many dimensions, since $||N_0||_2$ goes to $0$ as $d$ goes to infinity, and the inequality trivially holds when $||N_0||_2 < \epsilon$.

However, I’ve discussed this with the author of the post privately over email and he intended for $N_0$ to be an $L^2$-normalized gaussian so that $||N_0||_2 = 1$. I'll use a different but equivalent formulation: we can keep $N_0$ as the usual d-dimensional standard gaussian (whose $L^2$ norm will be less than $1$) and require that the norm of the projection is less than $\epsilon||N_0||_2$ rather than less than $\epsilon$.

For this modified problem, no such $c$ exists. For the ball-indicator version, I’ve made no progress.

I’ll use the following notation for my solution:

$N_{d,x}$ : the $d$-dimensional standard Gaussian centered at $x$.

$M_d$ : $d$-dimensional Gaussian with double the covariance as standard, centered at $0$. In other words, the convolutional square of $N_{d, 0}$. Note that $\langle N_{d, x}, N_{d, y} \rangle = M_d(x - y)$

$\mathcal{V}_{d, c}$: The same as $\mathcal{V}$ as defined in the question, but with a subscript to indicate the dimension and the value of $c$ used.

The norm of the projection of $N_{d,0}$ onto $\mathcal{V}_{d, c}$ is equal to the sup of the norm of the projection of $N_{d,0}$ onto each one-dimensional subspace of $\mathcal{V}_{d, c}$. Applying this fact, and making a substitution for $\epsilon$, we have that the problem is equivalent to the following:

Does there exist a $c$ such that $$\frac{\langle v, N_{d,0} \rangle ^2}{\langle v,v\rangle \langle N_{d, 0}, N_{d, 0} \rangle} < \epsilon$$ for all $v \in \mathcal{V}_{c, d}$, uniformly for all $d$?

Let $S_{d, n}$ be the set of all $x \in \mathbb{Z}^d$ with a $1$ in exactly $n$ coordinates and a $0$ in the remaining $d - n$ coordinates. Let $f_{d, n} = \sum_{x \in S_{d ,n}}N_{d, x}$.

We can explicitly compute the values $\langle f_{d,n} , N_{d,0} \rangle$ and $\langle f_{d,n} , f_{d,n} \rangle$. For this, let $G_d(r)$ be the value of $M_d$ at a point of norm $r$, so $M_d(x)$ = $G_d(||x||_2)$. Then we have $$\langle f_{d,n} , N_{d,0} \rangle = \binom{d}{n}G_d(\sqrt{n})$$ $$\langle f_{d,n} , f_{d,n} \rangle=\binom{d}{n} \sum_{m = 0}^{n} \binom{n}{m} \binom{d - n}{n - m} G_d(\sqrt{2(n - m)})$$

Here $m$ basically parameterizes the size of the overlap of nonzero coordinates between a pair of the terms comprising $f_{d,n}$.

If we fix $n$, and let $d$ go to infinity, the term with $m = 0$ dominates and we have: $$\frac{\langle f_{d,n} , f_{d,n} \rangle}{\binom{d}{n}^2 G_d(\sqrt{2n})} = 1 + O(\frac{1}{d})$$

We therefore have, from the computations above, and the fact that $\langle N_{d, 0}, N_{d, 0} \rangle = G_d(0)$:

$$\lim_{d \to \infty}{\frac{\langle f_{d, n}, N_{d,0} \rangle ^2}{\langle f_{d, n}, f_{d, n} \rangle \langle N_{d, 0}, N_{d, 0} \rangle}}$$ $$= \lim_{d \to \infty}{\frac{G_d(\sqrt{n})^2}{G_d(\sqrt{2n})G_d(0)}}$$ $$= 1$$

So no matter how large $c$ is, we can always choose a sequence of functions $f_{d,n}$ with a fixed $n > c^2$ which eventually breaks the inequality, as long as $\epsilon < 1$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Here is a suggestion for the one d case. First, look on the fourier transform side. Let $\phi_a$ etc. be the Gaussian shifted by a. On the the fourier transform side $\hat{\phi_a} \rightarrow e^{2 \pi a \xi} \phi_0$, and the question is can you approximate $\phi_0 $ by a linear combination of $e^{2 \pi n \xi} \phi_0$ where n is an integer and $|n| > c$ in $L^2$. This would entail that there is a linear combination so that $$ \int |\sum c_n e^{2 \pi n \xi} - 1 | ^ 2 \phi^2(\xi) d\xi $$ is small, where is sum is over $|n| > c$. But it cannot be small because $\phi_0^2 > m > 0$ on $(0, 2 \pi)$ so if it were small $$ \int_0^{2 \pi} |\sum c_n e^{2 \pi n \xi} - 1 | ^ 2 d \xi$$ would also be small, which it cannot be. This can be turned into a bound by considering what $m$ actually is, and getting the constants straight, which I have not done.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If we try to apply this to the $d$-dimensional case, we need to argue that $\int_{\sqrt{d} - 10 \leq |\xi| \leq \sqrt{d}+10} |1- \sum c_x e^{2 \pi i x \cdot \xi}|^2 \, \mathrm{d}\xi$ cannot be small if the sum is over $x$ with $|x|> c$. This seems very plausible ... $\endgroup$ – burtonpeterj May 14 '18 at 16:19
  • $\begingroup$ If I understand correctly, this bound doesn't get any better as c is increased, and therefore can't lead to a solution of the problem on its own. That being said, it is still interesting. $\endgroup$ – Tom Price Nov 11 '18 at 5:46

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.