Designing patch-level features is essential for achieving good performance in computer vision tasks, such as image classification and object recognition. SIFT (scale-invariant feature transform) and HOG (histogram of oriented gradient) are the typical schemes among many pre-defined patch-level descriptors, but the difference between artificial patch-level features is not good enough for reflecting the similarities of images. Kernel descriptor (KD) method offers a new way to generate features from match kernel defined over image patch pairs using KPCA (kernel principal component analysis) and yields impressive results. However, all joint basis vectors are involved in the kernel descriptor computation, which is both expensive and not necessary. To address this problem, this paper presents an efficient patch-level descriptor (EPLd) which is built upon incomplete Cholesky decomposition. EPLd automatically selects a small number of image patches pivots to achieve better computational efficiency. Based on EPLd, MMD (maximum mean discrepancy) distance is used for computing similarities between images. In experiments, the EPLd approach achieves competitive results on several image/scene classification datasets compared with state-of-the-art methods.