System and method embodiments for image coding are disclosed. In an embodiment, a method in a data processing system for image encoding includes determining a sparsity constraint according to a dimension of an input image signal. The method also includes iteratively determining a plurality of approximations to the input image signal. Each iteration provides an approximation of the input image signal. Each approximation includes a set of dictionary element indices and coefficients. The dictionary is an over-complete dictionary. Iterations of the determining step are terminated when a number of iterations is equal to the sparsity constraint. The method also includes selecting one of the plurality of approximations according to a minimum rate-distortion cost. The method also includes determining an encoded image signal according to non-zero coefficients and corresponding indices for each non-zero coefficient in the selected approximation.