In kernel machines we have some kernel function $k$ and we compute the $n \times n$ Gram matrix $K$ where $K_{ij} = k(x_i, x_j)$ for observations $x_i, x_j \in \mathbb R^p$. I'm letting $n$ denote the number of observations and $p$ the number of variables.

My question: how does the rank of the resulting $K$ relate to algorithm performance?

For example, if $k$ is the radial basis function then $K$ will always be full rank (since it is positive definite). Is this related to how SVM with the rbf kernel has infinite VC dimension? If instead $k$ is the polynomial kernel then the rank of $K$ is not necessarily $n$, and is smaller for smaller degrees, which definitely suggests that the rank of $K$ is related to the flexibility of a classifier using the corresponding kernel. What's really going on here?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.