Methods for super-resolution can be classified into three categories: (i) The Interpolation-based methods, (ii) The Reconstruction-based methods (iii) The Learning-based methods. The Learning-based methods usually have the best performance due to the learning process. However, learning-based methods can’t be applied to video super-resolution due to the great computational complexity. We proposed a fast sparsity-based video super-resolution algorithm by utilizing inter-frame information. Firstly, the background can be extracted via existing methods such as Gaussians Mixture Model(GMM) in this paper. Secondly, we construct background and foreground patch dictionaries by randomly sampling patches from high-resolution video. During the process of video super-resolution, only the foreground regions are reconstructed using foreground dictionary via sparse coding. Respectively the background is updated and only changed regions of the background is reconstructed using background dictionary in the same way. Finally, the background and foreground should be fused to get the super-resolution outcome. The experiments show that it makes sparsity-based methods much faster in video super-resolution with approximate, even better, performance.