This thesis presents a new approach to single-image super-resolution (SR), based on sparse signal recovery.Research on image statistics suggests that image patches can be well represented as a sparse linearcombination of elements from an appropriately chosen over-complete dictionary. Inspired by this observation,we seek a sparse representation for each patch of the low-resolution input, and then use the coefficientsof this representation to generate the high-resolution output. Theoretical results from compressed sensingsuggest that under mild conditions, the sparse representation can be correctly recovered from the downsampledsignals. By jointly training two dictionaries for the low- and high-resolution image patches, wecan enforce the similarity of sparse representations between the low- and high-resolution imagepatch pairs with respect to their own dictionaries. Therefore, the sparse representation of a low-resolutionimage patch can be applied with the dictionary of high-resolution image patches to generate a high-resolutionimage patch. Compared to previous approaches, which simply sample a large amount of raw image patch pairs,the learned dictionary pair is a more compact representation of the patch pairs, and, therefore, reduces thecomputation cost substantially. The effectiveness of such a sparsity prior is demonstrated on both generalimage super-resolution and the special case of face hallucination. In both cases, our algorithm can generatehigh-resolution images that are competitive or superior in quality to images produced by other similarSR methods, but with much faster processing speed.