Is linear kernel positive definite?

Question

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?

Answer 1

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.

Answer 2

OK, what you say makes sense actually, when I create a toy dataset with a full row rank, inner product matrix becomes positive definite. If there is even two linear dependent rows then it is not positive definite anymore. I'll accept your answer. Thanks.