In recent years, the emergence of the new paradigm of compressive sensing (CS) has led to the development of innovative image/signal processing and analysis tools that can be exploited to efficiently deal with serious challenges in pattern recognitions. This paper is concerned with the use of CS tools and dictionaries for face recognition, and in particular when dealing with uncontrolled conditions, e.g. faces captured at a distance in surveillance scenarios or in post-rioting forensic, whereby the images are severely degraded/blurred and of low-resolution. We present the results of our recent investigations into the construction of over-complete dictionaries that recover super-resolved face images from any input low-resolution degraded face image. These results demonstrate that non-adaptive image-independent implicitly designed dictionaries that guarantee the recovery of sparse signals achieve face recognition accuracy levels and yield significant recognition rates that are as good as if not better than those achieved by a recently proposed image-based learnt dictionaries. We shall also show that a variety of random dictionaries known to satisfy the Restricted Isometry Property (RIP), achieve similar accuracy rates, and thereby removing the need for training images. The high quality of the super-resolved images provides great potential for forensics and crime/terrorism fighting.