The development of automated methods of electroencephalogram (EEG) seizure detection is an important problem in neonatology. This paper proposes improvements to a previously described method of seizure detection based on atomic decomposition by developing a new time-frequency (TF) dictionary that is highly coherent with the newborn EEG seizure. We compare the performance of the proposed dictionary on neonatal EEG signals with that achieved using Gabor, Fourier and wavelet dictionaries. Through the analysis of real newborn EEG data, we show first, that dictionary selection can influence the seizure detection accuracy and second, that the proposed dictionary outperforms other dictionaries by at least 10% in seizure detection accuracy and 5% improvement in the area under the Receiver Operator Characteristic curve.