We propose a novel single-image super resolution (SISR) approach using self-similarity of image and the low-rank matrix recovery (LRMR). The method performs multiple upsampling steps with relatively small magnification factors to recover a desired high resolution image. Each upsampling process includes the following steps: First, a set of low/high resolution (LR/HR) patch pairs is generated from the pyramid of the input low resolution image. Next, for each patch of the unknown HR images, similar HR patches are found from the set of LR/HR patch pairs by the corresponding LR patch and are stacked into a matrix with approximately low rank. Then, the LRMR technique is exploited to estimate the unknown HR image patch. Finally, the back-projection technique is used to perform the global reconstruction. We tested the proposed method on fifteen images including humans, animals, plants, text, and medical images. Experimental results demonstrate the effectiveness of the proposed method compared with several representative methods for SISR in terms of quantitative metrics and visual effect.