Abstract With the rapid increase in the available data, it becomes computationally harder to extract useful information. Thus, several techniques like PCA were proposed to embed high-dimensional data into lowdimensional latent space. However, these techniques don’t take the data relations into account. This motivated the development of other techniques like MDS and LLE which preserve the relations between the data instances. Nonetheless, all these techniques still use latent features, which are difficult for data analysts to understand and grasp the information encoded in them. In this work, a new embedding technique is proposed to mitigate the previous problems by projecting the data to a space described by few points (i.e, exemplars) which preserves the relations between the data points. The proposed method Exemplar-based Kernel Preserving (EBEK) embedding is shown theoretically to achieve the lowest reconstruction error of the kernel matrix. Using EBEK in approximate nearest neighbor task shows its ability to outperform related work by up to 60% in the recall while maintaining a good running time. In addition, our interpretability experiments show that EBEK’s selected basis are more understandable than the latent basis in images datasets.