Kernel sparse representation for classification (KSRC) has attracted much attention in pattern recognition community in recent years. Although it has been widely used in many applications such as face recognition, KSRC still has some open problems needed to be addressed. One is that if the training set is of a small scale, KSRC may potentially suffer from lack of training samples when a nonlinear mapping is used to transform the original input data into a high dimensional feature space, which is often accomplished using a kernel-based method. In order to address this problem, this work proposes a scheme that automatically yields a number of new training samples, termed virtual dictionary, from the original training set. We then use the yielded virtual dictionary and the original training set to build the KSRC model. To improve the computational efficiency of KSRC, we exploit the coordinate descend algorithm to solve the KSRC model. Our approach is referred to as kernel coordinate descent based on virtual dictionary (KCDVD). KCDVD is easy to implement and is computationally efficient. Experiments on many face databases show that the proposed algorithm is effective at remedying the problem with small training samples.