In this paper, we propose a novel algorithm for fast single image super-resolution based on self-example learning and sparse representation. We propose an efficient implementation based on the K-singular value decomposition (SVD) algorithm, where we replace the exact SVD computation with a much faster approximation, and we employ the straightforward orthogonal matching pursuit algorithm, which is more suitable for our proposed self-example-learning-based sparse reconstruction with far fewer signals. The patches used for dictionary learning are efficiently sampled from the low-resolution input image itself using our proposed sample mean square error strategy, without an external training set containing a large collection of high- resolution images. Moreover, the l ⁰ -optimization-based criterion, which is much faster than l ¹ -optimization-based relaxation, is applied to both the dictionary learning and reconstruction phases. Compared with other super-resolution reconstruction methods, our low- dimensional dictionary is a more compact representation of patch pairs and it is capable of learning global and local information jointly, thereby reducing the computational cost substantially. Our algorithm can generate high-resolution images that have similar quality to other methods but with an increase in the computational efficiency greater than hundredfold.