title: Polynomial Kernel not PSD?
body: <p>I am currently going through different Machine Learning methods on a low-level basis. Since the polynomial kernel </p>
  
  <blockquote>
    <p>K(x,z)=(1+x^T*z)^d</p>
  </blockquote>
  
  <p>is one of the more commonly used kernels, I was under the assumption that this kernel must yield a positive (semi-)definite matrix for a fixed set of data {x1,...,xn}.
  However, in my implementation, this seems to not be the case, as the following example shows:</p>
  
  <pre><code>import numpy as np    
  np.random.seed(93)
  x=np.random.uniform(0,1,5)
  #Assuming d=1
  kernel=(1+x[:,None]@x.T[None,:])
  np.linalg.eigvals(kernel)
  </code></pre>
  
  <p>The output would be</p>
  
  <pre><code>[ 6.9463439e+00  1.6070016e-01  9.5388039e-08 -1.5821310e-08  -3.7724433e-08]
  </code></pre>
  
  <p>I'm also getting negative eigenvalues for d>2.
  Am I totally misunderstanding something here? Or is the polynomia kernel simply not PSD?</p>
  
  <p>EDIT: In a previous version, i used <code>x=np.float32(np.random.uniform(0,1,5))</code> to reduce computing time, which lead to a greater amount of negative eigenvalues (I believe due to numerical instabilities, as @user2357112 mentioned). I guess this is a good example that precision does matter? Since negative eigenvalues still occur, even for float64 precision, the follow-up question would then be how to avoid such numerical instabilities?</p>