Check using empirical rules Set N and d to any value and repeat any number of times.
checkpositivesemidefinite.py
import numpy as np
def possemicheck(X,C):
N = len(C)
K = np.empty([N,N])
summe = 0
for i in range(N):
for j in range(N):
K[i][j] = np.linalg.norm(np.convolve(X[i],X[j]))**2
summe = summe + (C[i]*C[j]*K[i][j])
if (summe>=0):
output = True
else:
output = False
return output, summe
N = 300 #Number of datasets
d = 200 #Data set dimensions
ite = 10 #Number of repetitions
a = 1
for i in range(ite):
X = np.random.randn(N, d)
C = np.random.randn(N)
output, summe = possemicheck(X,C)
print summe
a = a * output
if (a==True):
print("the kernel is positive semi-definite")
else:
print("the kernel is not positive semi-definite")
Mathematical proof
possemidef.tex
\documentclass{amsart}
\usepackage{pdfpages}
\title{Possemidef}
\begin{document}
Covolution Kernel\\
Let $x$, $x'$ be two univariate real-valued discrete time series.\\
\begin{eqnarray*}
k(x,x') = || x \ast x'||^2
\end{eqnarray*}
\\
Proof that the convolution kernel is positive semi-definite: \\
\begin{eqnarray*}
\sum_i \sum_j c_i c_j k(x_i, x_j) \geq 0 \ \ \ \ c_i, c_j \in \mathbb{R}
\end{eqnarray*}
\begin{equation*}
\left.
\begin{array}{r@{\;}ll}
\sum_i \sum_j c_i c_j k(x_i, x_j) & = \sum_i \sum_j c_i c_j || x_i \ast x_j||^2 &\\
&=\sum_i \sum_j c_i c_j \sum_t(\sum_{\tau} x_i(\tau)x_j(t-\tau) )^2 &\\
&=\sum_i \sum_j c_i c_j \sum_t(\sum_{\tau} x_i(\tau)x_j(t-\tau) )(\sum_{\tau'} x_i(\tau')x_j(t-\tau') )& \ \ \ | \ \ x_i * x_j = x_j * x_i \ \ \ \\
&=\sum_i \sum_j c_i c_j \sum_t(\sum_{\tau} x_i(\tau)x_j(t-\tau) )(\sum_{\tau'} x_j(\tau')x_i(t-\tau') )& \\
&= \sum_t \sum_i \sum_j c_i c_j \sum_{\tau}\sum_{\tau'} x_i(\tau)x_j(t-\tau) x_j(\tau')x_i(t-\tau')& \ \ \ |s = t - \tau -\tau' \\
& & \ \ \ |t - \tau = s + \tau' \\
& & \ \ \ |t - \tau' = s + \tau \\
&=\sum_s \sum_i \sum_j c_i c_j \sum_{\tau}\sum_{\tau'} x_i(\tau)x_j(s+\tau') x_j(\tau')x_i(s+\tau) & \\
&=\sum_s \sum_i \sum_j c_i c_j \sum_{\tau}\sum_{\tau'} x_i(\tau)x_i(s+\tau) x_j(\tau')x_j(s+\tau') & \\
&=\sum_s (\sum_i \sum_{\tau} c_i x_i(\tau)x_i(s+\tau))( \sum_j \sum_{\tau'}c_j x_j(\tau')x_j(s+\tau')) & \\
&=\sum_s (\sum_i \sum_{\tau} c_i x_i(\tau)x_i(s+\tau))^2 \geq 0
\end{array}
\right\}
\end{equation*}
\end{document}
Recommended Posts