How would you argument or prove that this is a valid kernel:
$$ K_a(x, t) = \prod_{i=1}^{n} (1 + x_it_i + (1-x_i)(1-t_i)). $$
I know that there are two conditions that a kernel must satisfy to be a valid kernel: symmetry and positive-semidefiniteness. Clearly the first condition is satisfied. But I am not sure how to prove the second.
I have re-arranged the expression as:
$$ K_a(x, t) = \prod_{i=1}^{m}2\left(x_i – \frac{1}{2}\right)\left(t_i – \frac{1}{2}\right) + \frac{3}{2},$$
but I am unsure if this is of any help. Thanks.
Best Answer
Let's build this kernel up piecewise, using a bunch of properties that allow you to do that. The two forms are about the same for doing that, but let's use the second one.
Scaling: If $k$ is a psd kernel, then so is $\gamma k$ for $\gamma \ge 0$.
Sum: If $k_1$ and $k_2$ are psd kernels, then $k_1 + k_2$ is psd.
Product: If $k_1$ and $k_2$ are psd kernels, then so is $f(x, y) = k_1(x, y) k_2(x, y)$.
(These are proved e.g. in this answer.)
Shift: If $k(x, y)$ is a valid kernel, so is $k_\delta(x, y) = k(x + \delta, y + \delta)$ for any constant $\delta$.
Proof: if $\varphi(x)$ is the feature map for $k$, then $x \mapsto \varphi(x + \delta)$ is the feature map for $k_\delta$.
Projection: if $k(x, y)$ is a valid kernel on $\mathcal X$, then $k'(\vec x, \vec y) = k(x_\ell, y_\ell)$ is a valid kernel on $\mathcal X^d$ for any dimension $\ell \in \{1, \dots, d\}$.
Proof: For any points $\{\vec x_j \}_{j=1}^n$ and corresponding constants $a_i$, $$\sum_{i,j} a_i k'(\vec x_i, \vec x_j) a_j = \sum_{i,j} a_i k(x_{i,\ell}, y_{j,\ell}) \ge 0$$ since $k$ is a psd kernel.
Constants: $k(x, y) = \gamma$ is psd for any $\gamma \ge 0$, on any input set.
Proof: $\sum_{i,j} a_i k(x, y) a_j = \gamma \sum_{i,j} a_i a_j = \gamma \lVert a \rVert^2 \ge 0.$
Now: