The use of non-uniform sampling of NMR spectra may give significant reductions in the data acquisition time. For quantitative experiments such as the measurement of spin relaxation rates, non-uniform sampling is however not widely used as inaccuracies in peak intensities may lead to errors in the extracted dynamic parameters. By systematic reducing the coverage of the Nyquist grid of (15)N Carr-Purcell-Meiboom-Gill (CPMG) relaxation dispersion datasets for four different proteins and performing a full data analysis of the resulting non-uniform sampled datasets, we have compared the performance of the multi-dimensional decomposition and iterative re-weighted least-squares algorithms in reconstructing spectra with accurate peak intensities. As long as a single fully sampled spectrum is included in a series of otherwise non-uniform sampled two-dimensional spectra, multi-dimensional decomposition reconstructs the non-uniform sampled spectra with high accuracy. For two of the four analyzed datasets, a coverage of only 20 % results in essentially the same results as the fully sampled data. As exemplified by other data, such a low coverage is in general not enough to produce reliable results. We find that a coverage level not compromising the final results can be estimated by recording a single full two-dimensional spectrum and reducing the spectrum quality in silico.