A major limitation of these approaches is patch similarities are not directly linked to object categories. Therefore, a supervised approach to learning patch-level features that takes into account image class labels is in urgent need. In this paper, we achieve this goal by proposing supervised efficient kernel descriptors (SEKD), in which incomplete Cholesky decomposition is performed jointly with image class label in feature learning. Experimental results on several well-known image classification benchmarks suggest that SEKDs are more compact and have superior discriminative power than previous unsupervised feature descriptors.