How does linear SVMs function in multi dimensional feature space? I'm not able to picture how a linear SVM can perform classification in more than 2 dimensions. Also, when to chose linear SVMs and kernel based SVMs? For example, my dataset has over 5000 instances with 4000 features.
Linear SVM always works in the exact same way, even if you can't mentally wrap your head around the geometrics. Humans are generally bad at reasoning in more than three dimensions, so don't let that worry you.
Imagine linear SVM in one dimension. This would look something like this:
+ + + + + | - - - -
where | is your decision boundary. A hyperplane in one dimension is a cutoff value. In two dimensions, you get a line. In three dimensions, you get a plane, ...
With 4000 features in input space, you probably don't benefit enough by mapping to a higher dimensional feature space (= use a kernel) to make it worth the extra computational expense. Hence, use a linear kernel.
In fact, always use the linear kernel first and see if you get satisfactory results. Generally, you can try a nonlinear kernel if and only if you don't get good results with a linear kernel.