6
$\begingroup$

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?

$\endgroup$

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.