Although sparse representation (SR) based on the -norm and -norm have achieved promising classification results for face recognition (FR) from frontal views, they both require an overcomplete training dictionary, which is usually unrealistic. We focus on addressing the problem of performing FR with SR with an incomplete dictionary. Motivated by the fact that image gradients could explicitly consider the relationships between neighboring pixel points and be less sensitive to illumination than image pixels, we introduce image gradients to SR and propose gradient-based sparse representation classification (GSRC). By combining image pixels and image gradients, GSRC has less model error and requires fewer training samples from each individual than sparse representation–based classification (SRC). Furthermore, GSRC can easily be combined with dimensionality reduction algorithms and be solved by the regularized least-square method, which makes GSRC work much faster than SRC. Extensive experimental results demonstrate that GSRC is quite efficient for both incomplete dictionary and occlusion and has a reasonable speed.