Recently, patch-based sparse representation has been used as a statistical image modeling technique for various image restoration applications, due to its ability to model well the natural image patches and automatically discover interpretable visual patterns. Standard sparse representation however does not consider the intrinsic and geometric structure present in the data, thereby leading to sub-optimal results. In this paper, we exploit the concept that a signal is block sparse in a given basis-i.e., the non-zero elements occur in clusters of varying sizes-and propose an efficient framework for learning sparse representation modeling of natural images, called graph regularized block sparse representation (GRBSR). The proposed GRBSR is able to sparsely represent natural images in the domain of a block, which enforces the intrinsic local sparsity. We apply the proposed GRBSR to learn a dictionary-based local regression model for super-resolving a single low-resolution image without any external training image sets. We show that the proposed method provides improved performance as compared to the existing single-image super-resolution methods by running them on various input images containing diverse textures or other artifacts.