6
$\begingroup$

First of all, let me give a basic definition and the problem that we want to solve [both taken from Armin Iske's Book "Approximation Theory and Algorithms for Data Analysis"]:


Problem 8.1. On given interpolation points $X = \{x_1, \dots, x_n\}\subset \Omega$, where $\Omega\subset \mathbb R^{d}$ for $d>1$, and function values $f_X\in \mathbb R^{n}$ find an interpolant $s\in \mathcal C(\Omega)$ satisfying $s_X = f_X$, so that $s$ satisfies the interpolation conditions $$s(x_j) = f(x_j) \quad \text{for all $1\leq j\leq n$}.$$

Definition 8.2. [taken from Armin Iske's Book "Approximation Theory and Algorithms for Data Analysis"]:

A continuous and symmetric function $K: \mathbb R^{d}\times \mathbb R^{d} \rightarrow \mathbb R$ is said to be positive definite on $\mathbb R^{d}$, $K\in \textbf{PD}_d$, if for any set of pairwise distinct interpolation points $X = \left\{ x_1, \dots, x_n\right\} \subset \mathbb R^{d}$, $n\in \mathbb N$, the matrix $$A_{K, X} = \left( K\left(x_k, x_j\right) \right)_{1\leq j, k\leq n}\in\mathbb R^{n\times n}$$ is symmetric and positive definite.


Now, here comes the problem that I want to solve:

Let $\Phi\left(x-y\right) = K(x,y)$ be positive definite, $K\in \textbf{PD}_d$, where $\Phi:\mathbb R^{d}\rightarrow \mathbb R$ is even and satisfies, for $\alpha > 0$, the growth condition $$\left\vert \Phi\left(0\right) - \Phi\left( x\right) \right\vert \leq C \left\vert\left\vert x\right\vert\right\vert_{2}^{\gamma} \quad \forall x\in B_{R}\left( 0\right)$$ on some ball $B_{R}\left( 0\right)$ around $0$ with radius $R > 0$ and constant $C > 0$. Prove that no positive definite kernel $K\in \textbf{PD}_d$ satisfies the growth condition for $\gamma > 2$.

This is a homework we got in a class.

EDIT: This is the definition of (total) differentiability I know:

Let $U\subseteq \mathbb R^n$ be open and $F: U\rightarrow \mathbb R^m$.

(i) The function $F$ is called (totally) differentiable if there exists a linear map $A: \mathbb R^n\rightarrow\mathbb R^m$ such that $$\lim_{\xi\in\mathbb R^n\backslash\{0\},\ \xi\rightarrow 0}\frac{\|F(x+\xi)-F(x)-A(\xi)\|}{\|\xi\|} = 0$$

(ii) The function $F: U\rightarrow\mathbb R^m$ is called differentiable if $F$ is at all points $x\in U$ differentiable.

$\endgroup$
5
  • $\begingroup$ $\Phi \equiv 1$ satisfies the inequality for any $\alpha $. Prove that $\alpha >1$ implies that $\Phi$ is a constant. $\endgroup$ Commented May 12, 2021 at 23:30
  • $\begingroup$ I have updated the answer so that it no longer depends on this calculus fact in your edit, see below... $\endgroup$ Commented May 21, 2021 at 12:38
  • $\begingroup$ anyway to use the Taylor series expansion you would have to assume at least that K is a smooth function, but reading your definition again I see that you only assume K to be continuous. In my edited answer no assumption on the smoothness of K is required. $\endgroup$ Commented May 21, 2021 at 14:39
  • $\begingroup$ for (a) i have given a bit more detail in the edited answer below. for (b) if there is a precise definition of what makes a point an "interpolation point" or not an interpolation point, then you need to include that in your question. Otherwise I am assuming that the term "interpolation point" is just verbal fluff with the exact same meaning as ``point". $\endgroup$ Commented May 21, 2021 at 19:15
  • $\begingroup$ I believe that the current proof given is not correct.. To my understanding, the set $X$ of interpolation points is given, not sth that we can choose (as you do in your second paragraph) arbitrarily.. It also clearly states in the problem formulation (Problem 8.1. of my post) that $X$ is given $\endgroup$
    – Hermi
    Commented May 30, 2021 at 13:16

2 Answers 2

0
$\begingroup$

For every symmetric positive definite kernel function $K$ on a set $X$, there exists a unique Hilbert space $\mathcal{H}$ of functions on $X$ for which $K$ is a reproducing kernel. $\mathcal{H}$ is called the native reproducing kernel Hilbert space of K or native space in short. More in Wiki article in particular Moore-Aronszajn theorem.

The idea is to first show the corresponding (Hölder) condition for functions from the native space $\mathcal{H}$, apply mean value theorem to show that they are constant for $\alpha > 2$ and conclude that $K$ is not positive definite in this case.

Let $\mathcal{H}$ be the Hilbert space of functions $f: X \rightarrow \mathbb{R}$ with associated inner product $\langle \cdot, \cdot \rangle_{\mathcal{H}}$, then $$ \langle K(\cdot, x), f \rangle_{H} = f(x) \qquad \text{for all $f \in \mathcal{H}, x \in X$} $$

First, suppose that $\Phi(x - y) = K(x, y)$ satisfy the condition

\begin{equation} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} |\Phi(0) - \Phi(x)| \leq C \norm{x}_{2}^{\alpha} \qquad \text{for all } x \in B_{r}(0) \tag{1} \label{condition} \end{equation}

And let the kernel be normalized $$ \Phi(0) = 1 $$

Then, for every $f \in \mathcal{H}$, we have that \begin{align*} |f(x) - f(y)|^{2} &= |\langle f, \Phi(\cdot - x) - \Phi(\cdot - y) \rangle_{K}|^{2} \\ \tag{By Cauchy–Schwarz} &\leq \norm{f}_{K}^{2} \norm{\Phi(\cdot - x) - \Phi(\cdot - y)}_{K}^{2} \\ &= \norm{f}_{K}^{2} \left( \norm{\Phi(\cdot - x)}_{K}^{2} - 2 \langle \Phi(\cdot - x), \Phi(\cdot - y) \rangle_{K} + \norm{\Phi(\cdot - y)}_{K}^{2} \right) \\ \tag{Using the normalization $\Phi(0) = 1$} &= \norm{f}_{K}^{2} \left( 1 - 2 \Phi(x - y) + 1 \right)\\ &= \norm{f}_{K}^{2} 2 \left(\Phi(0) - \Phi(x - y) \right) \\ \tag{Using Condition \eqref{condition}} &\leq \norm{f}_{K}^{2} 2 C \norm{x - y}_{2}^{\alpha} \end{align*}

Meaning that every $f \in \mathcal{H}$ is globally Hölder continuous $$ |f(x) - f(y)| \leq D \norm{x - y}_{2}^{\alpha/2} $$ with the constant $D = \norm{f}_{K}^{2} 2 C$ and exponent $\alpha/2$.

Second, we show that for $\alpha > 2$, the native space $\mathcal{H}$ contains only constant functions $f$.

If the exponent $\alpha/2 > 1$, we can write $$ \frac{|f(x) - f(y)|}{\norm{x - y}_{2}} \leq D \norm{x - y}_{2}^{\alpha/2 - 1} $$

and taking the limit as $y \rightarrow x$ $$ \lim_{y \rightarrow x} \frac{|f(x) - f(y)|}{\norm{x - y}_{2}} \leq \lim_{y \rightarrow x} D \norm{x - y}_{2}^{\alpha/2 - 1} = 0 $$

Update: Recall that $f: X \rightarrow \mathbb{R}$ is differentiable at $x \in X$ if there exists a bounded linear operator $f'(x): X \rightarrow \mathbb{R}$ with

$$ \lim_{h \rightarrow 0} \frac{|f(x + h) - f(x) - f'(x) h|}{\norm{h}_{2}} = 0 $$

for $h \in X$. In our case, for $h = y - x \in X$, we have that $$ 0 \leq \lim_{h \rightarrow 0} \frac{|f(x + h) - f(x)|}{\norm{h}_{2}} \leq \lim_{h \rightarrow 0} D \norm{h}_{2}^{\alpha/2 - 1} = 0 $$ which shows that $f$ is differentiable at $x \in X$ with derivative $f'(x) \equiv 0$ for each $x \in X$.

Now let $X = \mathbb{R}^{d}$. The derivative $f'(x)$ is an element of dual space $X^{*}$ of Hilbert space $X$. Using Riesz isomorphism $R: X^{*} \rightarrow X$, we can define the gradient $\nabla f(x) = R f'(x)$ as an element of $X$. Then $$ \langle f'(x), h \rangle_{X^{*}, X} = \nabla f(x)^{T} \cdot h $$ where $\cdot$ is the inner product in $X$. Since $\nabla f(x) = 0 \in \mathbb{R}^{d}$, every partial derivative of $f$ is 0, it follows by mean value theorem, that $f$ is a constant function.

Finally, the associated kernel $K(\cdot, \cdot)$ is then also a constant function \begin{align*} \langle K(\cdot, x) - K(\cdot, y), f \rangle_{\mathcal{H}} &= \langle K(\cdot, x), f \rangle_{\mathcal{H}} - \langle K(\cdot, y), f \rangle_{\mathcal{H}} \\ &= f(x) - f(y) = 0 \implies K(\cdot, x) = K(\cdot, y) \quad \text{for all $x, y \in X$} \end{align*}

and thus not positive definite. The determinant of interpolation matrix is $\text{det} \left( K(x_{i}, x_{j}) \right)_{i,j} = 0$.

We can conclude that no positive definite kernel $K$ satisfies the Condition \eqref{condition} for $\alpha > 2$.

$\endgroup$
4
  • $\begingroup$ Thanks, I think I understand the general gist, but there is one thing confusing me: In our case, $f: \mathbb R^d \rightarrow \mathbb R$ (actually, this is a typo in your answer because $f$ is not only defined on $X$. Then you show that $$\frac{\vert f(x) - f(y)\vert}{\vert\vert x-y\vert\vert_2} \leq D\vert\vert x - y\vert\vert^{\frac{\alpha}{2}-1},$$ which I can also follow. But why does the existence of the limit tell us that $f$ is differentiable? After all, we are in a multi-dimensional setup, if we had been in $1D$, I would have immediately agreed... $\endgroup$
    – Hermi
    Commented Sep 7, 2021 at 12:37
  • $\begingroup$ The existence of the limit implies that a bounded linear operator $f'$, or $(\nabla f)^{T}$ in case of $X = \mathbb{R}^{d}$, exists. Then $f$ is called differentiable. I added the Update with the derivation to my answer. Also, the mean value theorem generalizes to real multivariable functions, see section Mean value theorem in several variables on Wiki: en.wikipedia.org/wiki/Mean_value_theorem $\endgroup$ Commented Sep 8, 2021 at 8:38
  • $\begingroup$ Thanks, things are starting to make sense. But I think you mistyped... Shouldn't it read $\langle \nabla f(x), h\rangle$ and $\nabla f: \mathbb R^d \to \mathbb R^d$ instead of $\nabla f: \mathbb R^d \to \mathbb R$? Also check Wikipedia: en.wikipedia.org/wiki/Gradient $\endgroup$
    – Hermi
    Commented Sep 8, 2021 at 11:56
  • $\begingroup$ You're right, I shouldn't have defined $\nabla f(x)$ as the derivative, it is dual to the derivative $f'(x)$, although they are just transpose of each other. In any case, it refers to a mapping into the real numbers ($\mathbb{R}$ not $\mathbb{R}^{d}$), the value of the gradient at a point. I fixed already in my answer also. $\endgroup$ Commented Sep 8, 2021 at 19:29
0
+50
$\begingroup$

Let $\Phi$ correspond to a PD kernel, and assume WLOG that $\Phi(0)=1$. By considering the points $X=\{0,x\}$, we see that $K(x,x)K(0,0)-K(0,x)K(x,0)=\Phi(0)^2-\Phi(x)^2>0$. Thus it must be the case that $\Phi(x)<\Phi(0)=1$ for all $x\neq 0$.

Now consider the sample points $\{0,x/2,x\}$. Writing out the matrix $A_{K,X}$ and using the relation $K(x_i,x_j)=\Phi(|x_i-x_j|)$, we see that the following matrix must be positive definite: \begin{array} {ccc} \Phi(0)& \Phi(x/2)& \Phi(x)\\ \Phi(x/2)& \Phi(0)& \Phi(x/2)\\ \Phi(x)& \Phi(x/2)& \Phi(0)\\ \end{array}

In particular, the determinant must be positive. The determinant is given by

\begin{eqnarray} Det & = & \Phi(0)(\Phi(0)^2-\Phi(x/2)^2)-\Phi(x/2)(\Phi(x/2)\Phi(0)-\Phi(x/2)\Phi(x))+\Phi(x)(\Phi(x/2)^2-\Phi(0)\Phi(x))\\ & = & 1-\Phi(x/2)^2-\Phi(x/2)^2+\Phi(x/2)^2\Phi(x)+\Phi(x)\Phi(x/2)^2-\Phi(x)^2\\ & = &1-2\Phi(x/2)^2+2\Phi(x/2)^2\Phi(x)-\Phi(x)^2\\ &>0& \end{eqnarray} Rearranging,

\begin{eqnarray} (1-\Phi(x)^2)/2&>&\Phi(x/2)^2(1-\Phi(x))\\ (1+\Phi(x))/2&>&\Phi(x/2)^2\\ 1-\Phi(x)&<&2(1-\Phi(x/2)^2)\\ 1-\Phi(x)&<&2(1+\Phi(x/2))(1-\Phi(x/2)) \end{eqnarray} where we used the fact that $1-\Phi(x)>0$ in going from first to second line.

The value of $x$ is arbitrary, so we can replace $x$ with $x/2$ in the above inequality to see that $$1-\Phi(x/2)<2(1+\Phi(x/4))(1-\Phi(x/4))$$

Plugging this back in to the original inequality we get \begin{eqnarray} 1-\Phi(x)&<&2(1+\Phi(x/2))(1-\Phi(x/2))\\ & < & 2(1+\Phi(x/2))*2*(1+\Phi(x/4))(1-\Phi(x/4))\\ & = & 4(1+\Phi(x/2))(1+\Phi(x/4))(1-\Phi(x/4)) \end{eqnarray}

By repeating this process $k$ times, it is easy to verify that we get the following result:

$$1-\Phi(x)<2^k(1-\Phi(x/2^k))\prod_{i=1}^k1+\Phi(x/2^i)$$

for any positive integer $k$. By hypothesis, $(1-\Phi(x/2^k))\leq C |x/2^k|^{\alpha}=C2^{-k\alpha} |x^{\alpha}|$. Furthermore, we have already seen that $\Phi(x)\leq 1$ for all $x$, so the product term is bounded by $2^k$. Thus we have the bound $$1-\Phi(x)<C2^k2^{-k\alpha}|x|^{\alpha}2^k=C2^{k(2-\alpha)}|x|^{\alpha}$$

Recall that $\alpha>2$ by hypothesis. Since $k$ was arbitrary, we can take the limit $k\to\infty$, in which the right hand side vanishes. This implies that $\Phi(x)$ is a constant function, which contradicts the positive definiteness.

$\endgroup$
9
  • $\begingroup$ To be honest, I believe that the current proof is not correct either.. To my understanding, the set $X$ of interpolation points is given, not sth that we can choose (as you do in your second paragraph) arbitrarily.. It also clearly states in the problem formulation (Problem 8.1. of my post) that $X$ is given $\endgroup$
    – Hermi
    Commented May 30, 2021 at 13:15
  • $\begingroup$ @Hermi Either your understanding is mistaken or else the theorem is false for trivial reasons. Take an extreme example where $n=1$. According to your more restrictive interpretation, the only thing we can say about $K$ is that $\Phi(x_1)=K(x_1)>0$, where $x_1$ is some fixed point. But obviously there are continuous functions such that $|\Phi(x)-\Phi(0)|<C|x|^{\gamma}$ for $x<R$ (e.g. take R=|x_1|/2) and $\Phi(x_1)>0$. $\endgroup$ Commented May 31, 2021 at 2:09
  • $\begingroup$ In fact there is a potentially-confusing typo in my previous comment. If $X$ consists of a single point $x_1$, then, if we go by your more restrictive interpretation, the only thing we can say about $\Phi$ is that $K(x_1,x_1)=\Phi(0)>0$. But obviously we can choose $\Phi$ such that $\Phi(0)>0$ and the growth condition in the problem statement is satisfied. So the theorem is clearly false if we only assume that $A_{K,X}$ is p.d. on some fixed set $X$. $\endgroup$ Commented Jun 1, 2021 at 15:18
  • $\begingroup$ Just to make sure: I can follow until the part that by my interpretation, the only thing we can say is that $\Phi\left( 0\right) > 0 $. And I also agree that it is probably not all to hard to come up with any function that satisfies $\Phi(0) > 0$, but: How do you then follow that then "the growth condition in the problem statement is satisfied". Can you explain a bit more more? After all, we have the growth condition $|\Phi(0) - \Phi(x)| \leq C ||x||_2^{\gamma}$, and we still don't know $\Phi(x)$.. $\endgroup$
    – Hermi
    Commented Jun 1, 2021 at 16:11
  • $\begingroup$ I mean that there exists a function $\Phi$ that satisfies both of the conditions: (1) \Phi(0)>0 and (2) the condition on $|\Phi(x)-\Phi(0)|$. And if such a function exists, then that disproves the theorem, at least as you are interpreting it. $\endgroup$ Commented Jun 1, 2021 at 18:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .