Abstract: The Very Low Resolution (VLR) problem happens in many face recognition application systems given the increasing demand for camera-based surveillance applications,. Currently, the existing face recognition algorithms cannot deliver satisfactory performance with VLR face images. While face super-resolution (SR) methods can be employed to enhance the resolution of the images, the existing dictionary learning-based face SR methods are inadequate for VLR face images. To overcome this problem, we propose a novel SR face reconstruction method based on non-local similarities and multi-scale linear combinations and subsequently, a new approach for VLR face recognition based on resolution scale invariant features. Experimental results show that the proposed approach based on dictionary learning outperforms the existing algorithms in public face databases, obtaining a good visuality suitable for face recognition applications subject to the VLR problem.