The presented work revolves around sparsity. It contributes to dictionary training for sparse representation with a new algorithm and analysis. It showcases the usability of trained dictionary in image processing problems. It demonstrates a new framework for image recovery (inpainting and denoising) using sparse representation. In the end, it proposes an extension of the well-known sparse signal recovery algorithm, Orthogonal Matching Pursuit (OMP) for compressed sensing. It also provides a complete analysis of the proposed extension, and its theoretical guarantees.