We consider the problem of sparse modeling of a signal consisting of an unknown number of exponentially decaying sinusoids. Since such signals are not sparse in an oversam-pled Fourier matrix, earlier approaches typically exploit large dictionary matrices that include not only a finely spaced frequency grid but also a grid over the considered damping factors. The resulting dictionary is often very large, resulting in a computationally cumbersome optimization problem. Here, we instead introduce a novel dictionary learning approach that iteratively refines the estimate of the candidate damping factor for each sinusoid, thus allowing for both a quite small dictionary and for arbitrary damping factors, not being restricted to a grid. The performance of the proposed method is illustrated using simulated data, clearly showing the improved performance as compared to previous techniques.