This paper addresses the very low resolution (VLR) problem in face recognition in which the resolution of face image to be recognized is lower than 16×16. The VLR problem happens in many surveillance camera-based applications and existing face recognition algorithms are not able to give satisfactory performance on VLR face image. While face super-resolution (SR) methods can be employed to enhance the resolution of the images, the existing learning-based face SR methods do not perform well on such a very low resolution face image. To overcome this problem, this paper models the SR problem under VLR case as a regression problem with two constraints. First, a new data constraint is design to perform the error measurement on high resolution image space which provides more detailed and discriminative information. Second, discriminative constraint is proposed and incorporated in the training stage so that the reconstructed HR image has higher discriminability. CMU-PIE, FRGC and surveillant camera face (SCface) databases are selected for experiments. Experimental results show that the proposed method outperforms the existing methods, in terms of image quality and recognition accuracy.