In this paper the face recognition problem is addressed in a part-based sparse approach through the comparison of respective facial regions between different images. To this purpose, a sparse coding procedure is applied to non-overlapping patches derived from frontal-face images, in order to extract local facial information. An adequate measure is introduced, incorporating the resulted sparse representation along with the Hamming distance, in order to express pairwise similarities between faces. Finally, a simple Nearest Neighbor classifier is employed to determine the identity of each facial image. In addition, a new criterion is presented for the rejection of outliers. The emerged face recognition scheme is evaluated using publicly available facial image databases, and the results are compared with those of other well-established recognition methods.