In this paper, we are comparing the optimization algorithms incorporated with overcomplete discrete cosine transform (DCT) based dictionary and discrete Tchebichef transform (DTT) basis function used as a dictionary for sparse representation. Further, we measured the performance of optimization greedy algorithm family e.g., Matching Pursuit (MP), Orthogonal Matching Pursuit (OMP) and Stage-wise Orthogonal Matching Pursuit (St-OMP) and convex relaxation technique like Basis Pursuit (BP) on proposed pre-specified dictionaries in terms of accuracy and probability of error. We also compared performance in terms of sparse coefficients recovery atoms and analyzed the error of probability over small image patch using the fixed dictionaries. Result showed that our proposed dictionary based on DTT basis function performed well and also convex relaxation achieved good sparse coefficients as compared to other optimization algorithms. The BP produced more accuracy as compared to greedy techniques with little increase of the processing time. © 2015 IEEE.