The Sparse representation research field and applications have been rapidly growing during the past 15 years. The use of overcomplete dictionaries in sparse representation has gathered extensive attraction. Sparse representation was followed by the concept of adapting dictionaries to the input data (dictionary learning). The K-SVD is a well-known dictionary learning approach and is widely used in different applications. In this thesis, a novel enhancement to the K-SVD algorithm is proposed which creates a learnt dictionary with a specific number of atoms adapted for the input data set. To increase the efficiency of the orthogonal matching pursuit (OMP) method, a new sparse representation method is proposed which applies a multi-stage strategy to reduce computational cost. A new phase included DCT (PI-DCT) dictionary is also proposed which significantly reduces the blocking artifact problem of using the conventional DCT. The accuracy and efficiency of the proposed methods are then compared with recent approaches that demonstrate the promising performance of the methods proposed in this thesis.