This paper proposes a novel speech enhancement algorithm based on a low-rank sparse decomposition model. The sparse and low-rank components of a corrupted signal are considered as speech and noise in time-frequency domain, respectively. We use a new alternating optimization algorithm for accurate decomposition of the noisy observed data using sparse coding over the speech and noise dictionaries. Adequate noise training frames with the same data size as speech data are provided by a noise estimation algorithm to learn the overcomplete noise dictionaries with low sparse approximation error. Since encountering non-stationary noises reduces the performance of speech enhancement methods, we take advantage of domain adaptation method which is a novel speech enhancement procedure to transform a learned noise dictionary to an adapted dictionary by data distribution captured in the enhancement process. Using this step, an adapted separation scheme based on the current situation of noisy space is carried out, and the main drawbacks seen in the earlier dictionary-learning-based speech enhancement methods are solved. The proposed approach results in a significant reduction of noise, especially for non-stationary noises, in comparison with the earlier methods in this context and the traditional procedures, based on different objective and subjective measures.