Face recognition under natural scenes is a significant challenge in pattern recognition research. With the success of sparse representation-based classification in related fields, face recognition based on compressed sensing (CS) theory has received increasing attention. These CS-based approaches produce excellent results when dealing with face data from experimental environments, but are inadequate when dealing with images from natural scenes. For solving this problem, a novel Generalized Compressed Sensing (GCS) framework is proposed in this paper. The main innovations of this paper are three-fold. First, with reference to the commutative property of the inner product, GCS recovery treats the original CS matrix, not the original signal, as the processing object. Second, in order to ensure the reliability and feasibility of GCS recovery, a QR-based vision matrix learning method is presented to realize face information embedding for the original CS matrix. Third, to balance the restricted isometry property (RIP) of the original CS matrix for CS sampling and its sparsity for GCS recovery, a low density parity check code is introduced to generate the original CS matrix. With this full CS framework including CS sampling and GCS recovery, the final generalized l-norm optimal solution can be used as the criterion for face recognition. Experimental results show that, compared with conventional approaches to CS recognition, the proposed method achieves a significant performance for face recognition tasks under natural scenes.