[PYTHON] Semi-definite matrix check of convolution kernel

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}