In a lot of articles, the linear kernel (inner product of two matrices) is listed as positive definite however when I try it with a toy dataset, positive definiteness test returns negative result. I checked the MATLAB SVM function for linear kernel.
The linear kernel function is one line command,
K=(u*v')
However after this step in the main svm_train function it does another operation using K,
kx= (kx+kx')/2 + diag(1./boxconstraint)
Where kx is K and diag(1./boxconstraint) is just a diagonal matrix of size kx and resultant kx pass the positive definiteness test. As an explanation of this step it says
'% ensure function is symmetric.' I also checked libsvm but I could not find this additional operation there.
However the inner product is already symmetric and this step is usually used to turn indefinite matrices into positive definite matrices. I am a bit confused about why inner product kernel does not pass the positive definiteness test?
If u,v are both row vectors (i.e. K evaluates to a scalar), K will only be positive definite if K=dot(u,v)>0.
If u and v are more general matrices (not row vectors) and u~=v, then K=u*v' will not generally be symmetric, let alone positive definite. Even when u=v, K will be non-negative definite, but will not be strictly positive definite unless u has full row rank. However, the additional matrix 1./diag(boxconstraint) is strictly positive definite assuming all boxconstraint(i)>0. Adding a non-negative definite matrix to a strictly positive definite matrix produces a strictly positive definite result always.